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

6.7 Περίληψη

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

Η πρώτη μέθοδος συγχρονισμού αφορά το να αφήνονται οι διεργασίες να καταστρέφονται μετά από κάθε επανάληψη και να ξαναδημιουργούνται στην αρχή της επόμενης επανάληψης. Η μέθοδος αυτή είναι χρήσιμη σε συστήματα με χαμηλό κόστος δημιουργίας διεργασιών. Όμως, σε συστήματα με μεγάλο κόστος δημιουργίας διεργασιών δεν είναι επιτρεπτή αυτή η μέθοδος καταστροφής των διεργασιών. Για αυτά τα συστήματα μπορεί να χρησιμοποιηθεί ένας συγχρονισμός φράγματος, έτσι ώστε να συγχρονίζονται οι διεργασίες μετά το τέλος κάθε επανάληψης. Περιγράφηκε μια τεχνική φράγματος με πολυπλοκότητα O(n) που χρησιμοποιεί κλείδωμα και που βασίζεται σε μια μεταβλητή αθροιστή. Στη μέθοδο μεταβλητής αθροιστή, οι διεργασίες αθροίζονται καθώς περνούν από τη Φάση Άφιξης του φράγματος. Η τελευταία διεργασία που θα περάσει τη Φάση Άφιξης θα ανοίξει και τη Φάση Αναχώρησης ελευθερώνοντας έτσι όλες τις διεργασίες.

Για την επίτευξη ενός φράγματος με πολυπλοκότητα O(logn) χρησιμοποιήθηκε η τεχνική δυαδικού δένδρου. Καθώς οι διεργασίες εισέρχονται στο φράγμα ζευγαρώνουν και επιλέγουν κάποιον νικητή. Οι νικητές ζευγαρώνουν στον επόμενο γύρο. Αυτή η μορφή τουρνουά μειώνει τον αριθμό των διεργασιών κατά το ήμισυ μετά το τέλος κάθε γύρου. Η τελική γενική διεργασία νικητής κάθεται στην κορυφή του δένδρου του τουρνουά. Στην συνέχεια, η διεργασία νικητής προσπελαύνει το δένδρο προς τα κάτω ελευθερώνοντας τους προηγούμενους χαμένους αντιπάλους της που βρίσκονται σε κατάσταση αναμονής. Τελικά όλες οι διεργασίες ελευθερώνονται και επιστρέφουν στους υπολογισμούς. Αυτή η τεχνική δένδρου ελαχιστοποιεί τη συμφόρηση που προκύπτει από τις μεθόδους πολυπλοκότητας O(n) εξαιτίας της συγκέντρωσης. Η αποκέντρωση στη μέθοδο του δένδρου αυξάνει τον παραλληλισμό και μειώνει τον ανταγωνισμό για τα διαμοιραζόμενα κανάλια. Αυτή η τεχνική δυαδικού δένδρου είναι χρήσιμη αν ο αριθμός των διεργασιών είναι πολύ μεγάλος.

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

Όλες οι μέθοδοι καθολικού συγχρονισμού φράγματος εφαρμόζονται εύκολα για να υλοποιήσουν μια άλλη σημαντική λειτουργία: την καθολική συλλογή και την διάδοση δεδομένων. Η λειτουργία αυτή χρησιμοποιείται σαν βάση μιας μεγάλης κατηγορίας παράλληλων αλγορίθμων που ονομάζεται Υπολογισμός, Συλλογή και Διάδοση. Όταν προστίθεται στο πρόγραμμα Jacobi και ένας καθολικός έλεγχος σύγκλισης το αποτέλεσμα είναι ένας CAB αλγόριθμος. Ο έλεγχος σύγκλισης εφαρμόζεται τοπικά σε κάθε διεργασία και μετά τα τοπικά αποτελέσματα συλλέγονται σε καθολικό επίπεδο και το αποτέλεσμα μεταδίδεται πίσω σε κάθε διεργασία. Για αλγόριθμους που παρουσιάζουν μια τοπικότητα, όπως ο Jacobi, είναι δυνατός ο συνδυασμός τοπικών φραγμάτων με καθολική συλλογή και διάδοση. Το αποτέλεσμα είναι ένα πολύ αποδοτικό πρόγραμμα που επιτυγχάνει μεγάλη επιτάχυνση.

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