11.3 Οι Getwork και Putwork

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

11.3 Οι Getwork και Putwork

Ο κατανεμημένος αλγόριθμος τερματισμού που βασίζεται στα μηνύματα επιβεβαίωσης είναι αρκετά γενικός και μπορεί να χρησιμοποιηθεί σε μεγάλη ποικιλία προγραμμάτων συστημάτων κατανεμημένης μνήμης. Όταν χρησιμοποιείται στα προγράμματα των Κατανεμημένων Εργαζομένων, οι πληροφορίες που αφορούν τον αλγόριθμο τερματισμού είναι εντελώς κρυμμένες μέσα στην υλοποίηση της Δεξαμενής Εργασίας. Η δημιουργία και η επεξεργασία των επιβεβαιώσεων καθώς και οι αλλαγές των καταστάσεων δημιουργούνται μέσα στις διαδικασίες Putwork και Getwork, έτσι ώστε η Δεξαμενή εργασίας να παρουσιάζεται ως η αφηρημένη δομή δεδομένων που είδαμε στο σχήμα 11.1. Η διεργασία Worker που απαιτείται για τον αλγόριθμο του Συντομότερου Μονοπατιού είναι η ίδια με αυτή του σχήματος 11.1. Η Worker απλά περιμένει να λάβει το σήμα τερματισμού -1 από την υλοποίηση της Δεξαμενής Εργασίας όταν τελειώσει ο υπολογισμός. Όλα τα θέματα της κατανομής των αντικειμένων εργασίας και η ανίχνευση τερματισμού διαχειρίζονται μέσα στις διαδικασίες Putwork και Getwork.

Παρακάτω θα δώσουμε πρώτα μια υψηλού επιπέδου περιγραφή των διαδικασιών Putwork και Getwork και στη συνέχεια τον αντίστοιχο κώδικα της Multi-Pascal, που ενώνεται με τον κώδικα της Worker του σχήματος 11.1 για να ολοκληρώσουν το πρόγραμμα Συντομότερου Μονοπατιού σε σύστημα κατανεμημένης μνήμης. Η εσωτερική δομή της Δεξαμενής Εργασίας έχει ήδη περιγραφεί και παρουσιαστεί στο σχήμα 11.2. Η Δεξαμενή Εργασίας είναι ένας πίνακας καναλιών, με κάθε κανάλι να έχει ανατεθεί ως θύρα επικοινωνίας σε κάθε εργαζόμενο. Η διαδικασία του εργαζόμενου δημιουργεί αντικείμενα εργασίας που αποτελούν την νέα απόσταση προς έναν καθορισμένο κόμβο. Η Putwork χρησιμοποιεί τον αριθμό κόμβου για να βρει την κατάλληλη θύρα επικοινωνίας: μια νέα απόσταση προς τον κόμβο i θα πάει στο κανάλι workpool[i], που έχει ανατεθεί στον εργαζόμενο i.

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

Όνομα μεταβλητής Ερμηνεία

me Ο αναγνωριστικός αριθμός του εργαζόμενου

active Η κατάσταση του εργαζόμενου (αδρανής ή ενεργός)

ackcount Το πληθος των αντικειμένων εργασίας που έχουν σταλεί και για τα οποία δεν έχει φτάσει μήνυμα επιβεβαίωσης

parent Ο αναγνωριστικός αριθμός του εργαζόμενου γονέα.

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

Putwork(vertex, outputdistance):

 

    Increment ackcount;


    Build work item consisting of (me,outputdistance);     


    Write work item itno workpool[vertex];

