9.1 Επιβάρυνση Επικοινωνίας

Επόμενο: 9.2 Το Πρόβλημα των Ν-Σωμάτων στην Αστροφυσική Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: Κεφάλαιο 9o : Επιμερισμός δεδομένων

9.1 Επιβάρυνση Επικοινωνίας

Ένα από τα σημαντικότερα θέματα του κεφαλαίου είναι οι γενικές τεχνικές οργάνωσης για τα προγράμματα των συστημάτων κατανεμημένης μνήμης που ελαχιστοποιούν την επίδραση της καθυστέρησης επικοινωνίας στην απόδοση. Μέσα από μια σειρά παραδειγμάτων θα δείξουμε ότι η επιβάρυνση επικοινωνίας μπορεί να μειωθεί σε ένα ανεκτό επίπεδο μέσα από την κατάλληλη οργάνωση του προγράμματος. Πριν να αναφερθούμε σε συγκεκριμένα παραδείγματα είναι χρήσιμο να παρουσιάσουμε περιληπτικά μια γενική ανάλυση της επιβάρυνσης επικοινωνίας στα προγράμματα των συστημάτων κατανεμημένης μνήμης. Η ανάλυση αυτή οδηγεί στο να αποκτήσουμε μια σημαντική αντίληψη σχετικά με την απόδοση των προγραμμάτων των συστημάτων κατανεμημένης μνήμης και επίσης παρέχει τη βάση για μια πιο λεπτομερή ανάλυση της απόδοσης των παραδειγμάτων που αναφέρονται στη συνέχεια του κεφαλαίου.

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

Φάση επικοινωνίας: Sk^b

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

Πρόβλημα Ν-Σωμάτων: b=2

Πολλαπλασιασμός Μήτρας: b=3/2

Χαλάρωση Jacobi: b=1

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

Φάση επικοινωνίας: Vk + F

Η συνολική διάρκεια κάθε επανάληψης είναι το άθροισμα των φάσεων υπολογισμού και επικοινωνίας και συνεπώς έχει την ακόλουθη μορφή:

Διάρκεια της επανάληψης: Sk^b + Vk + F

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

Επιβάρυνση επικοινωνίας:

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

Σε μερικούς αλγόριθμους ο εκθέτης b=1. Σε αυτή την περίπτωση η επιβάρυνση επικοινωνίας προσεγγίζει μια σταθερά καθώς το μέγεθος του επιμερισμού δεδομένων k αυξάνεται:

Επιβάρυνση επικοινωνίας=

Παρά το ότι ο παραπάνω τύπος δεν είναι τόσο καλός όσο ο προηγούμενος, στον οποίο η επιβάρυνση επικοινωνίας εξαλείφεται για μεγάλα k, δίνει μια αποδεκτή επιβάρυνση απόδοσης γιατί η επιτάχυνση αυξάνεται γραμμικά ανάλογα με τον αριθμό των επεξεργαστών. Για p επεξεργαστές, η επιτάχυνση για αυξανόμενο k προσεγγίζει το παρακάτω όριο:

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