7.4 Απεικονίσεις πάνω στον Υπερκύβο

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

7.4 Απεικονίσεις πάνω στον Υπερκύβο

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

Η τοπολογία Δακτυλίου είναι και αυτή κατάλληλη για την εκτέλεση αλγορίθμων σωλήνωσης. Η διεργασία σωλήνωσης οργανώνεται στον Δακτύλιο όπως και στην τοπολογία Γραμμής. Η διεργασία σωλήνωσης δεν ταιριάζει φυσικά με τη δομή του Πλέγματος. Όμως, η σωλήνωση μπορεί να απεικονισθεί στο δι-διάστατο Πλέγμα, ώστε οι αντίστοιχες διεργασίες στη σωλήνωση να έχουν απευθείας σύνδεσμο επικοινωνίας μέσα στο Πλέγμα. Αυτό φαίνεται στο σχήμα 7.19, όπου τα βέλη δείχνουν τους αντίστοιχους επεξεργαστές στη σωλήνωση. Αυτή η γραμμική διάταξη των επεξεργαστών στο δι-διάστατο Πλέγμα ονομάζεται και σιγμοειδής διάταξη καθώς είναι αντίθετη από τη διάταξη κατά σειρά γραμμής που παρουσιάστηκε στο σχήμα 7.7. Χρησιμοποιώντας μια παρόμοια τεχνική ρύθμισης, μπορούμε επίσης να εφαρμόσουμε τη δομή δακτυλίου σε ένα Πλέγμα, με την προϋπόθεση ότι το πλήθος των επεξεργαστών είναι το ίδιο.

Η προσαρμογή μια Γραμμής σε ένα Πλέγμα είναι ένα συγκεκριμένο παράδειγμα μιας σημαντικής ιδέας στον προγραμματισμό παράλληλου συστήματος κατανεμημένης μνήμης που ονομάζεται τοπολογική απεικόνιση. Μια τοπολογία X μπορεί να προσαρμοστεί σε μια τοπολογία Y αν υπάρχει συγκεκριμένη αντιστοίχηση των επεξεργαστών που βρίσκονται στην X στους επεξεργαστές που βρίσκονται στην Y, τέτοια ώστε κάθε σύνδεσμος επικοινωνίας της τοπολογίας X να έχει έναν αντίστοιχο σύνδεσμο επικοινωνίας στην Y. Μια τοπολογική απεικόνιση επίσης απαιτεί ότι ο αριθμός των επεξεργαστών στις δυο τοπολογίες να είναι ο ίδιος. Ανάμεσα στις τοπολογίες που παρουσιάστηκαν είναι αλήθεια ότι τοπολογίες χαμηλής συνδεσιμότητας μπορούν να απεικονιστούν σε τοπολογίες υψηλότερης συνδεσιμότητας. Η σημαντικότερη εξαίρεση είναι το τρισδιάστατο Πλέγμα που μπορεί να μην δέχεται απεικόνιση των τοπολογιών Τόρου ή διδιάστατο Πλέγματος. Η πιο σημαντική τοπολογία σχετικά με την απεικόνιση είναι ο Υπερκύβος, γιατί έχει την υψηλότερη συνδεσιμότητα.

ΣΧΗΜΑ 7.19 Απεικόνιση γραμμής σε πλέγμα

Ο Υπερκύβος έχει τη σημαντική ιδιότητα του ότι όλες οι τοπολογίες που παρουσιάστηκαν μπορούν να απεικονιστούν πάνω σε αυτόν, με την προϋπόθεση ότι ο αριθμός των επεξεργαστών είναι ακριβώς δύναμη του 2. Αυτή η προϋπόθεση είναι απαραίτητη γιατί ο αριθμός των επεξεργαστών στον Υπερκύβο είναι πάντα αριθμός της δύναμης του 2.

Στον Υπερκύβο, όπως έχουμε προαναφέρει, κάθε επεξεργαστής συνδέεται απευθείας με όλους τους επεξεργαστές των οποίων οι αριθμοί διαφέρουν ακριβώς κατά ένα δυαδικό ψηφίο. Μια χρήσιμη έννοια σχετικά με τις απεικονίσεις του Υπερκύβου είναι ο Κώδικας Gray. Ο κώδικας Gray είναι μια ακολουθία αριθμών στην οποία ο κάθε διαδοχικός αριθμός διαφέρει από τον προηγούμενό του μόνο κατά ένα ψηφίο. Για παράδειγμα, οι παρακάτω είναι αναπαραστάσεις των αριθμών 0 ως 7 σύμφωνα με τον κώδικα Gray:

000 001 011 010 110 111 101 100