Το διάγραμμα καταστάσεων του σχήματος 11.4 μπορεί να χρησιμοποιηθεί ως βάση για το γράψιμο της διαδικασίας Getwork. Για την Getwork ένας απλός κώδικας θα χρησιμοποιεί το ίδιο κανάλι εισόδου για τη λήψη των εισερχομένων αντικειμένων εργασίας και των μηνυμάτων επιβεβαίωσης. Τα αντικείμενα θα μπορούν να διαβάζονται από αυτό το κανάλι και στη συνέχεια να επεξεργάζονται ανάλογα με αν είναι αντικείμενα εργασίας ή μηνύματα επιβεβαίωσης. Εφόσον κάθε εργαζόμενος i έχει ένα κανάλι workpool[i] αυτή η θύρα επικοινωνίας χρησιμοποιείται για όλα τα εισερχόμενα αντικείμενα εργασίας και τα μηνύματα επιβεβαίωσης που προορίζονται για αυτόν τον εργαζόμενο.

Η βασική λειτουργία της διαδικασίας Putwork είναι να διαβάζει αντικείμενα από τη θύρα του εργαζόμενου και ελέγχει για το πρώτο αντικείμενο εργασίας. Καθώς τα μηνύματα επιβεβαίωσης φτάνουν στη θύρα απλά παραλαμβάνονται και ο ackcount για τον συγκεκριμένο εργαζόμενο μειώνεται. Όταν βρεθεί το πρώτο αντικείμενο εργασίας στέλνεται ένα μήνυμα επιβεβαίωσης στην αφετηρία του και το τμήμα απόσταση (distance) του αντικειμένου εργασίας επιστρέφεται στον εργαζόμενο που το καλεί. Αν δούμε ότι έχουν ληφθεί όλα τα μηνύματα επιβεβαίωσης και ότι το κανάλι της δεξαμενής εργασίας είναι άδειο, τότε ο εργαζόμενος μεταβαίνει από την ενεργή κατάσταση σε αδράνεια. Παρακάτω δίνεται μια υψηλού επιπέδου περιγραφή της διαδικασίας Getwork:

Getwork:

 

Repeat


    If Worker in Active State AND Work Channel empty


        AND all acknowledgments received Then


        Begin


            Acknowledge current parent;


            Go into Idle State;


        End;


    Read new item from Work Pool;


    If new item is acknowledgment then decrement ack.count;


Until work item is received;

 

If Worker in Active State Then


    send acknowledgment to source of work item


Else Begin


Go into Active State;


Set new parent from source of this work item;


End;

 

Return “distance” part of work item to calling Worker;

Ο κώδικας της Multi-Pascal για τις διαδικασίες Putwork και Getwork παρουσιάζεται στο σχήμα 11.5 μαζί με τις απαιτούμενες δηλώσεις μεταβλητών και τις αρχικοποιήσεις τους. Ο κώδικας αυτός πρέπει να συνδυαστεί με αυτόν της διαδικασίας Worker του σχήματος 11.1 για να ολοκληρωθεί το πρόγραμμα Συντομότερου Μονοπατιού για σύστημα κατανεμημένης μνήμης. Στην αρχή του προγράμματος φαίνεται η δήλωση της Δεξαμενής Εργασίας ως πίνακας καναλιών. Κάθε αντικείμενο εργασίας είναι μια εγγραφή που περιέχει τον αριθμό κόμβου αφετηρίας και την νέα απόσταση. Η Δεξαμενή Εργασίας αρχικοποιείται στην αρχή του κυρίως προγράμματος τοποθετώντας το πρώτο αντικείμενο εργασίας στο κανάλι για τον κόμβο 1. Εφόσον αυτός είναι ο αρχικός κόμβος για όλα τα μονοπάτια η απόσταση αρχικοποιείται με την τιμή 0. Ο κώδικας των Putwork και Getwork μοιάζει με την περιγραφή υψηλού επιπέδου που δώσαμε προηγουμένως. Αυτές οι διαδικασίες βρίσκονται φυσικά μέσα στην διαδικασία Worker που τους δίνει πρόσβαση στις τοπικές της μεταβλητές: me, ackcount, parent και active.

