Επόμενο:B.11 ΠΕΡΙΛΗΨΗ Πάνω: Παράρτημα Β Πίσω: Β.9 ΑΠΕΙΚΟΝΙΣΗ ΑΠΟΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΟΣ

B.10 ΠΡΟΣΟΜΟΙΩΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΡΧΙΤΕΚΤΟΝΙΚΩΝ

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

Β.10.1. Επιλογή Αρχιτεκτονικής

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

ARCHITECTURE <όνομα αρχιτεκτονικής>(<αριθμός επεξεργαστών>);

Το παρακάτω τμήμα προγράμματος επιλέγει αρχιτεκτονική διαμοιραζόμενης μνήμης με 64 επεξεργαστές.

PROGRAM Sample;
ARCHITECTURE SHARED(64);
CONST size = 100;
VAR x, y, z: INTEGER;
    a: ARRAY [1..10] OF REAL;
...

Τα ονόματα αρχιτεκτονικών που επιτρέπονται από τη Multi-Pascal είναι:

SHARED(n) - σύστημα διαμοιραζόμενης μνήμης με έναν δίαυλο επικοινωνίας και n επεξεργαστές. Όλες οι μεταβλητές είναι αποθηκευμένες στη κύρια μνήμη και προσβάσιμες σε μία χρονική μονάδα. Είναι το βασικό σύστημα του προσομοιωτή με n = 256(ή 512).

LINE(n) - σύστημα κατανεμημένης μνήμης με n επεξεργαστές σε γραμμική διασύνδεση. Οι επεξεργαστές αριθμούνται από το 0 έως το n-1. Συνδεσιμότητα 2 και διάμετρος n-1. Υπάρχει μόνο μία διαδρομή μεταξύ δύο επεξεργαστών.

RING(n) - σύστημα κατανεμημένης μνήμης με n επεξεργαστές σε διασύνδεση δακτυλίου. Οι επεξεργαστές αριθμούνται όπως στη γραμμική διάταξη. Συνδεσιμότητα 2 και διάμετρος (n-1)/2. Επιλέγεται η συντομότερη από τις δύο διαθέσιμες διαδρομές.

MESH2(n) - σύστημα κατανεμημένης μνήμης με n₂ επεξεργαστές σε διασύνδεση δι-διάστατου πλέγματος. Οι επεξεργαστές αριθμούνται κατά σειρά από το 0 έως το n₂-1 ξεκινώντας από την ΒΔ γωνία του πλέγματος. Συνδεσιμότητα 4 και διάμετρος 2n-1. Η διαδρομή που ακολουθείται είναι πρώτα κατα μήκος της γραμμής, μέχρι την σωστή στήλη, και μετά κατα μήκος της στήλης.

TORUS(n) - σύστημα κατανεμημένης μνήμης με n₂ επεξεργαστές σε διασύνδεση διδιάστατου δακτυλίου (τόρος). Οι επεξεργαστές αριθμούνται όπως στο διδιάστατο πλέγμα. Συνδεσιμότητα 4 και διάμετρος (2n-1)/2. Η διαδρομή επιλέγεται όπως στο πλέγμα αλλά λαμβάνονται υπ΄ όψη και οι συνδέσεις δακτυλίου (δύο διαδρομές γιά κάθε γραμμή ή στήλη).

MESH3(n) - σύστημα κατανεμημένης μνήμης με n₃ επεξεργαστές σε διασύνδεση τρισδιάστατου πλέγματος. Οι επεξεργαστές αριθμούνται επίπεδο προς επίπεδο κατά σειρά από το 0 έως το n₃-1 ξεκινώντας από τη ΒΔ γωνία του πρώτου (και κάθε επόμενου επιπέδου). Συνδεσιμότητα 6 και διάμετρος 3n-1. Η διαδρομή σε ένα επίπεδο επιλέγεται όπως στο διδιάστατο πλέγμα και στη συνέχεια η διαδρομή προχωρεί προς την τρίτη διάσταση.

HYPERCUBE(n) - σύστημα κατανεμημένης μνήμης με 2_n επεξεργαστές σε διασύνδεση υπερκύβου διάστασης n. Η αρίθμηση των επεξεργαστών γίνεται με ανάθεση ενός δυαδικού αριθμού με n bits (από 0000..0 έως 1111..1) σε κάθε επεξεργαστή έτσι ώστε γειτονικοί επεξεργαστές διαφέρουν μόνο σε ένα bit. Συνδεσιμότητα n και διάμετρος n. Η διαδρομή επιλέγεται όπως παρακάτω. Έστω A ο δυαδικός αριθμός του αποστολέα ή ενδιάμεσου σταθμού και Β του παραλήπτη. Οι αριθμοί συγκρίνονται bit προς bit από τα δεξιά προς τα αριστερά. Έστω οτι διαφέρουν στο m bit. Τότε το πακέτο στέλνεται στον επεξεργαστή με αριθμό ίδιο με τον Α αλλά με το m bit αλλαγμένο. Η διαδρομή αυτή είναι η ελάχιστη.

