Επόμενο:8.4 Καθυστέρηση Επικοινωνίας Πάνω: Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πίσω: 8.2 Γλωσσική Υποστήριξη Προγραμματισμού Περάσματος Μηνυμάτων

8.3 Προγράμματα Διασωλήνωσης σε Συστήματα Κατανεμημένης Μνήμης

Τώρα που έχουμε περιγράψει όλα τα χαρακτηριστικά της Multi-Pascal για την υποστήριξη του προγραμματισμού στα συστήματα κατανεμημένης μνήμης, μπορούμε να εξετάσουμε κάποια παραδείγματα. Τα προγράμματα διασωλήνωσης που περιγράψαμε στο κεφάλαιο 4 χρησιμοποιούν ένα είδος περάσματος μηνυμάτων, παρά το ότι έχουν γραφεί για εκτέλεση σε συστήματα διαμοιραζόμενης μνήμης. Σε αυτά τα προγράμματα οι διεργασίες αλληλεπιδρούν μεταξύ τους στέλνοντας μηνύματα μέσω των καναλιών. Αυτή η επικοινωνία υλοποιείται με έναν πίνακα καναλιών που δηλώνεται στην αρχή του κυρίως προγράμματος. Η διεργασία i της διασωλήνωσης δέχεται μηνύματα από το κανάλι i του πίνακα και στέλνει δεδομένα στο γείτονα που βρίσκεται στα δεξιά της μέσα από το κανάλι i+1. Αυτή η γενική δομή των προγραμμάτων διασωλήνωσης παρουσιάστηκε στο σχήμα 4.5.

Καθένα από αυτά τα προγράμματα διασωλήνωσης μετατρέπεται εύκολα σε πρόγραμμα περάσματος μηνυμάτων που είναι κατάλληλο για εκτέλεση σε συστήματα κατανεμημένης μνήμης. Στο παρόν κεφάλαιο παρουσιάζονται τρία προγράμματα διασωλήνωσης: Ταξινόμηση με Εισαγωγή σε αυτή την παράγραφο, Ταξινόμηση με Ανταλλαγή στις προγραμματιστικές εργασίες και Προς τα Πίσω Αντικατάσταση στις ασκήσεις. Σε ένα πρόγραμμα διασωληνωμένης Ταξινόμησης με Ανταλλαγή η κύρια διεργασία στέλνει τα δεδομένα, ένα κάθε φορά, στη διασωλήνωση. Καθώς κάθε διεργασία λαμβάνει τα δεδομένα από τον αριστερό γείτονά της, κρατάει πάντα τη μικρότερη τιμή που έχει λάβει μέχρι στιγμής και στέλνει όλες τις άλλες τιμές στον δεξιό γείτονά της. Χρησιμοποιώντας μια αρχική λίστα με n τιμές δεδομένων και n διεργασίες, αυτός ο αλγόριθμος έχει ως αποτέλεσμα μια ταξινομημένη λίστα με κάθε i διεργασία κρατάει το i-οστο δεδομένο.

Το πρόγραμμα της ταξινόμησης με εισαγωγή για σύστημα κατανεμημένης μνήμης με πλήρως συνδεδεμένη τοπολογία φαίνεται στο σχήμα 8.5. Εφόσον η πλήρως συνδεδεμένη τοπολογία έχει έναν απευθείας σύνδεσμο επικοινωνίας για κάθε ζεύγος επεξεργαστών δεν είναι ιδιαίτερα πρακτική για συστήματα κατανεμημένης μνήμης. Όμως, είναι χρήσιμη σαν ένα ιδεατό μοντέλο για να βοηθήσει στον υπολογισμό των χαρακτηριστικών απόδοσης του προγράμματος. Όπως περιγράφεται και στο Παράρτημα, η συγκεκριμένη αρχιτεκτονική καθορίζεται με τη λέξη κλειδί ARCHITECTURE στην αρχή του προγράμματος. Σε αυτή την περίπτωση έχουμε ένα πλήρως συνδεδεμένο σύστημα κατανεμημένης μνήμης με 101 επεξεργαστές.

Παρατηρείστε στο σχήμα 8.5 τη δήλωση PORT για τα κανάλια που υλοποιούν το κανάλι. Κάθε διεργασία j χρησιμοποιεί το pipechan[j] σαν το κανάλι εισόδου της για να λαμβάνει δεδομένα. Έτσι, το pipechan[j] πρέπει να δηλωθεί σαν θύρα για τη διεργασία j. Η παράμετρος απομακρυσμένης διεύθυνσης sorteditem χρησιμοποιείται στη δήλωση δημιουργίας διεργασίας για επιτρέπει στις διεργασίες να επιστρέφουν τις τελικές ταξινομημένες τιμές στον πίνακα sorted στο κυρίως πρόγραμμα. Μετά τη δημιουργία όλων των διεργασιών διασωλήνωσης με τον τελεστή FORK το κυρίως πρόγραμμα στέλνει τη λίστα των τιμών στη διασωλήνωση. Αυτό είναι αναγκαίο γιατί ο πίνακας list που στέλνεται στη διασωλήνωση είναι τοπική μεταβλητή του κυρίως προγράμματος και συνεπώς δεν είναι απευθείας προσβάσιμη από όλες τις διεργασίες.