Ένα θέμα του σχήματος 11.5 που δεν έχουμε αναλύσει είναι η διαδικασία επόπτη. Ο μόνος σκοπός αυτής της διαδικασίας είναι να ανιχνεύει πότε αδειάζει το δένδρο των ενεργών εργαζομένων και τότε να στέλνει ένα σήμα τερματισμού σε κάθε διεργασία εργαζόμενο. Δείτε ξανά στο σχήμα 11.3 το διάγραμμα του δένδρου ενεργών εργαζομένων. Καθώς οι εργαζόμενοι αλλάζουν καταστάσεις από ενεργοί σε αδρανείς κατά τη διάρκεια των υπολογισμών το δένδρο μεγαλώνει και συρρικνώνεται δυναμικά. Εφόσον η Δεξαμενή Εργασίας αρχικοποιείται για να δώσει στην διεργασία εργαζόμενο 1 το πρώτο αντικείμενο εργασίας, ο εργαζόμενος 1 θα είναι πάντα ο πρώτος ενεργός εργαζόμενος και συνεπώς θα αποτελεί πάντα την ρίζα του δένδρου (δες σχήμα 11.3). Ο εργαζόμενος 1 θα γίνει αδρανής μόνο όταν όλοι οι απόγονοί του είναι αδρανείς. Έτσι, όταν ο εργαζόμενος 1 γίνει αδρανής αυτό σημαίνει ότι όλοι οι εργαζόμενοι είναι αδρανείς.

Συνεπώς, η ανίχνευση τερματισμού απλά αποτελείται από τον προσδιορισμό πότε ο εργαζόμενος 1 θα γίνει αδρανής. Οποιαδήποτε στιγμή ένας εργαζόμενος μεταβεί από την αδράνεια σε ενεργή κατάσταση στέλνει πάντα ένα μήνυμα επιβεβαίωσης στον γονέα του. Αφού ο εργαζόμενος 1 δεν έχει γονέα δημιουργείται μια ψεύτικη διεργασία εργαζόμενος 0 για να λειτουργήσει ως γονέας του εργαζόμενου 1. Αυτός ο ψεύτικος εργαζόμενος απλά περιμένει το μήνυμα επιβεβαίωσης από τον εργαζόμενο 1. Όταν το σήμα επιβεβαίωσης φτάσει τότε αυτό είναι και το σήμα τερματισμού. Αυτός ο ψεύτικος εργαζόμενος δημιουργείται από τον επόπτη χρησιμοποιώντας μια δήλωση FORK στο κυρίως πρόγραμμα. Ο επόπτης αρχίζει με μια εντολή ανάγνωσης του καναλιού 0 στην Δεξαμενή Εργασίας. Το κανάλι αυτό είναι άδειο μέχρι ο εργαζόμενος 1 στείλει την επιβεβαίωσή του, δηλώνοντας ότι όλοι οι εργαζόμενοι είναι αδρανείς και ότι ο υπολογισμός πρέπει να σταματήσει.

Όπως και η υλοποίηση της Δεξαμενής Εργασίας σε σύστημα διαμοιραζόμενης μνήμης έτσι και στο σύστημα κατανεμημένης μνήμης η υλοποίηση είναι γενική και μπορεί να χρησιμοποιηθεί από μια μεγάλη ποικιλία προγραμμάτων Κατανεμημένων Εργαζομένων. Για να προσαρμόσουμε τις διαδικασίες Putwork και Getwork σε ένα διαφορετικό πρόγραμμα πρέπει να αλλάξει η μορφή των αντικειμένων εργασίας. Επίσης, πρέπει να τροποποιηθεί η μέθοδος κατανομής των αντικειμένων εργασίας στην Putwork. Στο πρόγραμμα του Συντομότερου Μονοπατιού ο αριθμός του κόμβου προορισμού χρησιμοποιείται για την επιλογή του κατάλληλου εργαζόμενου για την λήψη κάθε αντικειμένου εργασίας. Αυτή η τεχνική βασίζεται στην ανάθεση ενός κόμβου του γραφήματος σε κάθε εργαζόμενο. Σε άλλα προγράμματα Κατανεμημένων Εργαζομένων για διαφορετικά προβλήματα, αυτή η τεχνική κατανομής ίσως να χρειάζεται τροποποίηση, αλλά όλα τα υπόλοιπα θέματα της υλοποίησης της Δεξαμενής Εργασίας παραμένουν ίδια.

