Κεφάλαιο 2 | Ενότητα8 | Ερωτήσεις επισκόπησης | Επόμενο| Λεξικό όρων

Ανίχνευση και εξάλειψη εξαρτήσεων

   Η εύρεση των εξαρτήσεων ενός προγράμματος είναι ένα σημαντικό κομμάτι τριών εργασιών :

  1. Καλός προγραμματισμός του κώδικα.
  2. Καθορισμός των βρόχων που μπορεί να περιέχουν παραλληλισμό.
  3. Εξάλειψη των εξαρτήσεων ονόματος.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 1

Θυμάστε πότε προκύπτουν οι εξαρτήσεις ονομάτων και τα είδη στα οποία χωρίζονται; Για περισσότερες λεπτομέρειες καλό θα ήταν να ανατρέξετε στην δεύτερη ενότητα αυτού του κεφαλαίου: «Είδη εξαρτήσεων-Εξαρτήσεις δεδομένων και ονομάτων».

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 1



Είναι αναγκαίο να βρούμε όλες τις εξαρτήσεις και να καθορίσουμε αν υπάρχει κάποιος κύκλος στις εξαρτήσεις, αφού το γεγονός αυτό μας εμποδίζει να τρέξουμε το βρόχο παράλληλα.

Παράδειγμα

Θεωρήστε το παρακάτω τμήμα κώδικα :

for ( i = 1 ; i 100 ; i = i+1) {
A[i] = B[i] + C[i]
D[i] = A[i] * E[i]          }


Επειδή η εξάρτηση που συνεπάγεται ο πίνακας Α δεν είναι εξάρτηση που μεταφέρεται με το βρόχο, μπορούμε να αναπτύξουμε το βρόχο και να εκτελέσουμε παράλληλα τις πολλαπλές επαναλήψεις του βρόχου, διατηρώντας όμως, τη σειρά για κάθε ζευγάρι εντολών σε κάθε επανάληψη. Η δεύτερη αναφορά στον πίνακα Α δε χρειάζεται να μεταφραστεί σε μια εντολή φόρτωσης, αφού η τιμή έχει ήδη υπολογιστεί από την προηγούμενη εντολή. Η βελτιστοποίηση αυτή, απαιτεί οι δύο αναφορές να είναι πάντα στην ίδια διεύθυνση μνήμης και ότι δεν μεσολαβεί πρόσβαση στην ίδια θέση.

Συνήθως, η ανάλυση της εξάρτησης δεδομένων δείχνει ότι μία αναφορά μπορεί να εξαρτάται από μία άλλη. Όμως, μία πιο πολύπλοκη ανάλυση απαιτείται για να καθορίσουμε ότι οι δύο αναφορές πρέπει να βρίσκονται ακριβώς στην ίδια διεύθυνση. Στο παραπάνω παράδειγμα, αρκεί μία απλή έκδοση αυτής της ανάλυσης, αφού οι αναφορές βρίσκονται στο ίδιο βασικό μπλοκ.

Σε πολλούς παράλληλους βρόχους ο βαθμός της παραλληλίας περιορίζεται μόνο από τον αριθμό των αναπτύξεων, ο οποίος περιορίζεται μόνο από τον αριθμό των επαναλήψεων του βρόχου. Βέβαια, στην πράξη, η εκμετάλλευση της παραλληλίας θα απαιτούσε πολλές λειτουργικές μονάδες και πιθανόν ένα τεράστιο αριθμό καταχωρητών. Η απουσία εξάρτησης που μεταφέρεται με το βρόχο, απλά δηλώνει ότι έχουμε διαθέσιμο ένα μεγάλο βαθμό παραλληλίας.

Συχνά οι εξαρτήσεις που μεταφέρονται με τον βρόχο εμφανίζονται στη μορφή μιας αναδρομής :

for ( i = 2 ; i 100 ; i = i+1) {
Υ[i] = Υ[i-1] + Y[i];      }


