Επόμενο:6.3 Γραμμικό Φράγμα Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.1 Επιλύνοντας μια Διαφορική Εξίσωση
6.2. Παράλληλος Αλγόριθμος Jacobi
Η πιο προφανής τεχνική παραλληλισμού του αλγορίθμου Jacobi είναι η αλλαγή των εσωτερικών βρόχων FOR με FORALL βρόχους. Με τον τρόπο αυτό θα έχουμε παραλληλισμό κατά τη διάρκεια κάθε επανάληψης. Ο εξωτερικός βρόχος FOR δεν μπορεί να αλλαχθεί με FORALL γιατί οι επαναλήψεις πρέπει να είναι ακολουθιακές. Μια δεύτερη μέθοδος για τον παραλληλισμό αυτού του προγράμματος είναι η εισαγωγή του εξωτερικού επαναληπτικού βρόχου μέσα σε κάθε παράλληλη διεργασία. Κάθε διεργασία θα εξακολουθήσει να επαναλαμβάνεται εσωτερικά, αλλά θα συγχρονίζεται με τις άλλες διεργασίες στο τέλος κάθε επανάληψης. Αυτές οι δυο τεχνικές θα αναλυθούν παρακάτω με λεπτομέρειες.
6.2.1 Συγχρονισμός με τερματισμό διεργασίας
Η βασική απαίτηση για την παράλληλη έκδοση του αλγορίθμου Jacobi είναι ότι κάθε επανάληψη συμπληρώνεται πριν την έναρξη της επόμενης. Αυτό αποτελεί τμήμα του ορισμού του αλγορίθμου και πρέπει να διατηρηθεί έτσι ώστε ο αλγόριθμος να δουλέψει σωστά και να προσεγγίσει μια κατάλληλη λύση. Παρόλη την ύπαρξη αυτού του περιορισμού, εξακολουθεί να υπάρχει η δυνατότητα παραλληλισμού μέσα σε κάθε επανάληψη. Η νέα τιμή κάθε σημείου υπολογίζεται από τις τιμές των τεσσάρων γειτονικών του. Ο υπολογισμός κάθε σημείου μπορεί να πραγματοποιηθεί παράλληλα με τον υπολογισμό όλων των σημείων. Με την αλλαγή των δύο εσωτερικών βρόχων FOR με ένα FORALL, επιτυγχάνεται ο παραλληλισμός κάθε επανάληψης. Όλες οι παράλληλες διεργασίες θα τελειώσουν μετά τον υπολογισμό της νέας τιμής του σημείου που έχουν αναλάβει. Μετά, στην αρχή της νέας επανάληψης θα δημιουργηθεί μια νέα ομάδα διεργασιών.
Η υπολογιστική δραστηριότητα κάθε διεργασίας φαίνεται στο σχήμα 6.2: κάθε διεργασία υπολογίζει απλά ένα μέσο όρο. Όλες οι διεργασίες έχουν μικρή διάρκεια και έτσι πιθανόν να δημιουργηθεί ένα πρόβλημα μεγέθους διεργασίας. Για την αποφυγή αυτού του προβλήματος και για να κάνουμε πιο απλό το πρόγραμμα θα δημιουργήσουμε μια διεργασία που χειρίζεται κάθε γραμμή στοιχείων. Αυτό επιτυγχάνεται με τον παραλληλισμό μόνο του i βρόχου. Το παράλληλο πρόγραμμα φαίνεται στο σχήμα 6.4. Ο εσωτερικός δείκτης j πρέπει να αλλαχθεί σε μια τοπική μεταβλητή μέσα σε κάθε διεργασία. Επίσης η λειτουργία αντιγραφής των νέων τιμών του B στον πίνακα A έχει γίνει παράλληλη. Παρόλο που αυτό στην παράλληλη έκδοση γίνεται με μια απλή δήλωση εκχώρησης, η εφαρμογή της λειτουργίας αντιγραφής αυτού του πίνακα απαιτεί πολλά ακολουθιακά βήματα.
PROGRAM ParallelJacobi;
CONST n = 32;
numiter = ...;
VAR A, B: ARRAY [0..n+1,0..n+1] of Real;
i, j, k: Integer;
BEGIN
... (*Τοποθέτηση αρχικών τιμών στον πίνακα Α*)
B:= A;
For k:= 1 to numiter do
BEGIN
(*Φάση Ι - Υπολογισμός των νέων τιμών*)
FORALL i:=1 to n do (*Δημιουργία διεργασίας για κάθε γραμμή*)
VAR
j: Integer;
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;
END;
(*Φάση ΙΙ -Αντιγραφή των νέων τιμών στον Α*)
FORALL i:=1 to n do (*Αντιγραφή των νέων τιμών από τον Β στον Α*)
A[i]:= B[i];
END;
END.
ΣΧΗΜΑ 6.4 Παράλληλος αλγόριθμος Jacobi
Το ακολουθιακό πρόγραμμα του σχήματος 6.3 έχει χρόνο εκτέλεσης για κάθε επανάληψη 45202 μονάδες χρόνου. Το παράλληλο πρόγραμμα απαιτεί 2100 μονάδες χρόνου για κάθε επανάληψη: πρόκειται για μια επιτάχυνση 21.5 πάνω από την ακολουθιακή έκδοση. Παρά το ότι η παράλληλη έκδοση δημιουργεί 32 διεργασίες για να εργαστούν πάνω στις 32 γραμμές, η επιτάχυνση είναι μόνο 21 εξαιτίας του επιπλέον κόστους της δημιουργίας των διεργασιών. Κατά τη διάρκεια κάθε επανάληψης όλες οι διεργασίες πρέπει να δημιουργηθούν στην πρώτη δομή FORALL να καταστραφούν και μετά να ξαναδημιουργηθούν στην δεύτερη FORALL. Το πρόγραμμα εξαιτίας αυτών των πολλών δημιουργιών διεργασιών έχει μεγάλο επιπλέον κόστος κάθε φορά στον εξωτερικό επαναληπτικό βρόχο. Πρόκειται περίπου για 33% απώλεια στη επιτάχυνση του προγράμματος.
Το παράλληλο πρόγραμμα Jacobi επιτυγχάνει συγχρονισμό των διεργασιών με το να καταστρέφει και στη συνέχεια να ξαναδημιουργεί τις διεργασίες. Στην πραγματικότητα υπάρχουν δύο συγχρονισμοί κατά τη διάρκεια κάθε επανάληψης: μία μετά τη φάση Ι και μια μετά τη φάση ΙΙ. Κατά τη διάρκεια της φάσης Ι το πρώτο σετ των 32 διεργασιών που θα εργαστούν πάνω στις 32 γραμμές του πίνακα A δημιουργούνται από το πρώτο FORALL. Η δομή FORALL τελειώνει μόνο μετά την καταστροφή των 32 διεργασιών. Με αυτό τον τρόπο η δομή της FORALL χρησιμοποιείται για τον συγχρονισμό των διεργασιών. Αυτός ο συγχρονισμός είναι απαραίτητος πριν την έναρξη της φάσης ΙΙ, κατά την οποία οι νέες τιμές του πίνακα B γράφονται στον πίνακα A. Είναι σημαντικό όλες οι νέες τιμές να έχουν υπολογιστεί πριν γίνει οποιαδήποτε αντιγραφή. Αυτό διασφαλίζεται με το χωρισμό των δυο διαφορετικών φάσεων στις δυο διαφορετικές FORALL δηλώσεις.
Όμοια είναι απαραίτητο να έχει ολοκληρωθεί η αντιγραφή του πίνακα B στον πίνακα A πριν ο δεύτερος χρησιμοποιηθεί ξανά στην επόμενη επανάληψη. Οι 32 διεργασίες που κάνουν την αντιγραφή στη φάση ΙΙ συγχρονίζονται στο τέλος της δεύτερης δήλωσης FORALL. Έτσι, μέσα σε κάθε επανάληψη διενεργούνται δυο συγχρονισμένες λειτουργίες, που παράγονται από την τεχνική της καταστροφής και της επαναδημιουργίας των διεργασιών. Το επιπλέον κόστος χρόνου εκτέλεσης αυτής της τεχνικής εξαρτάται από τον χρόνο δημιουργίας των διεργασιών και τον αριθμό των διεργασιών. Για ένα πρόγραμμα με n διεργασίες αυτή η μέθοδος συγχρονισμού έχει κόστος χρόνου O(n).
6.2.2 Συγχρονισμός φράγματος
Το σύστημα της Multi-Pascal χρησιμοποιεί έχει σχετικά μικρό επιπλέον κόστος στη δημιουργία των διεργασιών - κυμαίνεται στις 10 χρονικές μονάδες. Όμως, οι περισσότεροι πραγματικοί παράλληλοι υπολογιστές έχουν κόστος που είναι πολύ μεγαλύτερο. Για αυτό το λόγο, η μέθοδος της καταστροφής και της επαναδημιουργίας των διεργασιών δεν είναι αποδεκτή στα περισσότερα συστήματα. Μερικά συστήματα για να παράσχουν φτηνότερο συγχρονισμό διεργασιών εμπεριέχουν μια λειτουργία φράγματος στην παράλληλη γλώσσα προγραμματισμού. Φράγμα είναι ένα σημείο του προγράμματος στο οποίο οι παράλληλες διεργασίες περιμένουν η μία την άλλη. Η πρώτη διεργασία που θα εκτελέσει την δήλωση φράγματος απλά θα περιμένει μέχρι να φτάσουν όλες οι άλλες διεργασίες. Όταν όλες οι διεργασίες φτάσουν στη δήλωση φράγματος μπορούν όλες να συνεχίσουν την παράλληλη εκτέλεση. Η όλη διαδικασία του φράγματος φαίνεται στο σχήμα 6.5. Ο χρόνος κυλάει από την κορυφή ως τη βάση του σχήματος με τους αστερίσκους να δηλώνουν χρονικές περιόδους κατά τη διάρκεια των οποίων εκτελείται η διεργασία.
Η τεχνική του συγχρονισμού φράγματος μπορεί να εφαρμοστεί στο παράλληλο πρόγραμμα Jacobi. Οι διεργασίες δημιουργούνται μόνο μια φορά στην αρχή του βρόχου αντί να καταστρέφονται και να ξαναδημιουργούνται συνεχώς. Όπως είχαμε αναφέρει προηγουμένως, οι διεργασίες πρέπει να συγχρονίζονται δύο φορές κατά τη διάρκεια κάθε επανάληψης: πρώτα μετά τον υπολογισμό των νέων από τις παλιές και μετά κατά την αντικατάσταση των παλιών τιμών από τις νέες. Αυτό μπορεί να επιτευχθεί χρησιμοποιώντας δυο λειτουργίες φράγματος μέσα σε κάθε διεργασία. Το πρόγραμμα φαίνεται στο σχήμα 6.6.
ΣΧΗΜΑ 6.5 Συγχρονισμός φράγματος διεργασιών
Το πιο σημαντικό χαρακτηριστικό αυτού του νέου προγράμματος είναι το ότι η δήλωση FORALL είναι τώρα στον εξωτερικό βρόχο. Οι 32 διεργασίες δημιουργούνται μόνο μια φορά και λαμβάνουν την τιμή κάθε γραμμής. Οι επαναλήψεις από 1 ως numiter πραγματοποιούνται με έναν FOR βρόχο μέσα σε κάθε διεργασία. Στο πρόγραμμα αυτό το επιπλέον κόστος δημιουργίας των διεργασιών συμβαίνει μόνο μια φορά. Οι διεργασίες και εδώ πρέπει να συγχρονίζονται δύο φορές κατά τη διάρκεια κάθε επανάληψης, αλλά αυτό τώρα επιτυγχάνεται με το φράγμα και όχι με την καταστροφή και την επαναδημιουργία των διεργασιών.
Η διαδικασία εκτελείται μετά τον υπολογισμό των νέων τιμών της σειράς που έχει αναλάβει κάθε διεργασία. Με τον τρόπο αυτό όλες οι διεργασίες περιμένουν τον συγχρονισμό των άλλων και καμία δεν επιτρέπεται να συνεχίσει. Μετά από αυτόν τον συγχρονισμό υπολογίζονται όλες οι νέες τιμές. Το επόμενο βήμα είναι η αντιγραφή των νέων τιμών από τον πίνακα B στον πίνακα A. Αυτό επιτυγχάνεται με ένα απλό όρισμα σε κάθε διεργασία που αντιγράφει όλη τη γραμμή. Μετά τη λειτουργιά της αντιγραφής οι διεργασίες πρέπει και πάλι να συγχρονιστούν με τη διαδικασία Barrier πριν την έναρξη της νέας επανάληψης, που χρησιμοποιεί τον πίνακα A.
Η απόδοση αυτού του προγράμματος εξαρτάται σε μεγάλο βαθμό από το χρόνο που απαιτείται για την εκτέλεση της λειτουργίας του φράγματος. Με τη χρησιμοποίηση του συγχρονισμού φράγματος ο χρόνος δημιουργίας των διεργασιών έχει ελαχιστοποιηθεί, αλλά έχει δημιουργηθεί ένα νέο επιπλέον κόστος: η εκτέλεση της διαδικασίας φράγματος. Στις επόμενες παραγράφους θα εξετάσουμε δυο τεχνικές υλοποίησης φραγμάτων καθώς και την απόδοσης τους. Περιγράφεται μια τεχνική γραμμικού χρόνου της οποίας ο χρόνος εκτέλεσης είναι ανάλογος προς των αριθμό των διεργασιών. Στην συνέχεια παρουσιάζεται μια μέθοδος με λογαριθμικό χρόνο.
PROGRAM JacobiBarrier;
CONST n = 32;
numiter = ...;
VAR a, b : Array [0..n+1,0..n+1] of Real;
i, j : Integer;
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;
Barrier;
A[i] := B[i];
Barrier;
END;
END;
END.
ΣΧΗΜΑ 6.6 Αλγόριθμος Jacobi με συγχρονισμό φράγματος.
Επόμενο:6.3 Γραμμικό Φράγμα Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.1 Επιλύνοντας μια Διαφορική Εξίσωση