Επόμενο:Αναφορές Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: 9.4 Αλγόριθμος JACOBI

9.5 Περίληψη

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

Το πρώτο παράδειγμα που παρουσιάστηκε στο κεφάλαιο είναι το πρόγραμμα των Ν-Σωμάτων. Αυτό το πρόγραμμα έχει την ανεπιθύμητη ιδιότητα ότι άσχετα από τον τρόπο με τον οποίο επιμερίζονται τα δεδομένα κάθε επεξεργαστής εξακολουθεί να χρειάζεται πρόσβαση σε όλα τα δεδομένα. Όμως, παρά αυτή την απαίτηση είναι δυνατή η ανάπτυξη ενός αποδοτικού προγράμματος συστήματος κατανεμημένης μνήμης με περιστρεφόμενα τμήματα δεδομένων που κινούνται στο δίκτυο επικοινωνίας Δακτυλίου, έτσι ώστε κάθε επεξεργαστής τελικά να λάβει ένα αντίγραφο κάθε τμήματος. Επικαλύπτοντας την επικοινωνία με τον υπολογισμό η απώλεια του χρόνου από την περιστροφική κίνηση των τμημάτων ελαχιστοποιείται.

Το δεύτερο παράδειγμα είναι ο Πολλαπλασιασμός Μήτρας. Πολλά από τα θέματα αυτού του προγράμματος είναι παρόμοια με αυτά του προγράμματος των Ν-Σωμάτων, αλλά εδώ έχουμε δύο διαστάσεις αντί για μια. Οι πίνακες στον Πολλαπλασιασμό Μήτρας επιμερίζονται σε δύο διαστάσεις. Για την υλοποίηση του αλγορίθμου όλα τα τμήματα του πίνακα Α περιστρέφονται στην γραμμή τους και όλα τα τμήματα του Β περιστρέφονται στη στήλη τους. Εφόσον ο Τόρος έχει συνδέσεις μεταξύ των άκρων είναι ιδανικός για αυτή τη δι-διάστατη περιστροφή των τμημάτων. Το πρόγραμμα Πολλαπλασιασμού Μήτρας επιτυγχάνει επίσης καλή επιτάχυνση, με την προϋπόθεση ότι το μέγεθος των τμημάτων είναι αρκετά μεγάλο για να παράγει επαρκές μέγεθος διεργασίας, έτσι ώστε να ξεπεραστούν οι επιβαρύνσεις δημιουργίας διεργασίας και η κατανομή των αρχικών δεδομένων.

Το τελευταίο παράδειγμα του κεφαλαίου είναι το πρόγραμμα του αλγορίθμου Jacobi σε Υπερκύβο συστήματος κατανεμημένης μνήμης. ο πρόγραμμα αυτό είναι παρόμοιο με την έκδοση για σύστημα διαμοιραζόμενης μνήμης που παρουσιάστηκε στο κεφάλαιο 6. Ο πίνακας των δεδομένων επιμερίζεται κατά γραμμές, σε κάθε επεξεργαστή ανατίθεται μια γραμμή και επίσης κάθε επεξεργαστής λαμβάνει ένα αντίγραφο των δύο γειτονικών γραμμών. Μετά από κάθε επανάληψη οι διεργασίες στέλνουν τις πρόσφατα υπολογισμένες τιμές και στους δύο γείτονες. Διαφορετικά από τα προγράμματα των Ν-Σωμάτων και του Πολλαπλασιασμού Μήτρας, τα δεδομένα που κινούνται στον αλγόριθμο Jacobi είναι πάντα πρόσφατα υπολογισμένα. Συνεπώς, σε αυτό το πρόγραμμα η επικοινωνία δεν μπορεί να επικαλυφθεί με τον υπολογισμό.

Εκτός από τη διευκρίνηση των τεχνικών επιμερισμού δεδομένων το κεφάλαιο αυτό ασχολείται με μια ταξινόμηση των τεχνικών προγραμματισμού του περάσματος μηνυμάτων για το γράψιμο προγραμμάτων σε συστήματα κατανεμημένης μνήμης σε Μulti-Pascal. Όλες οι διεργασίες δημιουργούνται με την κλήση μιας διαδικασίας, που βασίζεται στις δικές της τοπικές μεταβλητές για τον υπολογισμό. Τα τμήματα των δεδομένων που ανατίθενται σε κάθε διεργασία περνούν σαν παράμετροι τιμών στην κλήση διαδικασίας. Κατά τη διάρκεια της φάσης υπολογισμού του προγράμματος τα δεδομένα κινούνται μεταξύ των διεργασιών χρησιμοποιώντας τις θύρες επικοινωνίας. Τα τρία παραδείγματα προγραμμάτων που παρουσιάστηκαν είναι επεξηγηματικά των γενικών οργανωτικών τεχνικών που μπορούν να χρησιμοποιηθούν σε μια μεγάλη ποικιλία προγραμμάτων συστημάτων κατανεμημένης μνήμης.

Επόμενο:Αναφορές Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: 9.4 Αλγόριθμος JACOBI