Επόμενο:6.1 Επιλύνοντας μια Διαφορική Εξίσωση Πάνω: Περιεχόμενα Πίσω: Ασκήσεις
Κεφάλαιο 6o : Σύγχρονος παραλληλισμός
Μια από τις βασικές πρακτικές εφαρμογές του παράλληλου προγραμματισμού αναφέρεται σε μεγάλα προβλήματα που προκύπτουν στους χώρους της επιστήμης και της μηχανικής. Αυτά τα προβλήματα στην ουσία σχετίζονται με πίνακες πολλών διαστάσεων, οι οποίοι προσφέρουν μια πολύ καλή ευκαιρία εφαρμογής του παραλληλισμού δεδομένων καθώς διαφορετικά στοιχεία των πινάκων μπορούν να προσπελαστούν παράλληλα. Οι αριθμητικές τεχνικές υπολογισμού σε αυτούς τους πίνακες είναι συνήθως επαναληπτικές με κάθε επανάληψη να οδηγεί πλησιέστερα προς την τελική επίλυση. Αυτό ειδικά συμβαίνει στην αριθμητική λύση μεγάλων συστημάτων εξισώσεων. Γενικά κάθε επανάληψη χρησιμοποιεί τα δεδομένα της προηγούμενης και το πρόβλημα σταδιακά συγκλίνει προς μια λύση με μια επιθυμητή ακρίβεια.
Σε τέτοιους επαναληπτικούς αριθμητικούς αλγορίθμους προσφέρονται σημαντικές ευκαιρίες ανάπτυξης του παραλληλισμού σε κάθε επανάληψη. Πολλές παράλληλες διεργασίες μπορούν να αναπτυχθούν για να δουλέψουν σε διαφορετικά τμήματα του πίνακα. Όμως, μετά από κάθε επανάληψη οι διεργασίες πρέπει να συγχρονίζονται γιατί οι τιμές που παράγονται από μια διεργασία χρησιμοποιούνται από άλλες διεργασίες στην επόμενη επανάληψη. Αυτή η μορφή παράλληλου προγραμματισμού ονομάζεται σύγχρονος παραλληλισμός (synchronous parallelism).
Στον σύγχρονο παραλληλισμό η συνολική δομή του προγράμματος συχνά αποτελείται από ένα FORALL βρόχο, ο οποίος δημιουργεί πολλές παράλληλες διεργασίες οι οποίες με τη σειρά τους επεξεργάζονται διαφορετικά τμήματα του πίνακα δεδομένων. Οι διεργασίες είναι επαναληπτικές και συγχρονισμένες μεταξύ τους στο τέλος κάθε επανάληψης. Ο σκοπός του συγχρονισμού αυτού είναι η διαβεβαίωση ότι όλες οι διεργασίες τελειώνουν την τρέχουσα επανάληψη πριν κάποια από αυτές να αρχίσει την επόμενη. Με αυτόν τον τρόπο όλες οι νέες τιμές δεδομένων που παράγονται κατά τη διάρκεια κάθε επανάληψης είναι διαθέσιμες προς όλες τις διεργασίες στην επόμενη. Το κεφάλαιο αυτό παρουσιάζει μια ποικιλία τεχνικών συγχρονισμού διαφορετικών διεργασιών που μπορούν να χρησιμοποιηθούν σε τέτοια προγράμματα.
Ο συγχρονισμός των διεργασιών μπορεί να δημιουργήσει σημεία συμφόρησης μέσα στο πρόγραμμα. Από τη φύση του ο συγχρονισμός είναι αντίθετος προς τον παραλληλισμό, γιατί όλες οι διεργασίες πρέπει να βρίσκονται κάτω από κάποιον κεντρικό έλεγχο. Όμως αυτή η διαδικασία μπορεί να προκαλέσει ανταγωνισμό και καθυστέρηση στην εκτέλεση των διεργασιών. Κατά την παρουσίαση των διάφορων τεχνικών συγχρονισμού θα παρουσιαστούν και θα συγκριθούν μεταξύ τους οι διαφορετικές αποδόσεις τους. Πολλές από τις τεχνικές παρουσιάζουν γραμμική καθυστέρηση ανάλογη προς τον αριθμό των διεργασιών. Η τεχνική του δυαδικού δέντρου παράγει καθυστέρηση που είναι ανάλογη προς τον λογάριθμο του αριθμού των διεργασιών. Κάποιοι τύποι αλγορίθμων είναι επίσης δυνατό να χρησιμοποιήσουν μια τοπική τεχνική συγχρονισμού, στην οποία κάθε διεργασία συγχρονίζεται μόνο με κάποιες άμεσα γειτονικές της διεργασίες. Αυτή η τεχνική απαιτεί σταθερό χρόνο που δεν αυξάνεται με τον αριθμό των διεργασιών.
Στο κεφάλαιο αυτό παρουσιάζεται επίσης μια σημαντική υποκατηγορία σύγχρονων παράλληλων αλγορίθμων: Υπολογισμός, Συλλογή και Διάδoση που προέρχεται από το Compute, Aggregate and Broadcast (CAB). Στα προγράμματα CAB ο συγχρονισμός της διεργασίας χρησιμοποιείται και για την συλλογή των τοπικών τιμών δεδομένων των διεργασιών και την ένταξή τους σε καθολικά δεδομένα που διαδίδονται ξανά προς όλες τις διεργασίες. Οι συνηθισμένες τεχνικές συγχρονισμού προσαρμόζονται εύκολα έτσι ώστε να φέρουν εις πέρας αυτή την συλλογή και τη διάδοση. Η τεχνική CAB είναι ιδιαίτερα χρήσιμη για τους επαναληπτικούς αριθμητικούς αλγορίθμους που πρέπει να συνεχίσουν μέχρι να συναντήσουν κάποιο κριτήριο σύγκλισης. Η φάση της συλλογής χρησιμοποιείται για τη συλλογή πληροφοριών από όλες τις διεργασίες έτσι ώστε να γίνει κατανοητό αν έχει συναντηθεί το γενικό κριτήριο σύγκλισης. Στη συνέχεια και στη φάση της διάδοσης θα σταλούν πληροφορίες ξανά σε κάθε διεργασία, που θα αναφέρουν στην κάθε μια ξεχωριστά αν χρειάζεται να πραγματοποιήσουν επιπλέον επανάληψη ή αν τελείωσαν.
Για την κατανόηση αυτών των τεχνικών σύγχρονου παραλληλισμού θα παρουσιαστεί ένα σημαντικό πρόγραμμα αριθμητικής ανάλυσης: πρόκειται για μια παράλληλη έκδοση του αριθμητικού αλγορίθμου που ονομάζεται Χαλάρωση Jacobi (Jacobi Relaxation) και χρησιμοποιείται για την επίλυση διαφορικών εξισώσεων.
Επόμενο:6.1 Επιλύνοντας μια Διαφορική Εξίσωση Πάνω: Περιεχόμενα Πίσω: Ασκήσεις