7.2 Τοπολογίες Συστημάτων Κατανεμημένης Μνήμης

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

7.2 Τοπολογίες Συστημάτων Κατανεμημένης Μνήμης

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

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

7.2.1 Τοπολογία Γραμμής και Δακτυλίου

Σε μια τοπολογία Γραμμής οι επεξεργαστές συνδέονται με μια ευθεία γραμμή, όπως φαίνεται και στο σχήμα 7.5. Στο σχήμα υποθέτουμε ότι κάθε αριθμημένος κύκλος περιέχει έναν επεξεργαστή, μνήμη και διεπαφή επικοινωνίας. Κάθε γραμμή μεταξύ δυο κύκλων αναπαριστάνει ένα σύνδεσμο επικοινωνίας διπλής κατεύθυνσης. Η λεπτομερής εσωτερική δομή κάθε στοιχείου του δικτύου παραλείπεται από το διάγραμμα αυτής της τοπολογίας και από όλα όσα ακολουθούν. Στα διαγράμματα θα φαίνονται μόνο αριθμημένοι κύκλοι και γραμμές που τους συνδέουν. Εφόσον οι επεξεργαστές είναι η αφετηρία και ο προορισμός κάθε μηνύματος θα αναφερόμαστε σε “επικοινωνία” και σε “συνδέσεις” μεταξύ των επεξεργαστών. Όταν χρησιμοποιούνται αυτοί οι όροι εννοούμε ότι στην πραγματικότητα έχουμε διεπαφές επικοινωνίας που είναι φυσικά συνδεδεμένες και επικοινωνούν φυσικά.

ΣΧΗΜΑ 7.5 Τοπολογία Γραμμής

Όταν δυο επεξεργαστές συνδέονται απευθείας μεταξύ τους σε μια δεδομένη τοπολογία, τότε ονομάζονται γειτονικοί επεξεργαστές. Για να συγκρίνουμε τα σχετικά χαρακτηριστικά απόδοσης διαφορετικών τοπολογιών υποθέτουμε ότι η βασική καθυστέρηση επικοινωνίας μεταξύ των γειτονικών επεξεργαστών είναι η ίδια για όλες τις τοπολογίες. Έτσι, η σχετική απόδοση εξαρτάται από την απόσταση μεταξύ των επεξεργαστών. Η απόσταση ανάμεσα σε δυο επεξεργαστές σε μια δοσμένη τοπολογία καθορίζεται ως ο αριθμός των συνδέσμων που πρέπει να διασχίσει ένα μήνυμα για να μεταφερθεί από τον ένα επεξεργαστή στον άλλο. Η διάμετρος μιας τοπολογίας ορίζεται ως η μέγιστη απόσταση μεταξύ οποιονδήποτε επεξεργαστών στο δίκτυο. Στην τοπολογία Γραμμής του σχήματος 7.5 με τους οκτώ επεξεργαστές η διάμετρος είναι 7. Γενικά, σε μια τοπολογία γραμμής με n επεξεργαστές η συνδεσιμότητα είναι 2 και η διάμετρος n-1. Η απόσταση μεταξύ δυο οποιονδήποτε επεξεργαστών i και j είναι πάντα | i-j|. Αν η βασική καθυστέρηση επικοινωνίας για δυο συνεχόμενους επεξεργαστές είναι T, τότε ο χρόνος που απαιτείται για την αποστολή ενός μηνύματος από τον επεξεργαστή i στον επεξεργαστή j είναι απλώς T|i-j|.