Μία αναδρομή συμβαίνει όταν, μία μεταβλητή υπολογίζεται από την τιμή της από προηγούμενη επανάληψη και συχνά από την αμέσως προηγούμενη. Η ανίχνευση των αναδρομών είναι σημαντική γιατί ένα πλήθος αναδρομών μπορεί να αποτελέσει την πηγή για μια λογική ποσότητα παραλληλίας. Αυτό φαίνεται από το παρακάτω παράδειγμα.

Παράδειγμα

Θεωρήστε τον παρακάτω βρόχο :

for ( i = 6 ; i 100 ; i = i+1) {
Υ[i] = Υ[i-5] + Υ[i];     }


Στην επανάληψη i, ο βρόχος αναφέρεται στο στοιχείο i-5. Λέμε ότι ο βρόχος έχει απόσταση εξάρτησης ίση με 5. Πολλοί βρόχοι με εξαρτήσεις που μεταφέρονται έχουν απόσταση εξάρτησης ίση με 1. Όσο μεγαλύτερη είναι η απόσταση, τόσο περισσότερος ενδεχόμενος παραλληλισμός μπορεί να επιτευχθεί με την ανάπτυξη του βρόχου. Για παράδειγμα, εάν αναπτύξουμε τον πρώτο βρόχο, με απόσταση εξάρτησης ίση με 1, τότε διαδοχικές εντολές αλληλοεξαρτώνται. Υπάρχει ακόμα παραλληλία ανάμεσα στις μεμονωμένες εντολές, αλλά όχι αρκετή. Εάν αναπτύξουμε τον βρόχο που έχει απόσταση εξάρτησης ίση με 5, υπάρχει μία ακολουθία πέντε εντολών που δεν έχουν εξαρτήσεις και έτσι υπάρχει περισσότερη παραλληλία σε επίπεδο εντολής. Αν και πολλοί βρόχοι με εξαρτήσεις μεταφερόμενες από τους βρόχους έχουν απόσταση εξάρτησης ίση με 1, προκύπτουν περιπτώσεις βρόχων με μεγαλύτερες αποστάσεις που παρέχουν αρκετή παραλληλία ώστε να κρατήσουν τον επεξεργαστή απασχολημένο.

Όλοι οι αλγόριθμοι ανάλυσης εξάρτησης δουλεύουν με την προϋπόθεση ότι οι δείκτες του πίνακα είναι συγγενικοί. Ο δείκτης ενός μονοδιάστατου πίνακα είναι συγγενικός όταν έχει τη μορφή a * i + b, όπου a και b σταθερές και i μεταβλητή δείκτη βρόχου.
Υποθέτουμε ότι αποθηκεύουμε σε ένα στοιχείο του πίνακα με δείκτη a * i + b και φορτώνουμε από τον ίδιο πίνακα με δείκτη c * i + d, όπου i είναι η μεταβλητή που παίρνει τιμή από m έως n. Μία εξάρτηση υπάρχει εάν ισχύουν δύο συνθήκες :

  1. Υπάρχουν δύο δείκτες επανάληψης, j και k, με m j και k n.
  2. Ο βρόχος αποθηκεύει σε ένα στοιχείο του πίνακα με δείκτη a * j + b και αργότερα ανακαλεί το ίδιο στοιχείο του πίνακα όταν αυτό έχει δείκτη c * k + d. Αυτό σημαίνει ότι a * j +b = c * k + d.

Μία απλή και επαρκής εξέταση για την απουσία εξάρτησης είναι ο μέγιστος κοινός διαιρέτης (GCD). Βασίζεται στην παρατήρηση ότι, εάν υπάρχει εξάρτηση μεταφερόμενη με τον βρόχο, τότε ο μέγιστος κοινός διαιρέτης των (c,a) πρέπει να διαιρεί το (d-b).

Παράδειγμα

Χρησιμοποιήστε το μέγιστο κοινό διαιρέτη για να καθορίσετε αν υπάρχουν εξαρτήσεις στον ακόλουθο βρόχο :

for ( i = 1 ; i 100 ; i = i+1) {
Χ[2*i+3] = Χ[2*i] * 5.0 ;     }


Δίνοντας τις τιμές a=2, b=3, c=2 και d=0, τότε GCD (a,c)=2 και d-b= -3. Αφού το 2 δεν διαιρεί το –3, καμία εξάρτηση δεν είναι πιθανή.

Για να χρησιμοποιηθεί ο μέγιστος κοινός διαιρέτης, ο βρόχος θα πρέπει πρώτα να κανονικοποιήσουμε το βρόχο, δηλαδή να γραφτεί έτσι ώστε ο δείκτης να αρχίζει από ένα και να αυξάνεται κατά ένα σε κάθε επανάληψη.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 2

Να χρησιμοποιήστε το μέγιστο κοινό διαιρέτη για να καθορίσετε αν υπάρχουν εξαρτήσεις στον ακόλουθο βρόχο:

for (i=2 ; i 1000 ; i+=2){
a[i]=a[i+2];     }


 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 2



ΔΡΑΣΤΗΡΙΟΤΗΤΑ 3

Να χρησιμοποιήστε το μέγιστο κοινό διαιρέτη για να καθορίσετε αν υπάρχουν εξαρτήσεις στον ακόλουθο βρόχο:

for (i=2 ; i 1000 ; i+=2){
a[i]=a[50*i+1];     }


 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 3



Υπάρχουν περιπτώσεις όπου ο μέγιστος κοινός διαιρέτης αν και είναι επιτυχής δεν υπάρχουν εξαρτήσεις. Αυτό συμβαίνει, για παράδειγμα, όταν ο μέγιστος κοινός διαιρέτης δεν λαμβάνει υπόψη του τα όρια του βρόχου.

Παράδειγμα

Θεωρήστε τον παρακάτω βρόχο :

for ( i = 1 ; i 100 ; i = i+1) {
Υ[i] = X[i] / c ; /*S1*/
X[i] = X[i] + c; /*S2*/
Z[i] = Y[i] + c; /*S3*/
Υ[i] = c - Y[i] ; /*S4*/ }

Βρείτε όλες τις πραγματικές εξαρτήσεις, τις εξαρτήσεις εξόδου και τις αντι-εξαρτήσεις. Εξαλείψτε τις εξαρτήσεις εξόδου και τις αντι-εξαρτήσεις με χρήση της μεθόδου της μετονομασίας.

Ανάμεσα στις τέσσερις εντολές του βρόχου υπάρχουν οι ακόλουθες εξαρτήσεις :

  1. Υπάρχουν πραγματικές εξαρτήσεις μεταξύ των εντολών S1 και S3 και μεταξύ των S1 και S4, λόγω του Υ[i]. Αυτές δεν είναι εξαρτήσεις που μεταφέρονται με τον βρόχο και επομένως πολλαπλές επαναλήψεις του βρόχου μπορούν να εκτελεστούν παράλληλα. Οι εξαρτήσεις αυτές αναγκάζουν τις εντολές S3 και S4 να περιμένουν την ολοκλήρωση της εντολής S1.
  2. Υπάρχει μία αντι-εξάρτηση μεταξύ των εντολών S1 και S2 λόγω του X[i].
  3. Υπάρχει μία αντι-εξάρτηση μεταξύ των εντολών S3 και S4 λόγω του Υ[i].
  4. Υπάρχει μία εξάρτηση εξόδου μεταξύ των εντολών S1 και S4 λόγω του Υ[i].

Η παρακάτω εκδοχή του βρόχου εξαλείφει τις εξαρτήσεις αυτές :

for ( i = 1 ; i 100 ; i = i+1) {
T[i] = X[i] / c ; /*S1*/
X1[i] = X[i] + c; /*S2*/
Z[i] = T[i] + c; /*S3*/
Υ[i] = c - T[i] ; /*S4*/ }

Στην εντολή S1 ο Υ μετονομάστηκε σε T με σκοπό τη μετακίνηση της εξάρτησης εξόδου. Στην εντολή S2 ο X μετονομάστηκε σε X1 με σκοπό τη μετακίνηση της αντι-εξάρτησης. Στις εντολές S3 και S4 ο Υ μετονομάστηκε σε T με σκοπό τη μετακίνηση της αντι-εξάρτησης.