PROGRAM Shortpath_2;


ARCHITECTURE HYPERCUBE(6);


CONST numworkers= 63;


    done= -1; ack= -2; (*Ειδικοί κωδικοί μηνυμάτων*)

…

 


TYPE worktype= RECORD (*Μορφή των αντικειμένων στη Δεξαμενή Εργασίας*)


        source: INTEGER;


        distance: INTEGER;


        END;

…

 


VAR workpool: ARRAY [0..numworkers] OF CHANNEL OF worktype;


    i: INTEGER;


    startwork: worktype;

…

 


PROCEDURE Monitor;


(*Περιμένει να τερματιστεί το δένδρο των ενεργών εργαζομένων*)


VAR i: INTEGER;


    workitem: worktype;


BEGIN


    workitem:= workpool[0]; (*Περίμενε εδώ*)


    workitem.source:= done;


workitem.distance:= done;


    (*Τώρα στείλε σήματα τερματισμού σε όλους τους Εργαζόμενους*)


    FOR i:= 1 TO numworkers DO


        workpool[i]:= workitem;


END;

 


PROCEDURE Worker(me: INTEGER; myweight: weightrow; VAR answer: INTEGER);


VAR ackwork, parent: INTEGER;


    active: BOOLEAN; (*Τρέχουσα κατάσταση του Εργαζόμενου*)

…

 


PROCEDURE Getwork(VAR inputdistance: INTEGER);


VAR inwork, ackwork: worktype;


BEGIN


    ackwork.source:= ack;


    REPEAT


        IF active AND (ackcount= 0) AND (NOT workpool[me]?) THEN


        BEGIN (*Αλλαγή από κατάσταση αδράνειας σε ενεργή)


            active:= False;


            workpool[parent]:= ackwork; (*Μήνυμα επιβεβαίωσης στον γονέα*)


        END;


        inwork:= workpool[me]; (*Ανάγνωση αντικειμένου από την Δεξαμενή Εργασίας*)


        IF inwork.source= ack THEN ackcount:= ackcount - 1;


    UNTIL inwork.source < > ack; (*Ανάγνωση μέχρι να λάβει αντικείμενα εργασίας*)

    IF active THEN workpool[inwork.source]:= ackwork (*Το ack στην αφετηρία*)

    ELSE BEGIN (*Αλλαγή κατάστασης από αδρανή σε ενεργή*)

    active:= True;

    parent:= inwork.source; (*Προσδιορίζω τον νέο γονέα*)

END;

inputdistance:= inwork.distance; (*Επιστροφή του αντικειμένου 

εργασίας σε αυτόν που καλεί*)

END;

 

PROCEDURE Putwork(vertex, outputdistance: INTEGER);

VAR outwork: worktype;

BEGIN    

    ackcount;= ackcount+1;

    outwork.source:= me; (*Ο “me” είναι ο αριθμός κόμβου που μου έχει ανατεθεί*)

    outwork.distance:= outputdistance;

    workpool[vertex]:= outwork; (*Τοποθέτηση μέσα στην Δεξαμενή Εργασίας*)

END;

 

BEGIN (*Worker*)

    ackcount:= 0;

    active:= false;

 

    … (*Η διαδικασία Worker του σχήματος 11.1*)

 

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

…

 

    startwork.source:= 0;

    startwork.distance:= 0;

    workpool[1]:= startwork; (*Ξεκίνημα με τον κόμβο 1*)

    FORK (@0 PORT workpool[0]) Monitor;

 

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

            (@i PORT workpool[i] Worker(i, weight[i], finaldist[i]);

 

END.

ΣΧΗΜΑ 11.5 Υλοποίηση της Δεξαμενής Εργασίας

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