Επόμενο: 3.5 Η Επίδραση του Αλγορίθμου Πάνω: Κεφάλαιο 3ο :Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω:3.3 Πολλαπλά Τμήματα Μνήμης

3.4 Δίκτυα διασύνδεσης Επεξεργαστή - Μνήμης.

Οι ιδιότητες του ανταγωνισμού πρόσβασης στη μνήμη που παρουσιάστηκαν για τα συστήματα διαμοιραζόμενης μνήμης, εξαρτώνται επίσης και από τον χαρακτήρα του δικτύου διασύνδεσης επεξεργαστή - μνήμης. Αναφερόμενοι στο γενικό διάγραμμα αρχιτεκτονικής του Σχήματος 1.2, η διαίρεση της διαμοιραζόμενης μνήμης στα πολλαπλά τμήματα μνήμης μειώνει αρκετά την πιθανότητα ανταγωνισμού. Όμως μπορεί να εμφανιστεί συμφόρηση στην σύνδεση υλικού, ακόμα και όταν οι επεξεργαστές αναφέρονται σε διαφορετικά τμήματα μνήμης. Έχουν γίνει πάρα πολλές θεωρητικές και πρακτικές έρευνες για τον σχεδιασμό του δικτύου διασύνδεσης επεξεργαστή - μνήμης στα συστήματα διαμοιραζόμενης μνήμης [Siegel, 1984].

Στο Σχήμα 3.6 το ραβδεπαφικό δίκτυο συνδέει οκτώ επεξεργαστές με οκτώ τμήματα μνήμης. Κάθε τμήμα μνήμης μπορεί να εξυπηρετήσει μόνο μια αίτηση σε κάθε δεδομένη στιγμή. Επομένως, ταυτόχρονες αιτήσεις από πολλούς επεξεργαστές, στο ίδιο τμήμα μνήμης, θα προκαλέσουν ανταγωνισμό. Όμως το ραβδεπαφικό δίκτυο έχει μια σημαντική ιδιότητα, σύμφωνα με την οποία δεν εμφανίζεται ποτέ ανταγωνισμός στο δίκτυο διασύνδεσης. Το ραβδεπαφικό δίκτυο μπορεί να συνδέει όλους τους επεξεργαστές ταυτόχρονα σε διαφορετικές μνήμες. Οι μεταγωγείς μπορούν να ρυθμιστούν, έτσι ώστε να επιτρέπουν σε οποιοδήποτε πιθανό πρότυπο σύνδεσης επεξεργαστή - μνήμης να υπάρχουν ταυτόχρονα, εξασφαλίζοντας φυσικά, ότι οι επεξεργαστές δεν αναφέρονται στο ίδιο τμήμα μνήμης. Αυτό συμβαίνει επειδή κάθε ζευγάρι επεξεργαστή - μνήμης έχει το δικό του μεταγωγέα στην ράβδο. Έτσι, για n επεξεργαστές και n τμήματα μνήμης απαιτούνται n² μεταγωγείς, και επομένως το δίκτυο έχει κόστος O(n²).

ΣΧΗΜΑ 3.6 Ραβδεπαφικό δίκτυο επεξεργαστή - μνήμης

Για ένα μεγάλο αριθμό επεξεργαστών, το κόστος O(n²) του δικτύου μπορεί να είναι απαγορευτικά μεγάλο. Για να μειωθεί το κόστος δίκτυα έχουν αναπτυχθεί δίκτυα κόστους O(n log n), όπως το δίκτυο πεταλούδας (butterfy), που παρουσιάζεται στο Σχήμα 3.7. Σε αυτό το δίκτυο, κάθε επεξεργαστής έχει ένα μονοπάτι για κάθε τμήμα μνήμης. Όμως, μερικά μονοπάτια συγκρούονται μεταξύ τους, έτσι ώστε ο ανταγωνισμός στους μεταγωγείς σύνδεσης να μπορεί να συμβεί ακόμα και όταν οι επεξεργαστές αναφέρονται σε διαφορετικά τμήματα μνήμης. Το δίκτυο πεταλούδας παίρνει το όνομα του από τα “φτερά πεταλούδας” που εμφανίζονται σε κάθε επίπεδο του δικτύου. Σε κάθε διαδοχικό επίπεδο του δικτύου από τα αριστερά προς τα δεξιά, τα φτερά πεταλούδας αυξάνονται με συντελεστή δύο. Γενικά, ο αριθμός των επιπέδων που απαιτείται για n επεξεργαστές είναι log n, με κάθε επίπεδο να έχει συνολικά n/20 μεταγωγούς. Επομένως, ο συνολικός αριθμός μεταγωγέων που απαιτούνται είναι (n/2)log n. Στο Σχήμα 3.7, 16 επεξεργαστές συνδέονται με 16 τμήματα μνήμης και χρησιμοποιούνται 32 μεταγωγείς. Το ραβδεπαφικό δίκτυο για τόσους επεξεργαστές και μνήμες θα απαιτούνται 16^.16=256 μεταγωγείς.

ΣΧΗΜΑ 3.7 Δίκτυο Πεταλούδας

Ένα άλλο δίκτυο μεταγωγής που έχει κόστος O(n log n) είναι το δίκτυο διαπλοκής - εναλλαγής (shuffle-exchange) που παρουσιάζεται στο Σχήμα 3.8. Αυτό το δίκτυο ονομάζεται έτσι επειδή το πρότυπο σύνδεσης σε κάθε επίπεδο μοιάζει με το μοίρασμα τράπουλας. Όπως και στο δίκτυο πεταλούδας το δίκτυο διαπλοκής - εναλλαγής, έχει πολλά μονοπάτια ανάμεσα στους επεξεργαστές και στις μνήμες, που επιτρέπουν να εξυπηρετούνται ταυτόχρονα πολλές παράλληλες προσπελάσεις μνήμης από τους επεξεργαστές. Επίσης, όπως και στο δίκτυο πεταλούδας, έτσι και στο δίκτυο διαπλοκής - εναλλαγής, είναι πιθανόν να εμφανιστεί ανταγωνισμός σε ένα μεταγωγέα, ακόμα και όταν οι επεξεργαστές αναφέρονται σε διαφορετικά τμήματα μνήμης. Αυτός ο ανταγωνισμός μέσα στους μεταγωγείς δεν εμφανίζεται στο ραβδεπαφικό δίκτυο, που όμως έχει μεγαλύτερο κόστος.

ΣΧΗΜΑ 3.8 Δίκτυο Διαπλοκής - Εναλλαγής

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

Επόμενο:3.5 Η Επίδραση του Αλγορίθμου Πάνω: Κεφάλαιο 3ο :Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω:3.3 Πολλαπλά Τμήματα Μνήμης