PROGRAM InsertionSort;


ARCHITECTURE FULLCONNECT(101); (*Πλήρως Συνδεδεμένη τοπολογία*)


CONST n=100;


VAR list, sorted: ARRAY [1..n} OF INTEGER;


    pipechan: ARRAY [1..n] OF CHANNEL OF INTEGER;


    j, k: INTEGER;


PROCEDURE Pipeprocess(me: INTEGER; VAR sorteditem: INTEGER);


VAR internal, newitem, I: INTEGER;


BEGIN


    internal := pipechan[me]; (*Διαβάζει το πρώτο στοιχείο απότα αριστερά*)


    FOR i:= 1 to n-me DO


        BEGIN


            newitem:= pipechan[me]; (*Διαβάζει το πρώτο στοιχείο απότα αριστερά*)


            IF newitem < internal THEN


            BEGIN


                pipechan[me+1]:= internal; (*Στέλνει το “internal” στα δεξιά*)


                internal:= newitem;


            END


            ELSE pipechan[me+1]:= newitem; (*Στέλνει το “newitem” στα δεξιά*)


        END;


    sorteditem:= internal; (*Επιστρέφει την τελική ταξινομημένη λίστα στοιχείων*)


END;


 


BEGIN


    ...


    (*Αρχικοποίηση των στοιχείων για να ταξινομηθούν στον πίνακα “ List ” *)


    FOR j:= 1 TO n DO (*Δημιουργία των διεργασιών διασωλήνωσης*)


        FORK ( PORT pipechan[j] )Pipeprocess(j, sorted[j]);


    FOR k:= 1 TO n DO


        pipechan[1]:= list[k]; (*Στέλνει τη λίστα στην αρχή της διασωλήνωσης*)


    ...


END.

ΣΧΗΜΑ 8.5 Ταξινόμηση με Εισαγωγή σε σύστημα κατανεμημένης μνήμης

Για να γίνει κατανοητή η χρήση του τελεστή @ θεωρείστε ότι εκτελούμε το πρόγραμμα του σχήματος 8.5 σε μια αρχιτεκτονική LINE. Η πιο αποδοτική τακτοποίηση των διεργασιών είναι η απεικόνιση της διασωλήνωσης διεργασιών απευθείας πάνω στην αρχιτεκτονική LINE δηλαδή στη διασωλήνωση επεξεργαστών. Στην περίπτωση αυτή κάθε επεξεργαστής μπορεί να στέλνει μηνύματα σε ένα γειτονικό του και τα μηνύματα που προορίζονται για απομακρυσμένους επεξεργαστές δεν χρειάζεται να προωθούνται. Θυμηθείτε ότι οι επεξεργαστές στην τοπολογία LINE αριθμούνται ακολουθιακά κατά μήκος της γραμμής. Για να απεικονίσουμε διασωλήνωση διεργασιών πάνω στη διασωλήνωση επεξεργαστών απλά αναθέτουμε τη διεργασία j στο φυσικό επεξεργαστή j. Αυτό φαίνεται στο σχήμα 8.6. Με αυτή την τακτοποίηση των διεργασιών κάθε ζεύγος διεργασιών που επικοινωνούν εκτελείται σε γειτονικούς φυσικούς επεξεργαστές ελαχιστοποιώντας έτσι τις καθυστερήσεις επικοινωνίας.

PROGRAM InsertionSort;


ARCHITECTURE LINE(101); (*Τοπολογία Γραμμής με 101 επεξεργαστές*)


CONST n=100;


VAR list, sorted: ARRAY [1..n} OF INTEGER;


    pipechan: ARRAY [1..n] OF CHANNEL OF INTEGER;


    j, k: INTEGER;


PROCEDURE Pipeprocess(me: INTEGER);


    .... (*Είναι τα ίδια με του προγράμματος 8.5*)


END;


BEGIN


    ... 


(*Αρχικοποίηση των στοιχείων για να ταξινομηθούν στον πίνακα “List”*)


    FOR j:= 1 TO n DO (*Δημιουργία των διεργασιών διασωλήνωσης*)


        FORK ( @j PORT pipechan[j] )Pipeprocess(j, sorted[j]);<


    FOR k:= 1 TO n DO


        pipechan[1]:= list[k];(*Στέλνει τη λίστα στην αρχή της διασωλήνωσης*)


...


END.

ΣΧΗΜΑ 8.6 Ταξινόμηση με Εισαγωγή σε τοπολογία LINE

Επόμενο:8.4 Καθυστέρηση Επικοινωνίας Πάνω: Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πίσω: 8.2 Γλωσσική Υποστήριξη Προγραμματισμού Περάσματος Μηνυμάτων