Επόμενο:6.7 Περίληψη Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.5 Τοπικός Συγχρονισμός
6.6 Διάδοση και Συλλογή
Οι μέθοδοι για την υλοποίηση φράγματος μπορούν να προσαρμοστούν και σε ένα νέο τύπο ενέργειας που είναι σημαντικός σε μερικούς παράλληλους αλγόριθμους: συλλογή των δεδομένων από τις διεργασίες και διάδοση των αποτελεσμάτων ξανά σε αυτές. Αυτή η ενέργεια της συλλογής και της διάδοσης των ενδιάμεσων αποτελεσμάτων δημιουργεί τη βάση για μια νέα κατηγορία παράλληλων αλγορίθμων που ονομάζεται Υπολογισμός, Συλλογή και Διάδοση (Compute, Aggregate και Broadcast - CAB). Οι αλγόριθμοι CAB είναι συνήθως επαναληπτικοί. Κάθε διεργασία περνά μια φάση υπολογισμού. Στη συνέχεια κάθε διεργασία δίνει κάποια δεδομένα στη φάση συλλογής κατά την οποία δημιουργούνται μερικές γενικές τιμές δεδομένων. Αυτά τα γενικά δεδομένα στέλνονται πίσω σε κάθε διεργασία στην φάση της διάδοσης. Αυτές οι φάσεις Υπολογισμού, Συλλογής και Διάδοσης επαναλαμβάνονται σε κάθε επανάληψη.
Για την κατανόηση τη μέθοδο οργάνωσης CAB θα αναπτύξουμε μια νέα έκδοση του αλγορίθμου Jacobi εισάγοντας έναν έλεγχο σύγκλισης μετά από κάθε επανάληψη.
6.6.1 Έλεγχος σύγκλισης
Σε όλες τις διαφορετικές εκδόσεις του προγράμματος Jacobi μέχρι στιγμής σε αυτό το κεφάλαιο, χρησιμοποιείται ένας σταθερός και προκαθορισμένος αριθμός επαναλήψεων που καθορίζεται με μια σταθερά στην αρχή του προγράμματος. Για τον αλγόριθμο Jacobi και επίσης για έναν μεγάλο αριθμό επαναληπτικών αλγορίθμων, είναι συνήθως δύσκολο να γνωρίζει κανείς εκ των προτέρων πόσες επαναλήψεις χρειάζονται. Όταν ο χρήστης λύνει τέτοιου είδους εφαρμογές στον υπολογιστή συνήθως έχει υπόψη του μια καθορισμένη και επιθυμητή ακρίβεια στην αριθμητική λύση. Στην περίπτωση αυτή το πρόγραμμα θα συνεχίζει τις επαναλήψεις μέχρι την επίτευξη αυτής της ακρίβειας. Ο αριθμός των επαναλήψεων δεν είναι προκαθορισμένος, αλλά εξαρτάται από το ρυθμό σύγκλισης των συγκεκριμένων δεδομένων που χρησιμοποιούνται σε κάθε εκτέλεση.
Στην περίπτωση του αλγορίθμου Jacobi η ακρίβεια της υπολογιζόμενης λύσης συνήθως καθορίζεται από το πόσες αλλαγές συμβαίνουν στις τιμές του πίνακα μετά από κάθε επανάληψη. Εμπειρικά κάποιος μπορεί να δει ότι αρχικά μετά από κάποιες επαναλήψεις συμβαίνουν μεγάλες αλλαγές στις τιμές διαφόρων σημείων. Καθώς η διαδικασία του υπολογισμού συνεχίζεται σταδιακά οι αλλαγές μειώνονται καθώς οι τιμές του πίνακα προσεγγίζουν κάποια λύση. Η συνήθης μέθοδος μέτρησης της ακρίβειας μετά από κάθε επανάληψη είναι η χρησιμοποίηση της μεγαλύτερης αλλαγής που συνέβηκε σε όλα τα στοιχεία του πίνακα κατά τη διάρκεια της δεδομένης επανάληψης. Οι επαναλήψεις θα συνεχιστούν μέχρι αυτή η μέγιστη αλλαγή να κατέβει κάτω από ένα κρίσιμο σημείο ανοχής που καθορίζεται από τον χρήστη. Για τον ακολουθιακό αλγόριθμο Jacobi η τεχνική αυτή φαίνεται στο σχήμα 6.13.
Ο εξωτερικός βρόχος στο πρόγραμμα είναι τώρα ένας βρόχος REPEAT και όχι FOR. Κατά τη διάρκεια κάθε επανάληψης υπολογίζεται μια νέα τιμή για κάθε σημείο και γράφεται στο B[i,j]. Η αλλαγή υπολογίζεται αφαιρώντας την παλιά τιμή A[i,j] από αυτή τη νέα τιμή. Καθώς οι σειρές και οι στήλες του πίνακα καλύπτονται από τους εσωτερικούς φωλιασμένους βρόχους, η μέγιστη αλλαγή αποθηκεύεται στην μεταβλητή maxchange. Στο τέλος κάθε επανάληψης η τιμή της maxchange συγκρίνεται με την επιθυμητή ανοχή για να ελέγξουμε αν είναι απαραίτητη και άλλη επανάληψη.
PROGRAM Jacobi;
CONST n = 32;
tolerance = .01;
VAR A, B : Array [0..n+1,0..n+1] of Real;
i,j : Integer;
change, maxchange : Real;
BEGIN
.... (*Ανάγνωση αρχικών τιμώω για τον πίνακα A*)
B := A;
REPEAT (*Υπολογισμός των νέων τιμών μέχρι να προσεγγιστεί η επιθυμητή ανοχή*)
BEGIN
maxchange := 0;
For i := 1 to n do
For j := 1 to n do
Begin (*Υπολογισμός των νέων τιμών και της αλλαγής τους από τις παλιές*)
B[i,j] := (A[i-1,j]+A[i+1,j]+A[i,j-1]+A[i,j+1]) / 4;
change := ABS(B[i,j] - A[i,j]);
If change > maxchange then
maxchange := change;
END;
A := B;
END;
Until maxchange < tolerance;
END.
ΣΧΗΜΑ 6.13 Ακολουθιακός αλγόριθμος Jacobi με έλεγχο σύγκλισης.
6.6.2 Εφαρμόζοντας παράλληλη συλλογή
Αυτή η τεχνική ελέγχου σύγκλισης μπορεί επίσης να εφαρμοστεί στην παράλληλη έκδοση του αλγορίθμου Jacobi. Στην βασική παράλληλη έκδοση του σχήματος 6.6 κάθε διεργασία έχει το δικό της βρόχο FOR για να μετρά τον προκαθορισμένο αριθμό των επαναλήψεων. Για να προσθέσουμε έναν έλεγχο σύγκλισης πρέπει ο βρόχος FOR να αντικατασταθεί με REPEAT για κάθε διεργασία που συνεχίζει τις επαναλήψεις μέχρι να επιτευχθεί η επιθυμητή ανοχή στη λύση. Κάθε διεργασία αναλαμβάνει και μια γραμμή του πίνακα και έτσι μπορεί να καθορίσει τις αλλαγές που συμβαίνουν στην γραμμή της μετά από κάθε επανάληψη. Όμως, ο έλεγχος σύγκλισης πρέπει να είναι καθολικός: οι αλλαγές που συμβαίνουν σε όλες τις σειρές του πίνακα πρέπει να λαμβάνονται υπόψη έτσι ώστε να καθορίζεται ο τερματισμός του αλγόριθμου. Οι αλλαγές κάθε γραμμής πρέπει να συλλέγονται σε γενικό επίπεδο μετά από κάθε επανάληψη και να ελέγχεται αν έχει επιτευχθεί η επιθυμητή ακρίβεια. Ακόμα και αν υπάρχει μόνο ένα σημείο σε όλον τον πίνακα που έχει σημειώσει μεγάλη αλλαγή σε μια δοσμένη επανάληψη θα προκαλέσει την συνέχιση της εκτέλεσης όλου του προγράμματος για αρκετές ακόμα επαναλήψεις.
Αυτή η καθολική συλλογή των αλλαγών που υπολογίζονται σε διάφορες διεργασίες πραγματοποιείται εύκολα με τη χρήση του φράγματος, που υπάρχει ήδη στο πρόγραμμα για τον σκοπό του συγχρονισμού. Οι υλοποιήσεις φράγματος για να συγχρονίσουν τις διεργασίες μετά από κάθε επανάληψη τις συλλέγουν και μετά τις αφήνουν όλες ελεύθερες. Κατά τη διάρκεια της φάσης συλλογής οι πληροφορίες των διεργασιών μπορούν να ομαδοποιηθούν και μετά να επιστρέψουν ή να διαδοθούν πίσω στις διεργασίες στη φάση που αφήνονται ελεύθερες.
Το σχήμα 6.13 δείχνει πως το κριτήριο τερματισμού είναι η αλλαγή σε όλα τα σημεία του πίνακα να είναι μικρότερη από μια δοσμένη ακρίβεια. Στην παράλληλη έκδοση, κάθε διεργασία μπορεί να ελέγξει αν οι αλλαγές της γραμμής της είναι μικρότερες από τη δοσμένη ανοχή. Αυτή η πληροφορία μπορεί να περαστεί στο φράγμα με τη μορφή μιας Boolean μεταβλητής, της mydone, η οποία είναι αληθής αν όλες οι αλλαγές στην εν λόγω σειρά είναι μικρότερες από την ανοχή. Αν όλες οι διεργασίες έχουν αληθή τιμή για την mydone μεταβλητή τους τότε όλες οι αλλαγές του πίνακα είναι μικρότερες από την επιθυμητή ανοχή και το πρόγραμμα πρέπει να σταματήσει. Για να συλλεχθούν όλες οι τιμές της mydone από όλες τις διεργασίες πρέπει κάθε διεργασία να περάσει την Boolean τιμή στο φράγμα. Καθώς το φράγμα πραγματοποιεί τον συγχρονισμό συλλέγει και αυτές τις Boolean τιμές. Αν όλες οι τιμές που έχουν συλλεχθεί είναι αληθείς τότε το φράγμα θα επιστρέψει σε κάθε διεργασία την τιμή αληθής για να σταματήσει η εκτέλεσή της.
Για την πραγματοποίηση της συλλογής και της διάδοσης η διαδικασία Barrier θα αντικατασταθεί με την συνάρτηση Aggregate (mydone), όπου mydone είναι η μεταβλητή Boolean που περιγράψαμε παραπάνω. Η συνάρτηση αυτή θα υλοποιήσει το συγχρονισμό φράγματος όπως και προηγουμένως, με τη διαφορά ότι θα συλλέξει όλες τις Boolean τιμές και θα διαδώσει το αποτέλεσμα σε όλες τις διεργασίες. Εφόσον η Aggregate είναι συνάρτηση μπορεί να επιστρέφει μια Boolean τιμή σε κάθε διεργασία που θα αναφέρει αν θα συνεχίσει ή όχι σε άλλη επανάληψη.
Όλες οι τεχνικές φράγματος που παρουσιάστηκαν πιο πριν στο κεφάλαιο μπορούν να υιοθετηθούν για το σκοπό αυτό. Έστω η μέθοδος του κεντρικού αθροιστή που παρουσιάστηκε αρχικά στο σχήμα 6.7. Καθώς κάθε διεργασία εισέρχεται στο φράγμα μπαίνει σε μια Φάση Άφιξης, κατά τη διάρκεια της οποίας η καθολική μεταβλητή count αυξάνεται. Καθώς οι διεργασίες περνούν στη Φάση Αναχώρησης μειώνουν την count και εξέρχονται από το φράγμα. Αυτή η μέθοδος μπορεί εύκολα να τροποποιηθεί για την συλλογή των τιμών της mydone από τις διεργασίες. Έχουμε τώρα μια νέα μεταβλητή, την globaldone. Καθώς κάθε διεργασία περνά από τη Φάση Άφιξης συγχωνεύει την τιμή της mydone στην τιμή της globaldone. Κατά τη διάρκεια της Φάσης Αναχώρησης αυτή η τιμή της globaldone επιστρέφεται σε κάθε διεργασία καθώς εξέρχεται.
Το σχήμα 6.14 δείχνει τη συνάρτηση Aggregate που βασίζεται στην μέθοδο του κεντρικού αθροιστή. Η συνάρτηση πραγματοποιεί ένα συγχρονισμό φράγματος για όλες τις n διεργασίες που καλεί. Επιπλέον, υπολογίζει τη λογική πράξη AND των Boolean παραμέτρων mydone για κάθε διεργασία. Στο πρόγραμμα αυτό έχουν γίνει λίγες επιπλέον αλλαγές σε σχέση με την διαδικασία Barrier και απλά αφορούν τη χρήση της μεταβλητής globaldone.
PROGRAM JacobiConv;
VAR ...
count : Integer;
Arrival, Departure : Spinlock;
globaldone : Boolean;
Function Aggregate (mydone : Boolean) : Boolean;
BEGIN
(*Φάση Άφιξης - Άθροιση των διεργασιών καθώς εισέρχονται στο φράγμα*)
Lock(Arrival);
count := count+1;
globaldone := globaldone AND mydone; (*Βήμα σύγκλισης*)
If count < n
then Unlock(Arrival) (*Συνέχιση της Φάσης Άφιξης*)
else Unlock(eparture); (*Τερματισμός της Φάσης Άφιξης*)
(*Φάση Αναχώρησης - Άθροιση των διεργασιών καθώς εξέρχονται από το φράγμα*)
Lock(Departure);
count := count - 1;
Aggregate:=globaldone;(*Επιστροφή της σημαίας flag στη διεργασία*)
If count > 0
then Unlock(Departure) (*Συνέχιση της Φάσης Αναχώρησης*)
else
BEGIN
globaldone := TRUE; (*Αλλαγή της τιμής της μεταβλητής για την επόμενη επανάληψη*)
Unlock(Arrival); (*Τερματισμός της Φάσης Αναχώρησης*)
END;
END;
BEGIN (*Κυρίως Πρόγραμμα*)
count := 0; (*Αρχικοποίηση της μεταβλητής count και τβν κλειδωμάτων*)
Unlock(Arrival);
Lock(Departure);
globaldone := TRUE; (*Αρχικοποίηση της τοπικής σημαίας*)
...
ΣΧΗΜΑ 6.14 Φράγμα συλλογής και διάδοσης
6.6.3 Παράλληλος αλγόριθμος Jacobi με σύγκλιση.
Η τεχνική συλλογής φράγματος μπορεί να χρησιμοποιηθεί ως βάση για το παράλληλο πρόγραμμα Jacobi με έλεγχο σύγκλισης, όπως φαίνεται στο σχήμα 6.15. Κάθε διεργασία έχει έναν βρόχο REPEAT που συνεχίζει τις επαναλήψεις μέχρι η μεταβλητή done να πάρει την τιμή TRUE. Η τιμή της done υπλογίζεται από την συνάρτηση Aggregate στο τέλος κάθε επανάληψης. Κάθε διεργασία περνά μία παράμετρο στην Aggregate: είναι η δική της συμβολή στον έλεγχο σύγκλισης. καθώς κάθε διεργασία υπολογίζει νέες τιμές των σημείων της γραμμής της, η μεταβλητή maxchange χρησιμοποιείται για να συσσωρεύει τη μέγιστη αλλαγή κάθε σημείου αυτής της σειράς. Στην συνέχεια η maxchange συγκρίνεται με την καθορισμένη ανοχή και η Boolean τιμή που προκύπτει εκχωρείται στην Aggregate σαν παράμετρος.
Όπως περιγράψαμε προηγουμένως, η συνάρτηση Aggregate συλλέγει όλες τις Boolean τιμές από όλες τις διεργασίες, υπολογίζει τη λογική πράξη AND και επιστρέφει το αποτέλεσμα σαν τιμή της συνάρτησης. Έτσι, η τοπική μεταβλητή done κάθε διεργασίας θα τεθεί στο καθολικό αποτέλεσμα του ελέγχου τερματισμού. Αν κάποια διεργασία δώσει κατά την συλλογή τιμή FALSE, τότε όλες οι διεργασίες θα λάβουν την τιμή αυτή και θα συνεχίσουν σε μια ακόμα επανάληψη. Μόνο όταν όλες οι διεργασίες περάσουν επιτυχώς το τεστ τερματισμού θα σταματήσουν. Παρατηρείστε στο πρόγραμμα 6.15 ότι εξακολουθεί να υπάρχει η πρώτη κλήση στη διαδικασία Barrier. Όμως, η δεύτερη διαδικασία Barrier έχει αντικατασταθεί από τη συνάρτηση Aggregate, που πραγματοποιεί μαζί συγχρονισμό και καθολικό έλεγχο τερματισμού.
PROGRAM JacobiConv;
CONST tolernce = .01;
n = 32;
VAR A, B : Array {0..n+1,o..n+1] of Real;
i,j : integer;
Procedure Barrier (me : Integer);
.... (*Ίδια με πριν*)
Function Aggregate (mydone : Boolean) : Boolean;
... (*Δες το σχήμα 6.14*)
BEGIN (*Κυρίως πρόγραμμα*)
...
B := A;
FORALL i := 1 to n do (*Δημιουργία των διεργασιών*)
VAR j: Integer;
change, maxchange : Real;
done : Boolean;
BEGIN
Repeat
maxchange := 0;
For j := 1 to n do (*Υπολογισμός νέων τιμών για κάθε στοιχείο της γραμμής*)
BEGIN
B[i,j] := (A[i-1,j]+A[i+1,j]+A[i,j-1]+A[i,j+1])/4;
change := ABS(B[i,j]-A[i,j]);
If change > maxchange then maxchange ;= change;
END;
Barrier;
A[i] := B[i];
done := Aggregate(maxchange‹tolerance);
Until done; (*Επανάληψη μέχρι τον καθορισμό του τοπικού τερματισμού*)
END;
END.
ΣΧΗΜΑ 6.15 Παράλληλο πρόγραμμα Jacobi με έλεγχο σύγκλισης
Η ακολουθιακή έκδοση του σχήματος 6.13 και η νέα παράλληλη έκδοση του 6.15 μπορούν να εκτελεστούν στο σύστημα της Multi-Pascal. Για κάθε επανάληψη η ακολουθιακή έκδοση απαιτεί 68000 μονάδες χρόνου, ενώ η παράλληλη 3200 μονάδες χρόνου ανά επανάληψη - έχουμε δηλαδή επιτάχυνση της τάξης του 21 περίπου για 32 επεξεργαστές. Η απώλεια της απόδοσης των επεξεργαστών είναι αποτέλεσμα της συμφόρησης που δημιουργείται από το φράγμα και την συλλογή. Όπως έχουμε δει και προηγουμένως, αυτή η συμφόρηση μπορεί να ελαχιστοποιηθεί χρησιμοποιώντας πιο αποδοτικές μεθόδους φράγματος. Κάθε μέθοδος φράγματος θα έχει και μια αντίστοιχη μέθοδο συλλογής. Για περισσότερες από 20 διεργασίες και οι δύο διαδικασίες Barrier και Aggregate πρέπει να χρησιμοποιούν τη μέθοδο του δυαδικού δένδρου, που απαιτεί χρόνο ανάλογο προς το λογάριθμο του αριθμού των διεργασιών. Οι ασκήσεις στο τέλος του κεφαλαίου ασχολούνται με το θέμα μετατροπής της μεθόδου του φράγματος δυαδικού δένδρου στην αντίστοιχη μέθοδο συλλογής.
Όμως, η τοπική μέθοδος φράγματος δεν έχει αντίστοιχη μέθοδο συλλογής. Στην τοπική μέθοδο φράγματος όπως εφαρμόζεται στον αλγόριθμο Jacobi οι διεργασίες συγχρονίζονται μόνο με τους άμεσους γείτονες τους μετά από κάθε επανάληψη. Αυτή η μορφή τοπικού συγχρονισμού δεν είναι επαρκής για την καθολική συλλογή των τιμών όλων των διεργασιών. Έτσι, η συνάρτηση Aggregate πρέπει να χρησιμοποιήσει μια από τις καθολικές μεθόδους φράγματος. Είναι όμως δυνατή η ελαχιστοποίηση της συνολικής μείωσης της απόδοσης που προκαλείται από την καθολική συλλογή, όπως θα δούμε στην επόμενη παράγραφο.
6.6.4 Βελτιώνοντας την απόδοση
Πιο πριν στο κεφάλαιο δείξαμε ότι το επιπλέον κόστος του συγχρονισμού στον αλγόριθμο Jacobi μπορεί να μειωθεί χρησιμοποιώντας ένα τοπικό φράγμα σε κάθε διεργασία. Στον αλγόριθμο Jacobi κάθε διεργασία χρησιμοποιεί τιμές που παράγονται από τους άμεσους γείτονές της στην προηγούμενη επανάληψη. Έτσι, είναι δυνατό για κάθε διεργασία να συγχρονιστεί τοπικά με τις δυο διεργασίες που έχουν αναλάβει την αμέσως επάνω και κάτω γραμμή του πίνακα. Η τοπική τεχνική φράγματος μειώνει το χρόνο συγχρονισμού σε μια μικρή σταθερά που είναι ανεξάρτητη από τον αριθμό των διεργασιών.
Όμως, η προσπάθεια χρησιμοποίησης τοπικού φράγματος στον αλγόριθμο Jacobi με έλεγχο σύγκλισης είναι ιδιαίτερα πολύπλοκη. Ο έλεγχος σύγκλισης απαιτεί μια καθολική συνάρτηση συλλογής που είναι βασικά ίδια με το καθολικό φράγμα. Αν αυτή η καθολική συλλογή γίνεται μετά από κάθε επανάληψη τότε το συνολικό κόστος συγχρονισμού πληρώνεται σε κάθε επανάληψη. Όμως, η επίδραση της συλλογής μπορεί να μειωθεί πραγματοποιώντας τον έλεγχο σύγκλισης μόνο μετά από κάποιο αριθμό επαναλήψεων. Ένα ολόκληρο σύνολο m επαναλήψεων μπορεί να πραγματοποιηθεί χρησιμοποιώντας την ιδιαίτερα αποδοτική μέθοδο τοπικού φράγματος για το συγχρονισμό των διεργασιών. Στην συνέχεια η καθολική συλλογή μπορεί να πραγματοποιηθεί στο τέλος των m επαναλήψεων, για να ελέξουμε αν έχει επιτευχθεί η επιθυμητή ανοχή στην λύση. Με αυτόν τον τρόπο, το επιπλέον κόστος που απαιτείται για καθολική ομαδοποίηση βρίσκεται από τον μέσο όρο των m επαναλήψεων. Αν η επιθυμητή ανοχή δεν έχει επιτευχθεί, τότε θα γίνουν όλες m επαναλήψεις επιπλέον και θα τις ακολουθήσει μια ακόμα καθολική συλλογή. Η γενική δομή κάθε διεργασίας i είναι όπως αυτή που φαίνεται παρακάτω :
Repeat For k := 1 to m do BEGIN Compute new values for row I; Record "maxchange" in values; LocalBarrier; Copy new values over old values; LocalBarrier; END; Compute "done" from global Aggregation; Until done;
Για μεγάλους αριθμούς διεργασιών αυτή η τεχνική του συνδυασμού τοπικού φράγματος με καθολικό έλεγχο σύγκλισης έχει σαν αποτέλεσμα μια σημαντική βελτίωση της απόδοσης. Όπως έχουμε προαναφέρει οι καλύτερες τεχνικές καθολικού φράγματος απαιτούν χρόνο ίσο με 20m ή με 80logn. Η μέθοδος της καθολικής συλλογής απαιτεί περίπου τον ίδιο χρόνο. Χρησιμοποιώντας m=10, η συλλογή πραγματοποιείται μόνο μια φορά στις δέκα επαναλήψεις, μειώνοντας έτσι το μέσο όρο του κόστους ανά επανάληψη στο 2n ή το 8logn. Το πρόγραμμα Jacobi με καθολική συλλογή μετά από κάθε επανάληψη (σχήμα 6.15) απαιτεί 3200 μονάδες χρόνου ανά επανάληψη. Αυτή η νέα έκδοση με τοπικά φράγματα επιτυγχάνει ένα μέσο όρο της τάξης των 2000 μονάδων χρόνου ανά επανάληψη, που είναι 27% βελτίωση. Ένα κρυφό επιπλέον κόστος σε αυτή τη νέα έκδοση είναι αποτέλεσμα των επιπλέον επαναλήψεων που μπορεί να πραγματοποιηθούν ακόμα και μετά την επίτευξη της επιθυμητής ανοχής στη λύση. Επειδή το πρόγραμμα κάνει έλεγχο σύγκλισης μόνο μετά από m επαναλήψεις, κάποιες επαναλήψεις που δεν χρειάζονται μπορεί να γίνουν κατά τη διάρκεια του τελευταίου σετ των m επαναλήψεων. έτσι, η τιμή m - δηλαδή η τιμή των επαναλήψεων ανά σετ - δεν πρέπει να αυξηθεί πολύ στην προσπάθειά μας επιπλέον μείωσης του μέσου κόστους συλλογής.
Και οι δύο εκδόσεις Jacobi με έλεγχο σύγκλισης επεξηγούν τον τύπο Υπολογισμός, Συλλογή και Διάδοση του παράλληλου αλγορίθμου. Κατά τη διάρκεια της Φάσης Υπολογισμού κάθε διεργασία υπολογίζει τις νέες τιμές του πίνακα με βάση τις παλιές. Στη Φάση Συλλογής συλλέγεται από κάθε διεργασία ο τοπικός έλεγχος ανοχής. Στη Φάση Διάδοσης επιστρέφεται σε όλες τις διεργασίες η καθολική συνθήκη τερματισμού. Οι Φάσεις Συλλογής και Διάδοσης καταναλώνουν πολύ χρόνο που είναι τουλάχιστον O(logn). Για αυτό το λόγο η συχνότητα των λειτουργιών αυτών σε σχέση με τη διάρκεια της Φάσης Υπολογισμού πρέπει να μειωθεί. Στο συγκεκριμένο παράδειγμα Jacobi είδαμε πως η απόδοση μπορεί να βελτιωθεί σημαντικά με την αύξηση της διάρκεια της Φάσης Υπολογισμού ώστε να συμπεριληφθούν επιπλέον επαναλήψεις.
Επόμενο:6.7 Περίληψη Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.5 Τοπικός Συγχρονισμός