Η εύρεση των εξαρτήσεων ενός προγράμματος είναι ένα σημαντικό κομμάτι τριών εργασιών :
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 1
ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 1 Είναι αναγκαίο να βρούμε όλες τις εξαρτήσεις και να καθορίσουμε αν υπάρχει κάποιος κύκλος στις εξαρτήσεις, αφού το γεγονός αυτό μας εμποδίζει να τρέξουμε το βρόχο παράλληλα. Παράδειγμα
D[i] = A[i] * E[i]        }
Επειδή η εξάρτηση που συνεπάγεται ο πίνακας Α δεν είναι εξάρτηση που μεταφέρεται με το βρόχο, μπορούμε να αναπτύξουμε το βρόχο και να εκτελέσουμε παράλληλα τις πολλαπλές επαναλήψεις του βρόχου, διατηρώντας όμως, τη σειρά για κάθε ζευγάρι εντολών σε κάθε επανάληψη. Η δεύτερη αναφορά στον πίνακα Α δε χρειάζεται να μεταφραστεί σε μια εντολή φόρτωσης, αφού η τιμή έχει ήδη υπολογιστεί από την προηγούμενη εντολή. Η βελτιστοποίηση αυτή, απαιτεί οι δύο αναφορές να είναι πάντα στην ίδια διεύθυνση μνήμης και ότι δεν μεσολαβεί πρόσβαση στην ίδια θέση.
Συνήθως, η ανάλυση της εξάρτησης δεδομένων δείχνει ότι μία αναφορά μπορεί να εξαρτάται από μία άλλη. Όμως, μία πιο πολύπλοκη ανάλυση απαιτείται για να καθορίσουμε ότι οι δύο αναφορές πρέπει να βρίσκονται ακριβώς στην ίδια διεύθυνση. Στο παραπάνω παράδειγμα, αρκεί μία απλή έκδοση αυτής της ανάλυσης, αφού οι αναφορές βρίσκονται στο ίδιο βασικό μπλοκ.
Σε πολλούς παράλληλους βρόχους ο βαθμός της παραλληλίας περιορίζεται μόνο από τον αριθμό των αναπτύξεων, ο οποίος περιορίζεται μόνο από τον αριθμό των επαναλήψεων του βρόχου. Βέβαια, στην πράξη, η εκμετάλλευση της παραλληλίας θα απαιτούσε πολλές λειτουργικές μονάδες και πιθανόν ένα τεράστιο αριθμό καταχωρητών. Η απουσία εξάρτησης που μεταφέρεται με το βρόχο, απλά δηλώνει ότι έχουμε διαθέσιμο ένα μεγάλο βαθμό παραλληλίας.
Συχνά οι εξαρτήσεις που μεταφέρονται με τον βρόχο εμφανίζονται στη μορφή μιας αναδρομής :
Μία αναδρομή συμβαίνει όταν, μία μεταβλητή υπολογίζεται από την τιμή της από προηγούμενη επανάληψη και συχνά από την αμέσως προηγούμενη. Η ανίχνευση των αναδρομών είναι σημαντική γιατί ένα πλήθος αναδρομών μπορεί να αποτελέσει την πηγή για μια λογική ποσότητα παραλληλίας. Αυτό φαίνεται από το παρακάτω παράδειγμα.
Παράδειγμα
Όλοι οι αλγόριθμοι ανάλυσης εξάρτησης δουλεύουν με την προϋπόθεση ότι οι δείκτες του πίνακα είναι συγγενικοί. Ο δείκτης ενός μονοδιάστατου πίνακα είναι συγγενικός όταν έχει τη μορφή a * i + b, όπου a και b σταθερές και i μεταβλητή δείκτη βρόχου.
Υποθέτουμε ότι αποθηκεύουμε σε ένα στοιχείο του πίνακα με δείκτη a * i + b και φορτώνουμε από τον ίδιο πίνακα με δείκτη c * i + d, όπου i είναι η μεταβλητή που παίρνει τιμή από m έως n. Μία εξάρτηση υπάρχει εάν ισχύουν δύο συνθήκες :
Μία απλή και επαρκής εξέταση για την απουσία εξάρτησης είναι ο μέγιστος κοινός διαιρέτης (GCD). Βασίζεται στην παρατήρηση ότι, εάν υπάρχει εξάρτηση μεταφερόμενη με τον βρόχο, τότε ο μέγιστος κοινός διαιρέτης των (c,a) πρέπει να διαιρεί το (d-b).
Παράδειγμα
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 2
ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 2 ΔΡΑΣΤΗΡΙΟΤΗΤΑ 3
ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 3 Υπάρχουν περιπτώσεις όπου ο μέγιστος κοινός διαιρέτης αν και είναι επιτυχής δεν υπάρχουν εξαρτήσεις. Αυτό συμβαίνει, για παράδειγμα, όταν ο μέγιστος κοινός διαιρέτης δεν λαμβάνει υπόψη του τα όρια του βρόχου.
Παράδειγμα Βρείτε όλες τις πραγματικές εξαρτήσεις, τις εξαρτήσεις εξόδου και τις αντι-εξαρτήσεις. Εξαλείψτε τις εξαρτήσεις εξόδου και τις αντι-εξαρτήσεις με χρήση της μεθόδου της μετονομασίας.
Ανάμεσα στις τέσσερις εντολές του βρόχου υπάρχουν οι ακόλουθες εξαρτήσεις : Η παρακάτω εκδοχή του βρόχου εξαλείφει τις εξαρτήσεις αυτές :
Στην εντολή S1 ο Υ μετονομάστηκε σε T με σκοπό τη μετακίνηση της εξάρτησης εξόδου. Στην εντολή S2 ο X μετονομάστηκε σε X1 με σκοπό τη μετακίνηση της αντι-εξάρτησης. Στις εντολές S3 και S4 ο Υ μετονομάστηκε σε T με σκοπό τη μετακίνηση της αντι-εξάρτησης.
X[i] = X[i] + c; /*S2*/
Z[i] = Y[i] + c; /*S3*/
Υ[i] = c - Y[i] ; /*S4*/ }
X1[i] = X[i] + c; /*S2*/
Z[i] = T[i] + c; /*S3*/
Υ[i] = c - T[i] ; /*S4*/ }
|
|