FULLCONNECT(n) - σύστημα κατανεμημένης μνήμης με n επεξεργαστές σε πλήρη διασύνδεση. Συνδεσιμότητα n-1 και διάμετρος 1. Η διαδρομή είναι ευθεία αφού υπάρχει ειδική κάθε φορά σύνδεση.

 

Β.10.2 Καθυστέρηση Επικοινωνίας

Εάν επιλέξουμε ως αρχιτεκτονική καποιο σύστημα κατανεμημένης μνήμης τότε η Multi-Pascal επιτρέπει την επιλογή κάποιας τιμής γιά την καθυστέρηση επικοινωνίας D με την εντολή

*DELAY <μονάδες χρόνου>

Eξ ορισμού η καθυστέρηση επικοινωνίας είναι 10 χρονικές μονάδες, αλλά η εντολή

*DELAY 30

θα την θέσει στις 30 μονάδες.

Όταν κατά τη διάρκεια της εκτέλεσης ενός προγράμματος δημιουργείται ένα μήνυμα τεμαχίζεται σε πακέτα που περιέχουν τρία δεδομένα το κάθε πακέτο. Ο χρόνος που απαιτείται γιά την αποστολή μηνύματος με k πακέτα σε απόσταση m επεξεργαστών είναι (m+(k-1)/2)D. Η εξήγηση των υπολογισμών και παραπέρα συζήτηση υπάρχει στο κεφάλαιο 8. Ο υπολογισμός του χρόνου επικοινωνίας με βάση τον παραπάνω τύπο είναι ικανοποιητικός εάν η κυκλοφορία των πακέτων δεν είναι πολύ υψηλή ή είναι τοπική και έτσι δεν δημιουργούνται προβλήματα συμφόρησης. Εάν όμως υπάρχει μεγάλη κυκλοφορία πακέτων σε μεταξύ απομακρυσμένων επεξεργαστών τότε υπάρχουν πρόσθετες καθυστερήσεις. Αυτές οι καθυστερήσεις μπορούν να ληφθούν θπ' όψη από τη Multi-Pascal εάν τεθεί σε ισχύ η επιλογή CONGESTION με την εντολή

*CONGESTION ON

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

Για τον υπολογισμό της καθυστέρησης λόγω συμφόρησης θεωρούμε πρώτα οτι η επικοινωνία μπορεί να επικαλυφθεί με υπολογισμούς. Επίσης οτι κάθε σύνδεσμος έχει ικανότητα ταυτόχρονης αμφίδρομης επικοινωνίας. Η αποστολή των δεδομένων πακέτων είναι σειριακή. Ένα πακέτο καταλαμβάνει χρόνο D/2 στην θύρα αποστολής και D/2 στην θύρα παραλαβής. Σε περίπτωση που υπάρχουν περισσότερα πακέτα σε μία θύρα τότε τίθενται σε μία ουρά. Για λόγους απλότητας η ουρά δεν έχει περιορισμένο μήκος. Η διαδρομή επιλέγεται με τους κανόνες που εξηγήθηκαν στην περιγραφή των αρχιτεκτονικών.

Η επιλογή του υπολογισμού καθυστέρησης από συμφόρηση ακυρώνεται με την εντολή

*CONGESTION OFF

Επειδή ο υπολογισμός της καθυστέρησης λόγω συμφόρησης είναι πολύ χρονοβόρος είναι καλό η εντολή CONGESTION να χρησιμοποιείται μόνο όταν πρέπει να ελεγχθεί αυτή η παράμετρος απόδοσης ενός συστήματος και όχι γενικά. Είναι εξ' άλλου πάντοτε προτιμότερος ο σχεδιασμός παράλληλων προγραμμάτων με περιορισμένες και τοπικές επικοινωνίες αφού αυτά επιτυγχάνουν πολύ καλύτερες αποδόσεις. Η κατάσταση των εντολών DELAY και CONGESTION μπορεί να εμφανιστεί με την εντολή DISPLAY.

Επόμενο:B.11 ΠΕΡΙΛΗΨΗ Πάνω: Παράρτημα Β Πίσω: Β.9 ΑΠΕΙΚΟΝΙΣΗ ΑΠΟΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΟΣ