Next              Up                Back                    Contents

Επόμενο:6.6 Διάδοση και Συλλογή Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.4 Φράγμα Δυαδικού Δένδρου


 

6.5 Τοπικός Συγχρονισμός

 

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

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

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


(*Υπολογισμός του μέσου όρου των τεσσάρων γειτονικών σημείων*)


For j:=1 to h do 


    B[i,j] := (A[i-1,j]+A[i+1,j]+A[i,j-1]+A[i,j+1]) / 4;

Η μεταβλητή i είναι ο μετρητής της FORALL και χρησιμοποιείται από κάθε διεργασία σαν δείκτης γραμμής του πίνακα. Ο παραπάνω βρόχος υπολογίζει τις νέες τιμές για κάθε i γραμμή αφήνοντας τον μετρητή j του βρόχου να παίρνει τιμές από τα αριστερά προς τα δεξιά κατά μήκος της γραμμής. Πρέπει να παρατηρήσουμε ότι οι μόνοι δείκτες του πίνακα που εμφανίζονται στον βρόχο είναι οι i, i+1 και i-1. Με αυτόν τον τρόπο σε κάθε επανάληψη η διεργασία i χρησιμοποιεί τιμές από τη δική της σειρά και τις άμεσα πάνω και κάτω γειτονικές της. Όταν οι διεργασίες i+1 και i-1 έχουν τελειώσει την προηγούμενη επανάληψή τους, η διεργασία μπορεί να προχωρήσει με τους υπολογισμούς της σειράς i. Έτσι, στο παράλληλο πρόγραμμα Jacobi ο τοπικός συγχρονισμός φράγματος μπορεί να αντικατασταθεί με έναν τοπικό συγχρονισμό, στον οποίο κάθε διεργασία συγχρονίζεται μόνο με τους δύο άμεσους γείτονες της.

Δυο οποιεσδήποτε διεργασίες Α και Β μπορούν να συγχρονιστούν με οποιεσδήποτε άλλες απλά με το να ανταλλάσσουν μηνύματα: η διεργασία Α στέλνει ένα μήνυμα στη διεργασία Β και η διεργασία Β στέλνει μήνυμα στην Α. Για την υλοποίηση αυτής της ανταλλαγής μηνυμάτων στο πρόγραμμα Jacobi σε κάθε διεργασία ανατίθονται δύο κανάλια που ονομάζονται higher και lower. Το κανάλι higher λαμβάνει μηνύματα από την γειτονική διεργασία της οποίας ο αριθμός είναι ο μεγαλύτερος και το κανάλι lower λαμβάνει μηνύματα από την γειτονική διεργασία που έχει τον μικρότερο αριθμό. Αυτά τα κανάλια δομούνται σε δυο πίνακες με τις τιμές higher[i] και lower[i] να αντιστοιχούν στη διεργασία i. Για το συγχρονισμό των χαμηλότερων και μεγαλύτερων γειτόνων κάθε διεργασία i πρώτα στέλνει μηνύματα και στους δυο γείτονες της και μετά διαβάζει τα μηνύματα με τον ακόλουθο τρόπο :

 

higher[i-1] := 1; (*Αποστολή μηνύματος στη διεργασία i-1*)


lower[i+1] := 1; (*Αποστολή μηνύματος στη διεργασία i+1*)


dummy := lower[i]; (*Λήψη μηνύματος από τη διεργασία i-1*)


dummy := higher[i];(*Λήψη μηνύματος από τη διεργασία i+1*)

 

Εφόσον κάθε διεργασία λαμβάνει το μήνυμα της γειτονικής της με το μεγαλύτερο αριθμό στο κανάλι higher η διεργασία i πρέπει να γράψει στο higher[i-1] όταν στέλνει ένα μήνυμα στη διεργασία i-1. Όμοια η διεργασία i πρέπει να γράψει στο κανάλι lower[i+1] όταν στέλνει ένα μήνυμα στην i+1. Τα ονόματα higher και lower δηλώνουν την πηγή του μηνύματος. Είναι σημαντικό οι διεργασίες να στείλουν πρώτα μήνυμα πριν να λάβουν. Εφόσον όλες οι διεργασίες εκτελούν τον ίδιο κώδικα αν κάποια προσπαθήσει να λάβει πριν να στείλει θα υπάρξει αδιέξοδο. Είναι επίσης σημαντικό να στείλει μια διεργασία και στις δυο γειτονικές της πριν να λάβει από κάποια από αυτές. Η ανταλλαγή μηνυμάτων με τον έναν γείτονα και μετά με τον άλλο μπορεί στην πραγματικότητα να οδηγήσει σε έναν γενικευμένο συγχρονισμού. Με αυτό το θέμα ασχολείται μια από τις ασκήσεις του κεφαλαίου.

