11.1 Πρόγραμμα Συντομότερου Μονοπατιού Συστήματος Κατανεμημένης Μνήμης

Επόμενο: 11.2 Υλοποίηση της Δεξαμενής Εργασίας Πάνω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού Πίσω: Κεφάλαιο 11o : Κατανεμημένη Ανίχνευση Τερματισμού

11.1 Πρόγραμμα Συντομότερου Μονοπατιού Συστήματος Κατανεμημένης Μνήμης

Το πρώτο θέμα που θα μας απασχολήσει σε αυτό το κεφάλαιο είναι πώς να προσαρμόσουμε το πρόγραμμα Συντομότερου Μονοπατιού σε σύστημα κατανεμημένης μνήμης. Θυμηθείτε τον ακολουθιακό αλγόριθμο Συντομότερου Μονοπατιού που περιγράψαμε στο προηγούμενο κεφάλαιο (δες σχήμα 10.3). Ο αλγόριθμος διατηρεί μια ουρά από αριθμούς κόμβων που πρέπει να εξεταστούν. Μια άλλη δομή δεδομένων (πίνακας mindist) καταγράφει τις συντομότερες αποστάσεις που έχουν βρεθεί μέχρι στιγμής για κάθε κόμβο. Αφού ένας αριθμός κόμβου x διαβαστεί από την ουρά είναι απαραίτητο να δούμε αρκετά στοιχεία του mindist: το mindist[x] και επίσης άλλα στοιχεία αντίστοιχα των κόμβων που συνδέονται απευθείας με τον κόμβο x. Αν βρεθεί μια πιο σύντομη απόσταση προς τους κόμβους με τους οποίους συνδέεται ο x, τότε το αντίστοιχο στοιχείο του mindist ενημερώνεται.

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

Εφόσον οι εργαζόμενοι διαβάζουν τους κόμβους από μια κεντρική Δεξαμενή Εργασίας, κάθε εργαζόμενος μπορεί να λάβει κάθε κόμβο του γραφήματος και συνεπώς να απαιτήσει πρόσβαση σε κάθε στοιχείο του πίνακα mindist. Εφόσον υπάρχει μόνο ένα αντίγραφο των στοιχείων του πίνακα mindist προκύπτει το θέμα του πού να τοποθετηθούν τα στοιχεία αυτά. Άσχετα από το πόσο έξυπνα έχουν κατανεμηθεί στις τοπικές μνήμες, είναι δύσκολο να εγγυηθεί κανείς ότι κάθε εργαζόμενος έχει το στοιχείο του mindist που απαιτεί στην τοπική του μνήμη. Το αποτέλεσμα είναι η συχνή απαίτηση μεταφοράς των τιμών του mindist μεταξύ των επεξεργαστών.

Για να αποφύγουμε αυτό το πρόβλημα σε ένα πρόγραμμα συστήματος κατανεμημένης μνήμης απαιτείται η αναδιοργάνωση του παράλληλου αλγορίθμου. Στα προηγούμενα κεφάλαια το ίδιο πρόβλημα είχε προκύψει στα προγράμματα συστημάτων κατανεμημένης μνήμης όταν οι δομές δεδομένων ενημερώνονταν δυναμικά. Θυμηθείτε ότι η λύση που ακολουθούσαμε πάντα ήταν ο επιμερισμός δεδομένων: διαίρεση των στοιχείων της διαμοιραζόμενης δομής δεδομένων στις τοπικές μνήμες και οργάνωση του αλγόριθμου με τέτοιο τρόπο ώστε κάθε διεργασία να επικεντρώνεται αρχικά στο δικό της τμήμα δεδομένων. Στην περίπτωση του προγράμματος του Συντομότερου Μονοπατιού αυτό σημαίνει ότι ο πίνακας mindist πρέπει να επιμεριστεί στις τοπικές μνήμες του συστήματος κατανεμημένης μνήμης. Το πρόγραμμα που παρουσιάζεται εδώ απλά θα τοποθετήσει ένα στοιχείο του mindist σε κάθε τοπική μνήμη. Αυτό είναι δυνατόν με την προϋπόθεση ότι ο αριθμός των κόμβων στο γράφημα είναι μικρότερος από τον αριθμό των επεξεργαστών. Για μεγαλύτερα γραφήματα θα χρειαστεί αρκετά στοιχεία του mindist να ανατεθούν σε κάθε τοπική μνήμη.