Χωρίς αύξηση του κόστους η απόδοση της τοπολογίας Γραμμής μπορεί να αυξηθεί πάρα πολύ απλά με την πρόσθεση ενός επιπλέον συνδέσμου από από τον πρώτο προς τον τελευταίο επεξεργαστή της γραμμής. Αυτή η τοπολογία ονομάζεται Δακτύλιος και φαίνεται στο σχήμα 7.6. Αυτή η επιπλέον σύνδεση μειώνει στο μισό τη μέση απόσταση μεταξύ των επεξεργαστών. Μια τοπολογία Δακτυλίου με n επεξεργαστές έχει διάμετρο n/2, ενώ όπως είδαμε και προηγουμένως η τοπολογία Γραμμής για τον ίδιο αριθμό επεξεργαστών είναι n-1. Στο σχήμα 7.6 η μέγιστη απόσταση είναι μεταξύ επεξεργαστών που βρίσκονται σε ακριβώς αντίθετες θέσεις πάνω στον Δακτύλιο. Έτσι, ένα μήνυμα πρέπει να διασχίσει μόνο τη μισή απόσταση γύρω από τον Δακτύλιο, ενώ στην τοπολογία Γραμμής για να κινηθεί ένα μήνυμα από τον επεξεργαστή 0 στον 7 έπρεπε να περάσει από όλους τους συνδέσμους του δικτύου.

ΣΧΗΜΑ 7.6 Τοπολογία Δακτυλίου

7.2.2 Τοπολογία Πλέγματος

Με την αύξηση του αριθμού των συνδέσμων επικοινωνίας που είναι συνδεδεμένοι σε κάθε επεξεργαστή μπορούμε να μειώσουμε τη διάμετρο του δικτύου και τη μέση καθυστέρηση επικοινωνίας. Μία τέτοια τοπολογία είναι το διδιάστατο Πλέγμα, που φαίνεται και στο σχήμα 7.7. Αυτή η τοπολογία αποτελείται από επεξεργαστές που είναι οργανωμένοι σε έναν πίνακα δύο διαστάσεων. Ένας επεξεργαστής που βρίσκεται στη γραμμή i και στην στήλη j συνδέεται με τους τέσσερις άμεσους γείτονες του στα αριστερά, δεξιά, επάνω και κάτω σε απόσταση: (i-1,j), (i+1,j), (i,j-1) και (i,j+1) αντίστοιχα. Οι συνδέσεις είναι είτε οριζόντιες μεταξύ των συνεχόμενων στηλών είτε κάθετες μεταξύ των συνεχόμενων γραμμών, όπως φαίνεται και στο σχήμα 7.7. Δεν υπάρχουν διαγώνιες συνδέσεις. Οι επεξεργαστές που βρίσκονται στα όρια έχουν μόνο δυο ή τρεις άμεσους γείτονες.

ΣΧΗΜΑ 7.7 Τοπολογία Δι-διάστατου Πλέγματος

Στο σχήμα 7.7 οι επεξεργαστές αριθμούνται ακολουθιακά κατά γραμμές, με τον επεξεργαστή 0 στην άνω αριστερή γωνία. Αυτή η μορφή αρίθμησης ονομάζεται κατά σειρά γραμμής. Τα μηνύματα που ταξιδεύουν μεταξύ απομακρυσμένων επεξεργαστών πρέπει να κινούνται κατά μήκος των οριζόντιων ή των κάθετων μονοπατιών μεταξύ των επεξεργαστών. Για παράδειγμα, ένα μήνυμα που κατευθύνεται από τον επεξεργαστή 6 στον 13 θα κινηθεί πρώτα στον επεξεργαστή 11, μετά στον 12 και τέλος στον 13: απαιτούνται συνολικά δηλαδή τρία βήματα. Το μήνυμα μπορεί επίσης να ακολουθήσει εναλλακτικά τα μονοπάτια 6-7-8-13 ή 6-7-12-13 και πάλι όμως ο αριθμός των βημάτων είναι 3. Κάθε ζεύγος των επεξεργαστών έχει ένα ελάχιστο μήκος μονοπατιού που τους συνδέει και που υπολογίζεται από το άθροισμα των αποστάσεων γραμμής και στήλης. Αν η βασική καθυστέρηση επικοινωνίας για τους συνεχόμενους επεξεργαστές είναι T τότε ο χρόνος επικοινωνίας μεταξύ επεξεργαστών για κάθε ξεχωριστό ζευγάρι είναι απλά το μήκος του μονοπατιού τους πολλαπλασιασμένο επί T. Για ένα Πλέγμα mxm η διάμετρος του δικτύου είναι απλά το μήκος μονοπατιού μεταξύ των επεξεργαστών που βρίσκονται στις αντίθετες γωνίες του Πλέγματος και είναι πάντα 2(m-1).