Ο κώδικας Gray μπορεί να χρησιμοποιηθεί για την απεικόνιση μιας τοπολογίας Γραμμής με οκτώ επεξεργαστές σε έναν Υπερκύβο με επίσης οκτώ επεξεργαστές. Εφόσον καθένας από τους αριθμούς σύμφωνα με τον κώδικα Gray διαφέρει από τον προηγούμενο και τον επόμενό του κατά ένα bit, υπάρχει απευθείας σύνδεση στον Υπερκύβο μεταξύ όλων των αντίστοιχων ζευγαριών επεξεργαστών στην παραπάνω ρύθμιση του κώδικα Gray. Με τον τρόπο αυτό δημιουργούν μια τοπολογία Γραμμής. Παρατηρήστε ότι ο τελευταίος αριθμός της παραπάνω ακολουθίας διαφέρει από τον πρώτο μόνο κατά ένα δυαδικό ψηφίο. Έτσι, υπάρχει απευθείας σύνδεση μεταξύ των δυο ακραίων στοιχείων αυτής της γραμμής επεξεργαστών και συνεπώς αποτελούν και μια τοπολογία Δακτυλίου εκτός από τοπολογία Γραμμής.

Η παραπάνω ακολουθία ονομάζεται 3-bit Κώδικας Gray, γιατί κάθε αριθμός αποτελείται από τρία bits. Γενικά, ο k-bit Κώδικας Gray G_k ορίζεται αναδρομικά όπως φαίνεται παρακάτω:

G_k είναι η ακολουθία: 0 1

Για όλα τα k > 1, G_k είναι η ακολουθία που δημιουργείται από τους ακόλουθους κανόνες:

1. Δημιουργείστε μια νέα ακολουθία προσθέτοντας ένα 0 στα αριστερά όλων των μελών του G_k-1.

2. Δημιουργείστε μια νέα ακολουθία αντιστρέφοντας το G_k-1 και μετά προσθέτοντας ένα 1 στα αριστερά όλων των μελών αυτής της ακολουθίας.

3. Το G_k είναι η σύνδεση των ακολουθιών που καθορίστηκαν στα βήματα 1 και 2.

Εφαρμόζοντας αυτούς τους κανόνες στον 3-bit Κώδικα Gray, από το πρώτο βήμα προκύπτει η ακολουθία:

0000 0001 0011 0010 0110 0111 0101 0100

Το βήμα 2 καταλήγει στην ακολουθία:

1100 1101 1111 1110 1010 1011 1001 1000

Συνδέοντας αυτές τις δύο ακολουθίες έχουμε τον 4-bit Κώδικα Gray. Παρατηρήστε ότι κάθε αριθμός στην ακολουθία διαφέρει από τους γείτονες του ακριβώς κατά ένα bit. Έτσι, αυτός ο Κώδικας Gray μπορεί να χρησιμοποιηθεί για να απεικονιστεί μια τοπολογία Γραμμής ή Δακτυλίου με 16 επεξεργαστές σε ένα Υπερκύβο με διάσταση 4, όπως φαίνεται παρακάτω

0000 - 0001 - 0011 - 0010 - 0110 - 0111 - 0101 - 0100

1000 - 1001 - 1011 - 1010 - 1010 - 1111 - 1101 - 1100

Παρατηρήστε ότι στην παραπάνω στοίχιση υπάρχει επίσης και κάθετη σχέση μεταξύ των αριθμών των επεξεργαστών. Όλα τα ζευγάρια των επεξεργαστών που σχηματίζονται μεταξύ της επάνω και της κάτω ακολουθίας διαφέρουν επίσης κατά ένα bit και συνεπώς συνδέονται στην τοπολογία Υπερκύβου. Τοποθετώντας τον ίδιο 4-bit Κώδικα Gray σε τέσσερις γραμμές και τέσσερις στήλες μπορούμε να δημιουργήσουμε μια τοπολογία δι-διάστατο Πλέγματος όπως φαίνεται και στο σχήμα 7.20. Τα βέλη στο σχήμα δηλώνουν την ακολουθία του Κώδικα Gray. Κάθε επεξεργαστής σε αυτή την κατασκευή διαφέρει από όλους τους άμεσους γείτονες του κατά ένα bit ακριβώς. Με αυτόν τον τρόπο κάθε επεξεργαστής στον Υπερκύβο έχει απευθείας φυσική σύνδεση με όλους τους άμεσους γείτονες του στο πλέγμα που σχηματίζεται. Αυτή η σιγμοειδής διάταξη της ακολουθίας του Κώδικα Gray μπορεί να χρησιμοποιηθεί για την απεικόνιση κάθε δι-διάστατου Πλέγματος σε μια τοπολογία Υπερκύβου με τον ίδιο αριθμό επεξεργαστών. Για ένα mxm Πλέγμα, ο αριθμός των επεξεργαστών είναι m² και συνεπώς η διάσταση του Υπερκύβου πρέπει να είναι 2logm.

ΣΧΗΜΑ 7.20 Απεικόνιση πλέγματος 4 x 4 σε υπερκύβο