Κάθε εργαζόμενος i θα δει ότι έχει τοπική πρόσβαση στο mindist[i], που είναι η συντομότερη απόσταση που έχει βρεθεί μέχρι στιγμής προς τον κόμβο i. Ο αλγόριθμος Συντομότερου Μονοπατιού μπορεί να τροποποιηθεί έτσι ώστε να αποφεύγεται εντελώς η ανάγκη για μεταφορά αυτών των mindist τιμών. Κάθε εργαζόμενος i θα ασχολείται μόνο με τον κόμβο i του γραφήματος. Όποτε ο κόμβος i θα τοποθετείται στην Δεξαμενή Εργασίας, η υλοποίηση της Δεξαμενής θα εξασφαλίζει ότι αυτό το αντικείμενο εργασίας πηγαίνει στον εργαζόμενο i.

Στον αλγόριθμο του Συντομότερου Μονοπατιού η εξέταση ενός δεδομένου κόμβου i από ένα εργαζόμενο i σχετίζεται με τον υπολογισμό μιας νέας απόστασης δοκιμής προς κάθε γειτονικό κόμβο w και στη συνέχεια τη σύγκρισή της με την τρέχουσα τιμή του mindist[w]. Όμως το mindist[w] βρίσκεται στην τοπική μνήμη του εργαζόμενου w. Έτσι ο εργαζόμενος i απλώς θα στείλει την trialdistance του w στον Εργαζόμενο w, όπου θα συγκριθεί με το mindist[w]. Με την νέα αυτή οργάνωση του παράλληλου αλγορίθμου όλα τα αντικείμενα εργασίας θα είναι αποστάσεις δοκιμής. Κάθε αντικείμενο εργασίας θα αποτελείται από έναν αριθμό κόμβου w και μια απόσταση δοκιμής για αυτό τον κόμβο. Όταν ένας εργαζόμενος w λάβει αυτό το αντικείμενο εργασίας θα συγκρίνει την απόσταση δοκιμής του με την τρέχουσα τιμή του mindist[w], η οποία βρίσκεται στην δική του τοπική μνήμη. Αν η απόσταση δοκιμής είναι μικρότερη τότε το mindist ενημερώνεται. Ο εργαζόμενος w θα εξετάσει στην συνέχεια όλους τους γειτονικούς κόμβους προς τον κόμβο w και θα στείλει σε όλους νέες αποστάσεις δοκιμής που βασίζονται στην νέα μικρότερη τιμή του mindist[w].

Το πρόγραμμα Συντομότερου Μονοπατιού για σύστημα κατανεμημένης μνήμης παρουσιάζεται στο σχήμα 11.1. Η υλοποίηση της Δεξαμενής Εργασίας δεν φαίνεται εδώ και θα περιγραφεί πιο κάτω στο κεφάλαιο. Όπως και πριν, η δομή του γραφήματος αναπαριστάται με τον δι-διάστατο πίνακα weight: το στοιχείο weight[i,j] είναι το βάρος που ανατίθεται στην ακμή που συνδέει τους κόμβους i και j. Αν δεν υπάρχει ακμή που να συνδέει τους δύο κόμβους, τότε η τιμή είναι το άπειρο. Συνεπώς, η γραμμή i του πίνακα περιέχει τα βάρη όλων των ακμών που ξεκινούν από τον κόμβο i. Εφόσον όλη η επεξεργασία για τον κόμβο i γίνεται από τον εργαζόμενο i αυτή η γραμμή του πίνακα weight περνά ως παράμετρος τιμής όταν δημιουργείται η διεργασία i.