Σε μια τοπολογία Πλέγματος, η κάθε γραμμή και η κάθε στήλη έχει την τοπολογία Γραμμής. Ακριβώς όπως η τοπολογία Γραμμής βελτιώνεται με την πρόσθεση ενός επιπλέον συνδέσμου που την μετέτρεπε σε τοπολογία Δακτυλίου, έτσι και η απόδοση του Πλέγματος μπορεί να βελτιωθεί αν προσθέσουμε κάποιες επιπλέον συνδέσεις σε κάθε γραμμή και στήλη. Με τον τρόπο αυτό κάθε γραμμή και κάθε στήλη θα μετατραπεί από Γραμμή σε Δακτύλιο. Αυτό φαίνεται στο σχήμα 7.8. Κάθε επεξεργαστής στο αριστερό όριο του Πλέγματος συνδέεται με το ταίρι του που βρίσκεται στο δεξί όριο. Όμοια κάθε επεξεργαστής που βρίσκεται στο άνω όριο συνδέεται με τον αντίστοιχο που βρίσκεται στο κάτω όριο. Αυτή η τοπολογία ονομάζεται Τόρος. Η συνδεσιμότητα κάθε τέτοιας τοπολογίας Τόρου είναι πάντα 4, εφόσον κάθε επεξεργαστής έχει τώρα τέσσερις συνδέσμους. Ακριβώς όπως όταν η τοπολογία Γραμμής αλλάζει σε Δακτύλιο και μειώνεται η διάμετρος στο μισό, έτσι βελτιώνεται και η απόδοση όταν το Πλέγμα μετατρέπεται σε Τόρο μετά την πρόσθεση των επιπλέον συνδέσεων. Οι επεξεργαστές που βρίσκονται σε αντίθετες θέσεις χωρίζονται τώρα από μια απόσταση ίση με 2. Η μέγιστη απόσταση σε έναν Τόρο είναι ανάμεσα στον επεξεργαστή που βρίσκεται στην γωνία και αυτόν που βρίσκεται στο κέντρο. Έτσι, μια mxm τοπολογία Τόρου έχει διάμετρο m.

ΣΧΗΜΑ 7.8 Τοπολογία Τόρου

Το πρότυπο του Πλέγματος μπορεί να επεκταθεί σε τρεις διαστάσεις, όπως φαίνεται και στο σχήμα 7.9. Μια τοπολογία Πλέγματος τριών διαστάσεων μπορεί να θεωρηθεί ως μια σειρά από διδιάστατα πλέγματα, το ένα πίσω από το άλλο και με συνδέσεις μεταξύ των αντίστοιχων επεξεργαστών στα διδιάστατα γειτονικά πλέγματα. Το κάθε ένα από τα διδιάστατα πλέγματα ονομάζεται επίπεδο. Η θέση κάθε επεξεργαστή στο τρισδιάστατο Πλέγμα θα έχει τρεις συντεταγμένες (i,j,k), όπου i είναι ο αριθμός της γραμμής, j ο αριθμός της στήλης και k ο αριθμός επιπέδου. Όπως και στην τοπολογία Πλέγματος δύο διαστάσεων, έτσι και εδώ κάθε επεξεργαστής έχει απευθείας συνδέσεις στους τέσσερις άμεσους γείτονές του στο ίδιο επίπεδο. Επιπλέον, κάθε επεξεργαστής είναι απευθείας συνδεδεμένος με τον αντίστοιχο επεξεργαστή που βρίσκεται στο μπροστά και πίσω επίπεδο. Για παράδειγμα, ένας επεξεργαστής με συντεταγμένες (i,j,k) έχει έξι απευθείας συνδέσεις με τους ακόλουθους επεξεργαστές: (i-1,j,k), (i+1,j,k), (i,j+1,k), (i,j-1,k), (i,j,k-1) και (i,j,k+1). Οι επεξεργαστές που βρίσκονται στα όρια του πλέγματος θα έχουν λιγότερες από έξι απευθείας συνδέσεις (είτε τέσσερις ή πέντε). Ένα τρισδιάστατο Πλέγμα με m³ επεξεργαστές έχει διάμετρο 3(m-1).