Η κατασκευή του σχήματος 7.20 ορίζει επίσης και έναν 4x4 Τόρο, γιατί όλοι οι επεξεργαστές που βρίσκονται στα άκρα διαφέρουν ακριβώς κατά ένα bit. Εφαρμόζοντας τη σιγμοειδή διάταξη του Κώδικα Gray, είναι δυνατόν να απεικονιστεί κάθε διδιάστατο Πλέγμα ή Τόρος σε μια τοπολογία Υπερκύβου με τον ίδιο αριθμό επεξεργαστών, με την προϋπόθεση ότι το πλήθος των επεξεργαστών είναι αριθμός δύναμης του δύο. Για τη δημιουργία των απεικονίσεων πρώτα υπολογίζουμε την ρύθμιση του Κώδικα Gray για όλους του επεξεργαστές του Υπερκύβου. Κατόπιν διασπάμε την ακολουθία του Κώδικα Gray σε μια δι-διάστατη σιγμοειδή διάταξη που έχει ίδιο αριθμό γραμμών και στηλών. Το αποτέλεσμα που προκύπτει έχει όλες τις απαραίτητες συνδέσεις για ένα δι-διάστατο Πλέγμα ή έναν Τόρο.

Η επιτυχία αυτής της μεθόδου βασίζεται στον αναδρομικό ορισμό του Κώδικα Gray. Ο κώδικας δημιουργείται με τη συνεχή αναστροφή και το διπλασιασμό του ίδιου προτύπου και μετά με την πρόσθεση ενός 0 ή 1 για το διαχωρισμό του αρχικού από το αντίγραφο. Με τον τρόπο αυτό μια ακολουθία Κώδικα Gray της μορφής p₁, p₂, … , p_n καθορίζει την επόμενη ακολουθία του Κώδικα Gray με το διπλάσιο μήκος

0p₁, 0p₂, … , 0p_n, 1p_n, 1p_n-1, … , 1p₁

Αν αυτή η ακολουθία αναδιπλωθεί τότε το αποτέλεσμα είναι το ακόλουθο:

****σχήμα σελίδας 177****

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

Αυτή η σιγμοειδής διάταξη του Κώδικα Gray μπορεί επίσης να χρησιμοποιηθεί για την εφαρμογή ενός τρισδιάστατου Πλέγματος σε έναν Υπερκύβο με τον ίδιο αριθμό επεξεργαστών. Η διάταξη μεταφέρει κάτω το μπροστά επίπεδο του τρισδιάστατου Πλέγματος όπως και με το διδιάστατο Πλέγμα, στη συνέχεια προχωράει προς το δεύτερο χρησιμοποιώντας το ίδιο σιγμοειδές πρότυπο, αλλά κινούμενο προς την αντίθετη κατεύθυνση. Αφού φτάσει την κορυφή του δεύτερου επιπέδου προχωράει προς το τρίτο, το τέταρτο κ.τ.λ. Με αυτόν τον τρόπο μια απλή διάταξη Κώδικα Gray όλων των επεξεργαστών σε κάθε Υπερκύβο μπορεί να χρησιμοποιηθεί για την απεικόνιση ενός τρισδιάστατου Πλέγματος με το ίδιο πλήθος επεξεργαστών. Αυτή η τεχνική φαίνεται στο σχήμα 7.21, όπου ένα 4x4x4 τρισδιάστατο Πλέγμα απεικονίζεται σε έναν Υπερκύβο διάστασης 6.

ΣΧΗΜΑ 7.21 Απεικόνιση τρισ-διάστατου πλέγματος σε υπερκύβο

Η παράγραφος αυτή έδειξε ότι με την τεχνική διάταξης του Κώδικα Gray μπορούν όλες οι τοπολογίες που αναφέρθηκαν, δηλαδή η Γραμμή, ο Δακτύλιος, το διδιάστατο Πλέγμα, ο Τόρος και το τρισδιάστατο Πλέγμα, να απεικονιστούν στην τοπολογία του Υπερκύβου. Έτσι, κάθε αλγόριθμος που έχει μια λογική δομή επικοινωνίας η οποία αντιστοιχεί σε οποιαδήποτε από τις τοπολογίες θα εκτελεστεί το ίδιο αποτελεσματικά σε έναν Υπερκύβο με τον ίδιο αριθμό επεξεργαστών. Αν ο αλγόριθμος περιλαμβάνει κάποιες γενικές λειτουργίες επικοινωνίας, όπως είναι η συλλογή και η διάδοση, τότε οι επιπλέον συνδέσεις του Υπερκύβου θα επιτρέψουν πιο αποδοτική εκτέλεση σε σύγκριση με τις άλλες τοπολογίες. Το μειονέκτημα του Υπερκύβου είναι ότι το κόστος της επικοινωνίας του δικτύου αυξάνεται με το λογάριθμο του αριθμού των επεξεργαστών, ενώ σε όλες τις άλλες τοπολογίες το κόστος είναι σταθερό.