Επόμενο:6.5 Τοπικός Συγχρονισμός Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.3 Γραμμικό Φράγμα
6.4 Φράγμα Δυαδικού Δένδρου
Μέχρι στιγμής έχουμε παρουσιάσει δύο τεχνικές συγχρονισμού που έχουν και οι δύο γραμμική πολυπλοκότητα χρόνου: η μέθοδος τερματισμού των διεργασιών και η υλοποίηση φράγματος που στηρίζεται σε μια μεταβλητή αθροιστή. Και στις δυο μεθόδους η γραμμική συμπεριφορά είναι αποτέλεσμα του ότι μια μόνο συγκεντρωτική μεταβλητή χρησιμοποιείται για τον συντονισμό του συγχρονισμού. Αυτή η συγκεντρωτική μεταβλητή πρέπει να χειριστεί κάθε μία από τις n διεργασίες ξεχωριστά έστω και για ένα μικρό χρονικό διάστημα. Έτσι, ο συνολικός χρόνος που απαιτείται για το συγχρονισμό είναι πάντα Ο(n).
Τα σημεία συμφόρησης, που προκαλούνται από τη συγκεντρωτική μεταβλητή, όσον αφορά την απόδοση είναι άλλο ένα παράδειγμα του γενικού προβλήματος του ανταγωνισμού για διαμοιραζόμενες πηγές σε ένα παράλληλο σύστημα. Στο παρελθόν έχουμε δει ότι ο ανταγωνισμός μπορεί να μειωθεί μέσα από την αποκέντρωση. Στην περίπτωση του συγχρονισμού η αποκέντρωση μπορεί να επιτευχθεί επιτρέποντας στις διεργασίες που φτάνουν στο φράγμα να συγχρονίζονται μεταξύ τους σε μικρές ομάδες και στη συνέχεια όλες οι ομάδες να συγκεντρώνονται ιεραρχικά. Όταν μια τέτοια τεχνική αποκέντρωσης εφαρμόζεται πολυεπίπεδα το αποτέλεσμα είναι μια δομή δένδρου. Ένα δέντρο είναι συγκεντρωτικό και αποκεντρωτικό ταυτόχρονα: αποκεντρώνεται στα φύλλα και συγκεντρώνεται στη ρίζα. Με τον τρόπο αυτό η δενδρική δομή παρέχει τη δυνατότητα πραγματοποίησης μια συγκεντρωτικής δραστηριότητας με αποκεντρωμένο αλλά ιεραρχικό τρόπο.
6.4.1 Τεχνική Τουρνουά
Με τη δημιουργία ενός δυαδικού δένδρου συγχρονισμού για τις διεργασίες που φτάνουν στο φράγμα, ο χρόνος εκτέλεσης μπορεί να μειωθεί στο Ο(logn) - να γίνει δηλαδή ανάλογος του λογαρίθμου του αριθμού των διεργασιών. Η τεχνική που χρησιμοποιείται ονομάζεται μερικές φορές τεχνική τουρνουά. Σε ένα τουρνουά όλοι οι παίκτες εισέρχονται στον πρώτο γύρο και σχηματίζουν ζευγάρια. Ο νικητής κάθε ζευγαριού πηγαίνει να παίξει στον επόμενο γύρο, όπου όλοι οι νικητές δημιουργούν και πάλι ζευγάρια. Μετά από κάθε γύρο ο συνολικός αριθμός των παικτών μειώνεται στο μισό, μέχρι τελικά να μείνει μόνο ένας νικητής. Η τεχνική τουρνουά δημιουργεί μια δομή δυαδικού δένδρου με όλους τους αρχικούς παίκτες στα φύλλα και τον τελικό νικητή στην ρίζα.
Η τεχνική τουρνουά μπορεί να εφαρμοστεί για τη δημιουργία ενός φράγματος συγχρονισμού για μια ομάδα n διεργασιών. Κάθε διεργασία έχει το δικό της κανάλι για τη λήψη των μηνυμάτων των άλλων διεργασιών. Σε κάθε στάδιο του πρωταθλήματος η διεργασία παίζει και επιλέγει έναν νικητή από κάποιο άλλο ζευγάρι, στέλνοντας μηνύματα. Για να μπορέσετε να αντιληφθείτε αυτή τη μέθοδο φανταστείτε ότι όλες οι διεργασίες έχουν φτάσει στο φράγμα και έχουν αριθμηθεί από το 0 ως το n-1. Το ζευγάρωμα των διεργασιών και η επιλογή των νικητών γίνεται με τη χρήση της δυαδικής μορφής των αριθμών των διεργασιών. Κατά τη διάρκεια του πρώτου γύρου κάθε διεργασία επιλέγει τον αντίπαλό της αντιστρέφοντας το ακροδεξιό bit του δικού της αριθμού. Έτσι, η διεργασία με τον αριθμό 000 θα ζευγαρώσει με την 001, η διεργασία 010 με την 011, η διεργασία 100 με την 101 κ.τ.λ. Ο νικητής κάθε ζευγαριού είναι απλά η διεργασία που έχει 0 στη δεξιά θέση του αριθμού της, δηλαδή οι νικητές είναι οι 000, 010, 100 κ.τ.λ. Κάθε διεργασία που χάνει για να δηλώσει την ήττα της στέλνει ένα μήνυμα στο νικητή αντίπαλό της.
Όλες οι n/2 διεργασίες τώρα συνεχίζουν στον επόμενο γύρο του παιχνιδιού. Εφόσον είναι νικητές του προηγούμενου γύρου έχουν όλοι 0 στη δεξιά θέση του αριθμού τους. Σε αυτό το δεύτερο γύρο το ζευγάρωμα και η επιλογή των νικητών γίνεται χρησιμοποιώντας το δεύτερο bit από τα δεξιά του αριθμού της διεργασίας. Πάλι, οι διεργασίες επιλέγουν τον αντίπαλό τους αντιστρέφοντας το δεύτερο bit και ο νικητής είναι αυτός που έχει 0. Οι διεργασίες που έχουν χάσει δηλώνουν ξανά την ήττα τους στέλνοντας ένα μήνυμα στον νικητή. Στη συνέχεια όλοι οι n/4 νικητές του δεύτερου γύρου συνεχίζουν προς τον τρίτο γύρο. Για τον τρίτο γύρο χρησιμοποιείται το επόμενο bit του αριθμού των διεργασιών. Γενικά μετά από logn γύρους θα παραμείνει μια διεργασία νικητής, της οποίας ο αριθμός θα είναι 0.
Το σχήμα 6.8 δείχνει ένα διάγραμμα του τουρνουά για 8 διεργασίες, με αριθμούς από το 0 ως το 7. Οι κυματοειδείς, διαγώνιες γραμμές αναπαριστάνουν την αποστολή μηνυμάτων των διεργασιών που έχουν χάσει και οι ευθείες γραμμές την λήψη μηνυμάτων από τς νικήτριες. Η δυαδική δομή είναι φανερή σε αυτό το σχήμα. Για τις n διεργασίες ο αριθμός των επιπέδων στο δέντρο είναι logn. Ένα σημαντικό θέμα που αφορά το δέντρο είναι ότι κάθε διεργασία συμμετέχει τουλάχιστον μια φορά στην ολοκλήρωση της δομής του. Έτσι, η διεργασία 0 μπορεί να φτάσει τη ρίζα του δένδρου μόνο μετά την άφιξη όλων των διεργασιών στο φράγμα. Αν κάποιες διεργασίες φτάσουν αργοπορημένες στο φράγμα, τότε το δένδρο θα καθυστερήσει σε κάποιο επίπεδο περιμένοντας ένα μήνυμα από τις αργοπορημένες διεργασίες.
ΣΧΗΜΑ 6.8 Συγχρονισμός δυαδικού δένδρου
6.4.2 Αλγόριθμος δημιουργίας του δένδρου
Το δυαδικό σχήμα αρίθμησης προτείνει έναν πολύ απλό αλγόριθμο για τη δημιουργία του δένδρου. Κάθε διεργασία ελέγχει τα bits της από δεξιά προς τα αριστερά. Αν το bit είναι 1 το αντιστρέφει για να πάρει το bit που έχει ο αντίπαλός της και στέλνει σε αυτόν ένα μήνυμα. Όμως, αν το bit είναι 0 τότε περιμένει μήνυμα από τον αντίπαλό της. Μετά τη λήψη του μηνύματος προχωράει στον επόμενο γύρο ελέγχοντας το επόμενο bit από τα αριστερά. Για τη μοντελοποίηση του αλγορίθμου χρειάζονται δυο ειδικές συναρτήσεις για να εργαστούμε πάνω στις θέσεις του δυαδικού bit :
Bit(i,p) - δίνει την τιμή της p θέσης του bit στον αριθμό i. (Οι θέσεις των bits είναι αριθμημένες σε αύξουσα τάξη από δεξιά προς τα αριστερά και με αριθμούς πολλαπλάσια του 2).
ClearBit(i,p) - επιστρέφει τον αριθμό που αποκτήθηκε με την αλλαγή της p θέσης του bit με τους αριθμούς i από 1 ως 0.
Από δεξιά προς τα αριστερά οι p θέσεις του bit αριθμούνται με τους 1, 2, 4, 8, 16 κ.τ.λ, δηλαδή εξετάζει τα πολλαπλάσια του 2 όπως είπαμε και πριν. Η συνάρτηση Bit(i,p) χρησιμοποιείται για bits της κάθε διεργασίας κατά τη διάρκεια των διαδοχικών γύρων. Εισάγοντας την συνάρτηση σε ένα βρόχο που διπλασιάζει το p, εξετάζουμε διαδοχικά το ένα bit μετά το άλλο. Η συνάρτηση ClearBit(i,p) χρησιμοποιείται από τις διεργασίες που έχουν χάσει, για να καθορίσουν τον αριθμό διεργασίας του αντιπάλου της που είναι και ο νικητής. Με την εκτέλεση αυτού του απλού αλγόριθμου από όλες τις διεργασίες χρησιμοποιώντας τους προσωπικούς τους αριθμούς mynumber, δημιουργείται το παρακάτω δυαδικό δένδρο συγχρονισμού :
position := 1;
While (Bit(mynumber, position) = 0) AND (position ‹ n) Do BEGIN Receive message from lossing partner ; position := position * 2; END; If mynumber ‹› 0 then BEGIN WinningPartner := ClearBit(mynumber, position); Send message for WinningPartner; Wait for reply message; END;
Αυτός ο απλός αλγόριθμος δημιουργεί το δυαδικό δένδρο συγχρονισμού. H ρίζα του δένδρου που δημιουργείται από τη διεργασία 0, η οποία είναι μοναδική από την άποψη ότι είναι πάντα ο νικητής. Σε κάθε υλοποίηση φράγματος είναι απαραίτητο να έχουμε όλες τις διεργασίες σε αναμονή μέσα στο φράγμα μέχρι να φτάσουν όλες οι υπόλοιπες καθυστερημένες διεργασίες. Αυτός ο περιορισμός στο δυαδικό δένδρο επιτυγχάνεται με την καθυστέρηση κάθε διεργασίας που χάνει. Με αυτόν τον τρόπο, καθώς το δένδρο ανεβαίνει προς τη ρίζα όλες οι διεργασίες που έχουν χάσει παραμένουν σε κατάσταση αναμονής στα χαμηλότερα επίπεδα του δένδρου. Τελικά, κάθε διεργασία θα χάσει - εκτός φυσικά από τη διεργασία 0. Έτσι, όταν η διεργασία 0 λάβει όλα τα απαιτούμενα μηνύματα από τους αντιπάλους της που έχουν χάσει, αυτόματα αυτό σημαίνει ότι όλες οι άλλες διεργασίες βρίσκονται σε κατάσταση αναμονής σε κάποιο από τα χαμηλότερα επίπεδα του δένδρου.
Για την απελευθέρωση όλων των εγκλωβισμένων διεργασιών, η διαδικασία δημιουργίας του δένδρου θα αντιστραφεί από πάνω - δηλαδή από τη ρίζα - προς τα κάτω. Στην καθοδική πορεία, οι διεργασίες νικητές θα κατευθύνονται προς τα κάτω στο δένδρο και θα στέλνουν μηνύματα στις χαμένες, που περιμένουν σε κάθε επίπεδο του δένδρου. Αυτή όλη η διαδικασία φαίνεται στο σχήμα 6.9.
ΣΧΗΜΑ 6.9 Απελευθέρωση των διεργασιών σε αναμονή από το φράγμα
Καθώς κάθε χαμένη διεργασία λαμβάνει ένα μήνυμα και “ξυπνάει” υποθέτει ότι έχει το ρόλο του νικητή και κατευθύνεται προς το πιο κάτω επίπεδο για να ξυπνήσει τις άλλες χαμένες διεργασίες που ήταν αντίπαλοί της. Για παράδειγμα, στη διαδικασία δημιουργίας του δένδρου η διεργασία 100 έχασε από την 000 και συνεπώς στο κατέβασμα του δένδρου λαμβάνει ένα μήνυμα από τη διεργασία 000. Στη συνέχεια η 100 κατεβαίνει στο επόμενο επίπεδο του δένδρου και στέλνει μήνυμα στην 110, η οποία ήταν ο αντίπαλός της που είχε χάσει σε αυτό το επίπεδο.
Ο αλγόριθμος για τη δημιουργία αυτού του καθοδικού δένδρου είναι παρόμοιος με τον προηγούμενο. Για την επίτευξη αυτής της καθοδικής πορείας του δένδρου οι θέσεις των bits εξετάζονται από αριστερά προς τα δεξιά. Έτσι, η μεταβλητή position αρχίζει με μια μέγιστη τιμή και στη συνέχεια κάθε φορά μέσα στον βρόχο διαιρείται με το 2. Η άλλη σημαντική διαφορά είναι ότι η διεργασία νικητής πρέπει να υπολογίσει τον αριθμό των διεργασιών που έχουν χάσει και ήταν ταίρια της σε κάθε επίπεδο και να τους στείλει μηνύματα. Για αυτό το σκοπό χρειάζεται μια νέα συνάρτηση :
SetBit(i,p) - επιστρέφει τον αριθμό που αποκτήθηκε με την αλλαγή της p θέσης του bit από τους αριθμούς I από 0 ως 1.
Ο παρακάτω αλγόριθμος δημιουργεί το καθοδικό δένδρο και ελευθερώνει όλες τις διεργασίες που βρίσκονται σε αναμονή στο φράγμα :
(*Η μεταβλητή position λαμβάνει μια μέγιστη τιμή από τον αλγόριθμο που τη δημιουργεί*)
While position > 1 do BEGIN position := position DIV 2; LosingPartner := SetBit(mynumber, position); Send message to LosingPartner; END;
6.4.3 Απόδοση
Οι δύο αλγόριθμοι δημιουργίας των δύο φάσεων συγχρονισμού του δυαδικού δένδρου μπορούν να συνδυαστούν σε μια διαδικασία της Multi-Pascal για την υλοποίηση του φράγματος. Οι τρεις ειδικές συναρτήσεις Bit, ClearBit και SetBit υλοποιούνται από την Multi-Pascal με τον τρόπο που φαίνεται παρακάτω:
Bit(i,p): i DIV p MOD 2
ClearBit(i,p): i - p
SetBit(i,p): i + p
Όλη η διαδικασία φράγματος φαίνεται στο σχήμα 6.10 ως περιεχόμενο του προγράμματος Jacobi. Ένας πίνακας από κανάλια synchan χρησιμοποιείται για να δώσει σε κάθε διεργασία το δικό της κανάλι για να λαμβάνει τα εισερχόμενα μηνύματα. Όταν οι διεργασίες καλούν τη διαδικασία Barrier περνούν τις τιμές δεικτοδότησης FORALL ως παράμετρο. Μέσα στη διαδικασία Barrier αυτό δημιουργεί έναν μοναδικό αριθμό me και ένα μοναδικό κανάλι synchan[me] για κάθε διεργασία. Η όλη ιδέα του δυαδικού δένδρου συγχρονισμού είναι ιδιαίτερα απλή και ο αλγόριθμος δημιουργίας του δένδρου περιλαμβάνει μόνο λίγες εντολές. Όμως, η δυναμική συμπεριφορά του αλγορίθμου είναι ιδιαίτερα πολύπλοκη και μάλλον απαιτεί επιπλέον μελέτη από το χρήστη. Αρκετές από τις ασκήσεις του κεφαλαίου ασχολούνται με τον αλγόριθμο και βοηθούν στην αποσαφήνιση της συμπεριφοράς του.
Ο χρόνος εκτέλεσης για το δυαδικό δένδρο υλοποίησης φράγματος είναι πολυπλοκότητας O(logn), ενώ της προηγούμενης μεθόδου είναι O(n). Χρησιμοποιώντας τη χρονομέτρηση του συστήματος της Multi-Pascal έχουμε ότι ο πραγματικός χρόνος εκτέλεσης είναι 80 logn. Εξαιτίας αυτού του μεγάλου σταθερού πολλαπλασιαστή πρέπει να υπάρχουν περισσότερες από 16 διεργασίες για να λειτουργήσει καλύτερα αυτή η μέθοδος από την γραμμική. Ένας λόγος για τον μεγάλο πολλαπλασιαστή είναι η δυσκολία υλοποίησης λειτουργιών bit στην Pascal. Σε κάποιες άλλες γλώσσες προγραμματισμού, όπως είναι η C, υπάρχουν ξεχωριστές λειτουργίες χειρισμού των bits, οι οποίες είνια πιο αποδοτικές και καταλήγουν σε μικρότερους πολλαπλασιαστές. Επίσης, αν η ρουτίνα Barrier μπορεί να γραφεί στην γλώσσα assembly και να χρησιμοποιηθούν εντολές μηχανής για κάθε χειρισμό των bits, τότε ο πολλαπλασιαστής 80 θα μειωθεί αισθητά.
PROGRAM JacobiBarrier;
CONST n = 32; VAR .... synchan: Array [0..n-1] of Channel of Integer; Procedure Barrier(me: Integer); VAR position, dummy: Integer; BEGIN position := 1; While (me DIV position MOD 2 = 0) AND (position ‹ n) Do BEGIN dummy:=synchan[me]; (*Λήψη μηνύματος από τον αντίπαλο που έχει χάσει*) position := position * 2; END; If me ‹› 0 then BEGIN synchan[me-position] := 1; (*Διάδοση μηνύματος στη διεργασία νικητή*) dummy := synchan[me]; (*Αναμονή για απάντηση*) END; While position › 1 do BEGIN position := position DIV 2; synchan[me+position] := 1; (*Αποστολή μηνύματος στη διεργασία που είχε χάσει προηγουμένως*) END; END; BEGIN (*Κυρίως Πρόγραμμα*) .... FORALL I := 1 to n do (*Δημιουργία μιας διεργασίας για κάθε σειρά του πίνακα*) .... Barrier(i-1); .... Barrier(i-1); .... END.
ΣΧΗΜΑ 6.10 Εφαρμογή φράγματος με δυαδικό δένδρο.
Ένα σημαντικό στοιχείο της διαδικασίας φράγματος του σχήματος 6.10 είναι ότι δουλεύει μόνο αν το n είναι ακριβής δύναμη του 2. Μερικές μικρές μετατροπές στον αλγόριθμο μπορούν να γενικεύσουν τη λειτουργία του για κάθε τιμή του n. Το θέμα αυτό αντιμετωπίζεται στις ασκήσεις.
Αυτός ο δυναμικός αλγόριθμος δημιουργίας δένδρου είναι ιδιαίτερα σημαντικός στο χώρο του παράλληλου προγραμματισμού. Έχει πάρα πολλές άλλες εφαρμογές εκτός από το συγχρονισμό φράγματος. Όπως είδαμε προηγουμένως σε αυτό το κεφάλαιο, μπορεί να χρησιμοποιηθεί για τη μετάδοση δεδομένων σε μια ομάδα διεργασιών ή και να αθροίσει δεδομένα από διεργασίες. Ο αναγνώστης μπορεί ίσως να διακρίνει ότι μια παρόμοια τεχνική με την αντιστροφή του bit που χρησιμοποιήθηκε στη Διτονική Ταξινόμηση με Συγχώνευση (Bitonic Merge Sort) για το ζευγάρωμα επεξεργαστών με σκοπό την σύγκριση τους και την εξαγωγή των τιμών τους. Αυτή η δυναμική τεχνική δημιουργίας δένδρου μοιάζει επίσης με τις αρχές στις οποίες βασίζεται το δίκτυο πεταλούδας, ένα από τα σημαντικότερα δίκτυα διασύνδεσης επεξεργαστή-μνήμης, που παρουσιάστηκε στο 3ο κεφάλαιο.
Επόμενο:6.5 Τοπικός Συγχρονισμός Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.3 Γραμμικό Φράγμα