ΣΧΗΜΑ 7.9 Τοπολογία Τρισ-διάστατου Πλέγματος

7.2.3 Τοπολογία Υπερκύβου

Στην τοπολογία διασύνδεσης Υπερκύβου, ο αριθμός των επεξεργαστών είναι πάντα ακριβώς δύναμη του 2. Αν ο αριθμός των επεξεργαστών είναι 2^d, τότε το d ονομάζεται διάσταση του υπερκύβου. Κάθε επεξεργαστής θα έχει έναν αριθμό του οποίου η αναπαράσταση στο δυαδικό σύστημα έχει d bits. Ο ορισμός του σχήματος διασύνδεσης του Υπερκύβου είναι: κάθε επεξεργαστής με δυαδικό αριθμό i έχει απευθείας συνδέσεις με όλους τους επεξεργαστές που έχουν δυαδικό αριθμό j, έτσι ώστε το j να διαφέρει από το i ακριβώς κατά ένα δυαδικό ψηφίο. Για παράδειγμα, ένας υπερκύβος με d=3 θα έχει οκτώ επεξεργαστές που είναι αριθμημένοι ως εξής 000, 001, 010, 011, 100, 101, 110, 111. Ο επεξεργαστής 000 θα έχει απευθείας συνδέσεις με τους ακόλουθους επεξεργαστές: 001, 010, 100. Ο επεξεργαστής 011 θα έχει απευθείας συνδέσεις με τους επεξεργαστές: 111, 001, 010.

Το σχήμα 7.10 παρουσιάζει έναν Υπερκύβο με διάσταση d=3. Για αυτή την μικρή διάσταση, ο υπερκύβος μοίαζει ίδιος με την τοπολογία τρισ-διάστατου πλέγματος. Όμως για μεγαλύτερες διαστάσεις η δομή του Υπερκύβου είναι διαφορετική. Σε ένα Πλέγμα κάθε επεξεργαστής έχει καθορισμένο αριθμό συνδέσεων, που είναι ανεξάρτητες από το μέγεθος του Πλέγματος. Στον Υπερκύβο ο αριθμός των συνδέσεων για κάθε επεξεργαστή αυξάνεται ανάλογα με την αύξηση του αριθμού των επεξεργαστών.

ΣΧΗΜΑ 7.10 Τοπολογία Υπερκύβου με διάσταση 3

Σε έναν Υπερκύβο ο αριθμός των απευθείας συνδέσεων για κάθε επεξεργαστή είναι πάντα ίδιος με τη διάσταση του Υπερκύβου. Το σχήμα 7.11 παρουσιάζει την τοπολογία ενός Υπερκύβου με 16 επεξεργαστές και διάσταση 4. Παρατηρείστε ότι κάθε επεξεργαστής έχει 4 συνδέσεις σε άλλους επεξεργαστές, ενώ στο σχήμα 7.10 κάθε επεξεργαστής συνδέεται απαυθείας με 3 μόνο επεξεργαστές. Ένας Υπερ κύβος με 128 επεξεργαστές έχει διάσταση 7, και συνεπώς κάθε επεξεργαστής έχει 7 απευθείας συνδέσεις. Οι επιπλέον συνδέσεις σε έναν Υπερκύβο με μεγάλη διάσταση θα μειώσουν τη μέση καθυστέρηση της επικοινωνίας, σε σύγκριση με την τοπολογία πλέγματος.