Κάποια επιπλέον στοιχεία στην ανταλλαγή μηνυμάτων είναι απαραίτητα για να μπορέσουν να ληφθούν υπόψη οι οριακές συνθήκες. Οι διεργασίες που αναλαμβάνουν τις γραμμές από 1 εως n έχουν μόνο μια γειτονική. Η συνολική τεχνική τοπικού συγχρονισμού φαίνεται στη διαδικασία LocalBarrier στο σχήμα 6.11. Κάθε διεργασία πρώτα εξετάζει αν όντως υπάρχει η συγκεκριμένη γειτονική της πριν επιχειρήσει την ανταλλαγή μηνυμάτων με αυτή. Το πρόγραμμα 6.11 δίνει το συνολικό παράλληλο πρόγραμμα Jacobi. Κάθε διεργασία πραγματοποιεί τον τοπικό της συγχρονισμό καλώντας τη διαδικασία LocalBarrier. Αυτό επιτυγχάνεται με τις ίδιες δύο θέσεις διεργασίας που γινόταν και στον καθολικό συγχρονισμό φράγματος. Σε αυτή τη νέα έκδοση ο χρόνος εκτέλεσης για τη διαδικασία LocalBarrier είναι μια μικρή σταθερά που δεν εξαρτάται από το συνολικό αριθμό των διεργασιών.

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

PROGRAM JacobiBarrier;


CONST n = 32;


     numiter = ...;

 

VAR a, b : Array [0..n+1,0..n+1] of Real;


    i, j : Integer;


    higher, lower : Array [1..n] of Channel of Integer;

 

Procedure LocalBarrier (I: Integer);


VAR dummy : Integer;

 

BEGIN


    If i › 1 then higher[i-1] := 1; (*Αποστολή στη διεργασία I-1*)

    If i ‹ n then 

        BEGIN

            lower[i+1] := 1; (*Αποστολή στη διεργασία I+1*)

            dummy := higher[i]; (*Λήψη από τη διεργασία I+1*)

        END;

    If i › 1 then dummy := lower[i]; (*Λήψη από τη διεργασία I-1*)

END;

 

BEGIN (*Κυρίως πρόγραμμα*)

    ... 

 
    B := A;

    FORALL i := 1 to n do (*Δημιουργία μιας διεργασία για κάθε γραμμή*)

        VAR j, k : Integer;

            BEGIN

                For k := 1 to numiter do

                    BEGIN

                For j := 1 to n do (*Υπολογισμός του μέσου όρου για τους τέσσερις γείτονες*)
				
                    B[i,j] := (A[i-1,j]+A[i+1,j]+A[i,j-1]+A[i,j+1])/4;

                LocalBarrier(i);

                A[i] := B[i];

                LocalBarrier(i);

                    END;

            END;

END.

ΣΧΗΜΑ 6.11 Αλγόριθμος Jacobi με τοπικό συγχρονισμό

 

Χρησιμοποιώντας τη χρονομέτρηση του συστήματος της Multi-Pascal προκύπτει ότι η διαδικασία LocalBarrier απαιτεί 60 σταθερές μονάδες χρόνου για να υλοποιηθεί ο τοπικός συγχρονισμός. Για μεγαλύτερο αριθμό διεργασιών αυτό μπορεί να έχει ως αποτέλεσμα τη μείωση ενός σημαντικού τμήματος χρόνου σε σχέση με καθολικές μεθόδους φράγματος, που έχουν O(n) ή O(logn). Το παράλληλο πρόγραμμα Jacobi του σχήματος 6.11 με τις 32 διεργασίες απαιτεί 1579 μονάδες χρόνου για κάθε επανάληψη, ενώ η καλύτερη καθολική υλοποίηση φράγματος απαιτεί 2191. Έτσι, αυτός ο τοπικός συγχρονισμός έχει μειώσει το συνολικό χρόνο εκτέλεσης του προγράμματος κατά 27%. Για μεγαλύτερο αριθμό διεργασιών η μείωση του χρόνου θα είναι ακόμα μεγαλύτερη.

Για να συνοψίσει τη σχετική απόδοση των τριών εφαρμογών φράγματος που παρουσιάστηκαν στο κεφάλαιο, το σχήμα 6.12 δείχνει την επιτάχυνση που επιτυγχάνεται από κάθε μέθοδο για διάφορες τιμές του n. Η επιτάχυνση υπολογίστηκε πρώτα εκτελώντας το ακολουθιακό πρόγραμμα Jacobi του σχήματος 6.3 για κάθε τιμή του n, έτσι ώστε να υπολογιστεί ο μέσος όρος του χρόνου εκτέλεσης ανά επανάληψη. Μετά ο χρόνος εκτέλεσης ανά επανάληψη για κάθεμια από τις τρεις μεθόδους διαιρέθηκε με τον ακολουθιακό χρόνο για τον καθορισμό της επιτάχυνσης. Όπως ήταν αναμενόμενο η μέθοδος του τοπικού συγχρονισμού είναι η καλύτερη για όλες τις τιμές του n. Συγκρίνοντας τις δύο καθολικές μεθόδους βρίσκουμε ότι η μέθοδος Κεντρικού Αθροιστή είναι καλύτερη για n<20 και η μέθοδος Δυαδικού Δένδρου είναι καλύτερη για n>20. Αυτό το σημείο τομής για τις δύο καθολικές μεθόδους ποικίλει σε διαφορετικά συστήματα πολυεπεξεργαστών και εξαρτάται από τους σχετικούς χρόνους εκτέλεσης των εντολών που χρησιμοποιούνται στις εφαρμογές τους.

 

image

ΣΧΗΜΑ 6.12 Σχετική απόδοση των εφαρμογών φράγματος


     Next              Up                Back                    Contents

Επόμενο: 6.6 Διάδοση και Συλλογή Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.4 Φράγμα Δυαδικού Δένδρου