Ο εργαζόμενος αρχίζει με την ανάγνωση ενός αρχικού αντικειμένου από τη Δεξαμενή Εργασίας. Η υλοποίηση της Δεξαμενής Εργασίας εγγυάται ο εργαζόμενος i θα λάβει μόνο εκείνα τα αντικείμενα εργασίας που αντιστοιχούν στον κόμβο i. Συνεπώς, ο αριθμός κόμβου παραλείπεται από την κλήση της Getwork-επιστρέφεται μόνο η απόσταση δοκιμής του αντικειμένου εργασίας. Ο εργαζόμενος i από τη στιγμή που έχει λάβει αυτή τη νέα απόσταση δοκιμής για τον κόμβο i, το συγκρίνει με τη συντομότερη απόσταση που έχει βρεθεί μέχρι στιγμής για τον κόμβο i, που βρίσκεται τοπικά στην μεταβλητή mindistance. Η συλλογή όλων αυτών των τοπικών τιμών mindistance είναι απλώς ο πίνακας mindist όπως είπαμε και προηγουμένως. Αυτές οι mindist τιμές επιμερίζονται στους εργαζόμενους.

Αν η νέα απόσταση δοκιμής είναι στην πραγματικότητα μικρότερη από την συντομότερη απόσταση προς τον κόμβο i, τότε η mindistance ενημερώνεται. Επίσης, για κάθε εξερχόμενη ακμή από τον κόμβο i προς έναν κόμβο προορισμού w, δημιουργείται ένα νέο αντικείμενο εργασίας που περιέχει την νέα απόσταση δοκιμής για τον κόμβο w (δες σχήμα 11.1). Η υλοποίηση της Δεξαμενής Εργασίας εγγυάται ότι αυτό το αντικείμενο εργασίας φτάνει την διεργασία Εργαζόμενο w. Κάθε εργαζόμενος συνεχίζει το βρόχο μέχρι να ανιχνεύσει ένα σήμα τερματισμού. Πριν να σταματήσει ο εργαζόμενος στέλνει την τελική τιμή του mindistance πίσω στην πρωτεύουσα διεργασία μέσα από την παράμετρο διεύθυνσης answer.

PROGRAM Shortpath_2;


ARCHITECTURE HYPERCUBE(6);


CONST n= 63; (*Αριθμός των κόμβων στο γράφημα*)


    numworkers= 63; 


    infinity= 32000; 


    done= -1;


TYPE weightrow= ARRAY [1..n] OF INTEGER;


VAR weirht: ARRAY [1..n] OF weightrow; (*Βάρη των ακμών στο γράφημα*)


    i: INTEGER;


    finaldist: ARRAY [1..n] OF INTEGER; (*Τελική λύση*)


 

PROCEDURE Worker(me:INTEGER; myweight: weightrow; 


VAR answer: INTEGER);


VAR mindistance: INTEGER; (*Συντομότερη απόσταση προς κόμβο “me”*)


    w, trialdistance: INTEGER;

 


PROCEDURE Getwork(VAR inputdistance: INTEGER);

    …

 

PROCEDURE Putwork(vertex, outputdistance: INTEGER);

    …

 

BEGIN (*Worker*)


    mindistance:= infinity;


    Getwork(trialdistance);


    WHILE trialdistance < > done DO

    BEGIN

        IF trialdistance < > mindistance THEN

        BEGIN (*Βρέθηκε η συντομότερη απόσταση προς τον κόμβο μου*)

            mindistance:= trialdistance;

            FOR w:= 1 TO n DO (*Για κάθε γειτονικό κόμβο*)

                IF myweight[w] < > infinity THEN

                    Putwork(w,mindistance+myweight[w]);

        END;

        Getwork(trialdistance);

    END;

    answer:= mindistance; (*τελική συντομότερη απόσταση*)

END;

 

BEGIN (*Κυρίως πρόγραμμα*)

 

… (*Διάβασμα των τιμών για τον πίνακα weight για τον καθορισμό του 

γραφήματος*)

 

    FORALL i:= 1 TO numworkers DO (*Δημιουργία των Κατανεμημένων Εργαζομένων*)

            (@i) Worker(i, weght[i], finaldist[i]);

 

    … (*Οι απαντήσεις βρίσκονται στον πίνακα finaldist*)

 

END.

ΣΧΗΜΑ 11.1 Αλγόριθμος Συντομότερου Μονοπατιού για σύστημα κατανεμημένης μνήμης