Επόμενο:9.1 Επιβάρυνση Επικοινωνίας Πάνω: Περιεχόμενα Πίσω: Ασκήσεις
Κεφάλαιο 9o : Επιμερισμός δεδομένων
Η αρχή του παραλληλισμού των δεδομένων παρουσιάστηκε στο κεφάλαιο 2 και εξηγήθηκε με αρκετά παραδείγματα. Ο παραλληλισμός των δεδομένων απλά σημαίνει ότι η πολλαπλότητα των δεδομένων χρησιμοποιείται σαν δομήγια τη δημιουργία παράλληλης δραστηριότητας: διαφορετικά τμήματα της δομής δεδομένων επεξεργάζονται παράλληλα. Οι παράλληλες εφαρμογές σχεδόν πάντα έχουν σχέση με μεγάλους πολυδιάστατους πίνακες αριθμών, που σχηματίζουν τη βάση του παραλληλισμού δεδομένων. Αυτή η αρχή του παραλληλισμού δεδομένων είναι κεντρική τόσο στον προγραμματισμό των συστημάτων κατανεμημένης όσο και διαμοιραζόμενης μνήμης. Όμως, όταν η αρχή αυτή εφαρμόζεται σε συστήματα κατανεμημένης μνήμης η κατανεμημένη φύση της φυσικής μνήμης απαιτεί τη χρήση μιας ειδικής μορφής παραλληλισμού που ονομάζεται επιμερισμός δεδομένων.
Στον επιμερισμό δεδομένων η δομή δεδομένων επιμερίζεται σε ξεχωριστά μέρη, τα οποία ανατίθενται στις τοπικές μνήμες του συστήματος κατανεμημένης μνήμης. Μια απλή παράλληλη διεργασία καθορίζεται να λειτουργήσει σε κάθε ξεχωριστό τμήμα των δεδομένων. Η διεργασία βρίσκεται στην ίδια τοπική μνήμη με το τμήμα των δεδομένων που της έχει ανατεθεί και συνεπώς μπορεί να προσπελάσει αυτά τα δεδομένα τοπικά. Κάθε διεργασία για να επιτύχει καλή απόδοση πρέπει να βασίζεται κυρίως στις δικές της τοπικές μεταβλητές και στο δικό της τοπικό τμήμα δεδομένων. Όταν μια διεργασία χρειάζεται να αποκτήσει πρόσβαση σε δεδομένα που βρίσκονται σε απομακρυσμένες μνήμες τότε αυτό μπορεί να επιτευχθεί με πέρασμα μηνυμάτων μέσω του δικτύου που συνδέει τους επεξεργαστές. Όμως, εξαιτίας της μεγάλης χρονικής καθυστέρησης που συμβαίνει σε αυτή την διεπεξεργαστική επικοινωνία, το πέρασμα των μηνυμάτων πρέπει να είναι σχετικά σπάνιο.
Το κεφάλαιο αυτό περιγράφει και αναλύει τις διάφορες τεχνικές επιμερισμού των δεδομένων με παραδείγματα. Θα συζητηθούν αρκετά θέματα οργάνωσης για προγράμματα συστημάτων κατανεμημένης μνήμης που χρησιμοποιούν επιμερισμό των δεδομένων. Συνήθως δεν είναι εφικτός ο πλήρης περιορισμός μιας διεργασίας στο δικό της τοπικό τμήμα δεδομένων. Ο παράλληλος αλγόριθμος μπορεί να οργανωθεί, έτσι ώστε οι περισσότεροι υπολογισμοί να γίνουν με τοπικά δεδομένα. Όμως, οι διεργασίες θα θέλουν περιοδικά να προσπελάσουν δεδομένα που δεν βρίσκονται σε τοπικά τους τμήματα. Αυτό επιτυγχάνεται με περιοδική με διεπεξεργαστική επικοινωνία που χρησιμοποιεί διατεταγμένα πρότυπα επικοινωνίας μεταξύ των επεξεργαστών.
Το πρώτο παράδειγμα που παρουσιάζεται είναι το πρόβλημα των Ν-Σωμάτων από την αστροφυσική, στο οποίο υπολογίζεται η αμοιβαία επίδραση της βαρύτητας για ένα σύνολο μεγάλων αντικειμένων. Σε αυτό το πρόγραμμα ο πίνακας των δεδομένων που περιγράφει τη μάζα και τη θέση κάθε αντικειμένου μπορεί να επιμεριστεί και να ανατεθεί στις διεργασίες, αλλά κάθε διεργασία χρειάζεται τελικά να προσπελάσει όλα τα δεδομένα του πίνακα. Αυτό επιτυγχάνεται με μια τοπολογία επικοινωνίας ιδεατού δακτυλίου, γύρω από την οποία κινούνται κυκλικά όλα τα δεδομένα και έρχονται τελικά σε επαφή με κάθε διεργασία. Ένας επαναληπτικός αλγόριθμος εναλλάσσει τους τοπικούς υπολογισμούς με την επικοινωνία γύρω από το δακτύλιο. Για όσο χρονικό διάστημα το μέγεθος της φάσης υπολογισμού είναι αρκετά μεγαλύτερο σε σχέση με τις καθυστερήσεις επικοινωνίας του υποκείμενου συστήματος κατανεμημένης μνήμης, ο αλγόριθμος μπορεί να επιτύχει καλή απόδοση.
Το επόμενο παράδειγμα σε αυτό το κεφάλαιο είναι ο Παράλληλος Πολλαπλασιασμός Μήτρας σε τοπολογία τόρου σε σύστημα κατανεμημένης μνήμης. Οι δύο πίνακες που πρόκειται να πολλαπλασιαστούν επιμερίζονται στους επεξεργαστές σε ένα δι-διάστατο Τόρο. Κάθε επεξεργαστής πραγματοποιεί έναν τοπικό πολλαπλασιασμό μητρών χρησιμοποιώντας τα τοπικά τμήματά του από τους πρωταρχικούς πίνακες. Στην συνέχεια, ακολουθεί η φάση επικοινωνίας, στην οποία κάθε επεξεργαστής στέλνει τα τοπικά τμήματά του σε άλλους επεξεργαστές και λαμβάνει νέα τμήματα. Ο επαναληπτικός αλγόριθμος εναλλάσσει τον τοπικό πολλαπλασιασμό μητρών με επικοινωνία και τελικά καταλήγει σε μια τελική συνολική μήτρα. Ο παράλληλος αλγόριθμος χρησιμοποιεί ολοκληρωτικά την τοπολογία Τόρου επικοινωνώντας και προς τις δύο κατευθύνσεις, κάθετα και οριζόντια.
Το τελευταίο παράδειγμα είναι μια έκδοση του προγράμματος του αλγόριθμου Jacobi, που παρουσιάστηκε στο κεφάλαιο 6 για την επίλυση μιας διαφορικής εξίσωσης. Σε αυτόν τον αλγόριθμο ο πίνακας δεδομένων εύκολα επιμερίζεται. Όμως, κάθε διεργασία χρειάζεται δεδομένα όχι μόνο από το δικό της τμήμα, αλλά επίσης και από τα τμήματα των άμεσων γειτόνων της. Έτσι, μετά από κάθε επανάληψη κάθε διεργασία πρέπει να στέλνει ένα αντίγραφο των δικών της τοπικών δεδομένων του τμήματός της σε όλες τις γειτονικές της διεργασίες. Αυτό πρέπει να γίνεται μετά από κάθε επανάληψη, γιατί οι τιμές των δεδομένων αλλάζουν και οι γειτονικές διεργασίες χρειάζονται τις νέες τιμές στην επόμενη επανάληψη.
Ο σκοπός αυτού του κεφαλαίου είναι να παρουσιάσει πώς όλες οι παράλληλες τεχνικές που παρουσιάστηκαν στα προηγούμενα κεφάλαια μπορούν να προσαρμοστούν στις ειδικές ανάγκες των συστημάτων κατανεμημένης μνήμης. Οι περισσότερες από τις αρχές και τις τεχνικές οργάνωσης που παρουσιάστηκαν πιο πριν και σχετίζονται με πολυεπεξεργαστές, ισχύουν και στα συστήματα κατανεμημένης μνήμης. Όμως, όπως θα δούμε και στη συνέχεια απαιτείται κάποια αναδιοργάνωση των παράλληλων αλγορίθμων. Επίσης αυτό το κεφάλαιο στοχεύει στην παρουσίαση της χρήσης της τεχνικής παράλληλου προγραμματισμού με πέρασμα μηνυμάτων, που παρουσιάστηκε στο κεφάλαιο 8.
Επόμενο:9.1 Επιβάρυνση Επικοινωνίας Πάνω: Περιεχόμενα Πίσω: Ασκήσεις