Η απόσταση μεταξύ των επεξεργαστών σε έναν Υπερκύβο είναι ακριβώς ίδια με τον αριθμό των θέσεων bit κατά τον οποίο διαφέρουν οι αριθμοί τους. Για παράδειγμα, στο σχήμα 7.10 ο επεξεργαστής 000 είναι δύο βήματα μακριά από τον επεξεργαστή 011. Για να επικοινωνήσει ο επεξεργαστής 000 με τον 011, θα στείλει πρώτα το μήνυμά του στον ενδιάμεσο γείτονά τους 001, ο οποίος με τη σειρά του θα προωθήσει το μήνυμα στον άμεσο γείτονά του 011. Συνεπώς η συνολική διαδικασία της επικοινωνίας από τον 000 στον 011 απαιτεί δύο βήματα. Για d=3, κάθε επεξεργαστής έχει τρεις άμεσους γείτονες και η μέγιστη απόσταση μεταξύ επεξεργαστών είναι τρία βήματα. Γενικά, για έναν Υπερκύβο με διάσταση d, οι επεξεργαστές θα έχουν d άμεσους συνδέσμους και η μέγιστη απόσταση μεταξύ επεξεργαστών είναι d βήματα. Έτσι, η συνδεσιμότητα του δικτύου είναι d και η διάμετρος του δικτύου είναι πάλι d.

ΣΧΗΜΑ 7.11 Τοπολογία Υπερκύβου με διάσταση 4

Μια τοπολογία Υπερκύβου μπορεί να καθοριστεί με τον απλό αναδρομικό κανόνα κατασκευής. Ένας Υπερκύβος με διάσταση 1 ορίζεται ότι έχει δύο επεξεργαστές με αριθμούς 0 και 1 και μια απλή απευθείας σύνδεση μεταξύ τους. Ένας Υπερκύβος διάστασης d+1 ορίζεται αναδρομικά από την ακόλουθη διαδικασία κατασκευής:

Δημιουργείστε ένα ακριβές αντίγραφο του Υπερκύβου με διάσταση d, συμπεριλαμβάνοντας και τους αριθμούς των επεξεργαστών.

Δημιουργείστε απευθείας σύνδεση μεταξύ των επεξεργαστών που έχουν τους ίδιους αριθμούς με το αρχικό και το αντίγραφο.

Προσαρτήστε ένα δυαδικό 1 στα αριστερά του αριθμού κάθε επεξεργαστή στο αντίγραφο και ένα δυαδικό 0 στα αριστερά του αριθμού κάθε επεξεργαστή στο αρχικό.

Αυτή η αναδρομική κατασκευή παρουσιάζεται για τις διαστάσεις 1-3 στο σχήμα 7.12. Για την δημιουργία ενός Υπερκύβου διάστασης 4, ο κανόνας λέει να αντιγράψουμε το πρότυπο για τη διάσταση 3 και να συνδέσουμε τις αντίστοιχες θέσεις στο αρχικό και το αντίγραφο. Αυτό έχει ήδη παρουσιαστεί στο σχήμα 7.11. Αυτός ο αναδρομικός κανόνας κατασκευής του Υπερκύβου μας δείχνει την εσωτερική δομή του πράγμα που θα φανεί ιδιαίτερα χρήσιμο αργότερα στο σχεδιασμό αποτελεσματικών αλγορίθμων για την εκτέλεση παράλληλων συστημάτων κατανεμημένης μνήμης Υπερκύβου.

ΣΧΗΜΑ 7.12 Αναδρομική κατασκευή Υπερκύβου

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

Τοπολογία Συνδεσιμότητα Διάμετρος

Γραμμή 2 n-1

Δακτύλιος 2 n/2

2-D Πλέγμα 2-4 2(n^1/2-1)

Τόρος 4 n^1/2

3-D Πλέγμα 3-6 3(n^1/3-1)

Υπερκύβος log n log n