10.4 Εξάλειψη της Συμφόρησης

Επόμενο:10.5 Πρόβλημα των Ν-Βασιλισσών Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: 10.3 Υλοποίηση των Δεξαμενών Εργασίας

10.4 Εξάλειψη της Συμφόρησης

Η υλοποίηση της Δεξαμενής Εργασίας όπως φαίνεται στο σχήμα 10.4 παρέχει ένα πλήρες Multi-Pascal πρόγραμμα για τον παράλληλο αλγόριθμο του συντομότερου μονοπατιού. Τώρα που έχει δημιουργηθεί ένα πλήρες πρόγραμμα, το επόμενο θέμα είναι η ανάλυση της απόδοσής του και ο έλεγχος αν είναι το πρόγραμμα αποδεκτό. Όπως εξηγήσαμε στο κεφάλαιο 5, οι ατομικές λειτουργίες μπορεί μερικές φορές να οδηγήσουν σε προβλήματα απόδοσης, γιατί μπορούν να εκτελούνται μόνο από μια διεργασία κάθε φορά. Κάθε εργαζόμενος χρησιμοποιεί μια ατομική λειτουργία για να ενημερώνει την μεταβλητή count κάθε φορά που προσπελαύνει την Δεξαμενή Εργασίας. Παρόλη τη σύντομη διάρκεια της ατομικής λειτουργίας, τελικά οδηγεί σε συμφόρηση της απόδοσης καθώς αυξάνεται ο αριθμός των εργαζομένων. Ας θέσουμε ως i το μέσο χρονικό διάστημα μεταξύ των προσπελάσεων της Δεξαμενής Εργασίας από κάθε διεργασία και ως d την διάρκεια της ατομικής λειτουργίας στη μεταβλητή count. Το σημείο κορεσμού του αριθμού των διεργασιών Εργαζομένων είναι i/d.

PROGRAM Shortpath;

CONST numworkers=…;

    …

 

TYPE worktype= INTEGER;

VAR workpool: CHANNEL OF worktype;

    count: INTEGER; (*Μετρητής της Δεξαμενής Εργασίας*)

    M: SPINLOCK;

    startvertex: worktype;

…

 

PROCEDURE Getwork(me: INTEGER; VAR item: worktype);

VAR workcount: INTEGER;

BEGIN

(*Πρώτη ανάγνωση και μείωση του μετρητή της Δεξαμενής Εργασίας*) Lock(M);

    workcount:= count-1;

    count:= workcount;

    Unlock(M);

    IF workcount=-numworkers THEN

    BEGIN (*Τερματισμός των Εργαζομένων*)

        item:= -1;

        FOR i:= 1 TO numworkers-1 DO

            workpool:= item;

    END

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

END;

 

PROCEDURE Putwork(me: INTEGER; item; worktype);

VAR workcount: INTEGER;

BEGIN

    Lock(M);

    count:= count+1; (*Αύξηση του μετρητή της Δεξαμενής Εργασίας*)

    Unlock(M);

    workpool:= item;

END;

 

PROCEDURE Worker(me: INTEGER);

... (*Διεργασία Worker-δες σχήμα 10.3*)

 

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

    count:= 1;

    startvertex:= 1;

    workpool:= startvertex; (*Ο κόμβος αφετηρία 1 στη Δεξαμενή Εργασίας*)

 

… (*Άλλες αρχικοποιήσεις όπως και στο σχήμα 10.3*)

 

    FORALL i:= 1 TO numworkers DO

        Worker(i);

END.

ΣΧΗΜΑ 10.4 Υλοποίηση των Getwork και Putwork

Στα προηγούμενα κεφάλαια παρουσιάστηκε η γενική αρχή ότι η συμφόρηση ενός διαμοιραζόμενου πόρου μπορεί να μειωθεί με την αποκέντρωση του πόρου αυτού. Αν εφαρμόσουμε αυτή την αρχή στην Δεξαμενή Εργασίας, τότε πρέπει να τροποποιήσουμε τη λύση ώστε να περιέχει αρκετά κανάλια που θα μπορούν να προσπελαστούν παράλληλα από πολλούς Εργαζόμενους. Κάθε κανάλι μπορεί να έχει τη δική του μεταβλητή count και έτσι να ελαττώνεται η συμφόρηση της απόδοσης τοπικά. Αυτό μπορεί να βελτιώσει την απόδοση, με την προϋπόθεση ότι λαμβάνεται υπόψη ένα άλλο σημαντικό θέμα: η εξισορρόπηση του φορτίου. Επίσης, η αποκέντρωση της Δεξαμενής Εργασίας απλοποιεί τον έλεγχο τερματισμού. Οι δύο παράγραφοι που ακολουθούν παρουσιάζουν μια υλοποίηση αποκεντρωμένης Δεξαμενής Εργασίας και λαμβάνουν υπόψη τα δύο ζητήματα - την εξισορρόπηση φορτίου και τον έλεγχο τερματισμού.

10.4.1 Εξισορρόπηση Φορτίου

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

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

Η λύση που υιοθετήσαμε εδώ αφορά τη διαίρεση όλων των διεργασιών Εργαζομένων σε ισομεγέθεις ομάδες και να αναθέσουμε μόνιμα κάθε ομάδα σε ένα μόνο κανάλι για τις Getwork λειτουργίες του. Για παράδειγμα, αν έχουμε τέσσερα κανάλια και 24 εργαζόμενους, τότε μια ομάδα των έξι εργαζομένων θα ανατεθεί σε κάθε κανάλι. Κάθε εργαζόμενος θα προσπελαύνει πάντα το κανάλι στο οποίο ανατέθηκε όταν θα πραγματοποιεί μια λειτουργία Getwork. Αν αυτό το κανάλι είναι άδειο, τότε ο εργαζόμενος θα αναστείλει τη λειτουργία του περιμένοντας για το άδειο κανάλι. Αυτή η τεχνική υλοποίησης παρουσιάζεται στο σχήμα 10.5.

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

ΣΧΗΜΑ 10.5 Δεξαμενή εργασίας πολλαπλών καναλιών

10.4.2 Αλγόριθμος Τερματισμού

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

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

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

Για να εφαρμόσουμε την ανίχνευση τερματισμού απαιτείται ένας πίνακας μετρητών με έναν μετρητή για κάθε κανάλι. Αυτοί οι μετρητές πίνακα αυξάνονται και μειώνονται κατά τη διάρκεια του προγράμματος καθώς εκτελούνται οι λειτουργίες Putwork και Getwork. Για να ανιχνεύσουμε την τελική συνθήκη τερματισμού χρησιμοποιείται ένας επιπλέον πρωτεύων μετρητής, ο master counter, που καταγράφει τον συνολικό αριθμό των αδρανών Ομάδων Εργαζομένων. Αυτό παρουσιάζεται στο σχήμα 10.6. Τα στοιχεία του πίνακα count για κάθε κανάλι αλλάζουν συχνά-κάθε φορά που πραγματοποιείται η Putwork ή η Getwork στο αντίστοιχο κανάλι. Όπως και στην προηγούμενη υλοποίηση, η ενημέρωση ενός μετρητή πρέπει να είναι μια ατομική λειτουργία και συνεπώς απαιτεί αποκλειστική πρόσβαση για ένα μικρό χρονικό διάστημα από έναν μόνο εργαζόμενο. Εφόσον κάθε κανάλι έχει τον δικό του μετρητή, η ενημέρωση των μετρητών δεν πρέπει να δημιουργεί συμφόρηση της απόδοσης.

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

Για να διασφαλίσουμε ότι η πρόσβαση στον πίνακα μετρητών και στον πρωτεύοντα μετρητή δεν δημιουργούν προβλήματα συμφόρησης, πρέπει να επιλέξουμε προσεκτικά τον αριθμό των καναλιών στην υλοποίηση της Δεξαμενής Εργασίας. Αν ο αριθμός των καναλιών είναι ιδιαίτερα μικρός, τότε θα υπάρχει ένας μεγάλος αριθμός εργαζομένων σε κάθε Ομάδα και έτσι θα εμφανίζεται το ίδιο είδος συμφόρησης όπως και στην υλοποίηση με το ένα κανάλι. Όμως, αν ο αριθμός των καναλιών είναι πολύ μεγάλος, τότε τα αντικείμενα εργασίας πρέπει να μοιραστούν σε όλα αυτά τα κανάλια και το πρόβλημα της εξισορρόπησης φορτίου μπορεί να προκαλέσει μείωση της απόδοσης. Η εμπειρία έχει δείξει ότι 5 ως 15 εργαζόμενοι ανά ομάδα είναι καλή επιλογή για ένα μεγάλο εύρος αλγορίθμων Αντιγράφων Εργαζομένων. Μια λεπτομερής μαθηματική ανάλυση του θέματος αυτού θα μας απασχολήσει αργότερα.

ΣΧΗΜΑ 10.6 Μετρητές τερματισμού

Παρακάτω δίνεται μια υψηλού επιπέδου περιγραφή των διαδικασιών Putwork και Getwork για αυτή την υλοποίηση πολλαπλών καναλιών των Δεξαμενών Εργασίας:

   Getwork(me,item);

 

    Compute my channel number in the Work Pool;

    Decrement counter for the channel;     

    If counter= -Worker_Group_Size then

    Begin (*Η δική μου Ομάδα Εργαζομένων είναι τώρα αδρανής*)

        Increment master counter;

        If master counter= number_of_Worker_Groups then

        (*Αποστολή ενός μηνύματος τερματισμού σε κάθε εργαζόμενο*)

            For i:= 1 to number_of_Worker_Groups do 

                For j:= 1 to Worker_Group_Size do

                    Put a termination flag into channel of Worker Group i;

    End;

    Read a task descriptor from my channel into “item”;

 

Putwork(me, item)

 

    Move my pointer to the next channel in Work Pool;

    Increment counter for the target channel;

    If counter= -Worker_Group_Size+1 then

        Decrement master counter; (*Η αδρανής Ομάδα Εργαζομένων είναι τώρα ενεργή*)

    Write “item” into the target channel;

Εκτός από την εγγραφή και την ανάγνωση αντικειμένων από τη Δεξαμενή Εργασίας οι ρουτίνες Putwork και Getwork πρέπει επιπλέον να τροποποιούν τους αθροιστές και να ανιχνεύουν τυχόν μεταβολές στις καταστάσεις των Ομάδων Εργαζομένων από αδρανείς σε ενεργές και το αντίθετο. Όταν το κανάλι που ανατίθεται σε μια Ομάδα Εργαζομένων είναι άδειο οι εργαζόμενοι αυτής της ομάδας θα βρεθούν σταματημένοι καθώς θα προσπαθήσουν να διαβάσουν το άδειο κανάλι. Όταν η τελευταία ενεργή διεργασία της Ομάδας Εργαζομένων καλέσει την Getwork για να διαβάσει το κανάλι, ο μετρητής αυτού του καναλιού θα φτάσει την ελάχιστη αρνητική τιμή του Worker_Group_Size. Τότε ο πρωτεύων μετρητής πρέπει να αυξηθεί για να δηλώσει ότι μια επιπλέον Ομάδα Εργαζομένων είναι αδρανής. Αν αυτή η Ομάδα Εργαζομένων συμβεί να είναι η τελευταία που γίνεται αδρανής τότε ο πρωτεύων μετρητής θα έχει φτάσει στην τιμή number_of_Worker_Groups. Σε αυτή την περίπτωση πρέπει να συμβεί τερματισμός και η ρουτίνα Getwork θα στείλει σήματα τερματισμού σε όλες τις Διεργασίες Εργαζόμενους, γράφοντας τα μηνύματα στη Δεξαμενή Εργασίας. Θυμηθείτε από το σχήμα 10.3 ότι οι εργαζόμενοι ελέγχουν για το σήμα τερματισμού “-1” στην αρχή κάθε επανάληψης.

Η Putwork εκτός από την εκ περιτροπής εγγραφή αντικειμένων στα κανάλια, πρέπει επίσης να ελέγχει τις αλλαγές των Ομάδων Εργαζομένων. Όταν μια Ομάδα Εργαζομένων είναι αδρανής, τότε όλες οι διεργασίες Εργαζόμενοι της ομάδας αυτής περιμένουν σε ένα άδειο κανάλι. Όμως, μια διεργασία Εργαζόμενος από μια άλλη ομάδα μπορεί να τοποθετήσει ένα νέο αντικείμενο σε αυτό το κανάλι και έτσι να “ξυπνήσει” την αντίστοιχη Ομάδα Εργαζομένων. Αν αυτή η Ομάδα Εργαζομένων είναι αδρανής ο μετρητής της θα έχει την τιμή -Worker_Group_Size. Συνεπώς, μετά την αύξηση του μετρητή για το δεδομένο κανάλι η ρουτίνα Putworkπρέπει να ελέγξει το μετρητή για να δει αν τώρα έχει την τιμή -Worker_Group_Size+1. Σε αυτή την περίπτωση η συγκεκριμένη Ομάδα Εργαζομένων έχει γίνει ενεργή και ο πρωτεύων μετρητής πρέπει να μειωθεί.

10.4.3 Απόδοση

Ο κώδικας της Multi-Pascal για τις διαδικασίες Putwork και Getwork παρουσιάζεται στο σχήμα 10.7. Αυτές οι διαδικασίες απλώς αντικαθιστούν την προηγούμενη υλοποίηση των Δεξαμενών Εργασίας. Οι εργαζόμενοι παραμένουν αμετάβλητοι γιατί αντιμετωπίζουν τη Δεξαμενή Εργασίας σαν μια αφηρημένη δομή δεδομένων: Η υλοποίηση της Δεξαμενής Εργασίας είναι διαφανής προς τους εργαζόμενους. Στο τμήμα δηλώσεων των μεταβλητών στην αρχή του σχήματος 10.7 βλέπουμε ότι η Δεξαμενή Εργασίας είναι ένας πίνακας καναλιών (ARRAY OF CHANNELS), στον οποίο κάθε κανάλι διατηρεί μια συλλογή κόμβων του γραφήματος. Οι αθροιστές δηλώνονται ως ένας πίνακας count με έναν πίνακα από κλειδώματα, τον CL, ο οποίος εξασφαλίζει αμοιβαίο αποκλεισμό. Θυμηθείτε ότι κάθε εργαζόμενος χρησιμοποιεί έναν περιφερόμενο δείκτη για να καθορίζει που θα γράψει τους κόμβους κατά τη διάρκεια της λειτουργίας Putwork. Αυτοί οι δείκτες για όλους τους Εργαζόμενους διατηρούνται στον καθολικό πίνακα nextchan.

Η διαδικασία Getwork του σχήματος 10.7 ανταποκρίνεται στην περιγραφή υψηλού επιπέδου που δώσαμε νωρίτερα. Στην αρχή της διαδικασίας ο εισερχόμενος εργαζόμενος υπολογίζει τον αριθμό καναλιού του στην Δεξαμενή Εργασίας, χρησιμοποιώντας τον δικό του αναγνωριστικό αριθμό εργαζόμενου που είναι αποθηκευμένος στην μεταβλητή me. Αυτοί οι αναγνωριστικοί αριθμοί ανατίθενται στους εργαζομένους όταν δημιουργούνται. Επίσης και η διαδικασία Putwork ανταποκρίνεται στην περιγραφή υψηλού επιπέδου που δώσαμε νωρίτερα. Ένα αξιοσημείωτο χαρακτηριστικό είναι η χρήση του πίνακα nextchan που διατηρεί τους δείκτες καναλιού της Δεξαμενής Εργασίας. Στην αρχή της Putwork ο δείκτης του καναλιού που θα χρησιμοποιηθεί από τον εργαζόμενο αντιγράφεται στη μεταβλητή next και στη συνέχεια χρησιμοποιείται ως δείκτης στους πίνακες count και workpool. Στο τέλος της Putwork ο δείκτης μεταφέρεται στο επόμενο κανάλι της Δεξαμενής Εργασίας.

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

Το σήμα 10.8 δείχνει μια καμπύλη απόδοσης της επιτάχυνσης του προγράμματος του Συντομότερου Μονοπατιού για ένα δείγμα γραφήματος με 2800 κόμβους. Ο οριζόντιος άξονας δείχνει το συνολικό αριθμό των καναλιών στη υλοποίηση της Δεξαμενής Εργασίας (η παράμετρος num_workers_groups στο πρόγραμμα του σχήματος 10.7). Ο συνολικός αριθμός των εργαζομένων διατηρείται σταθερός στους 60, η οποία είναι και η μέγιστη δυνατή επιτάχυνση. Για την περίπτωση τους ενός μόνο καναλιού και οι 60 Εργαζόμενοι χρησιμοποιούν το κανάλι με αποτέλεσμα να έχουμε σοβαρό πρόβλημα συμφόρησης, όπως φανερώνεται και από την πολύ χαμηλή επιτάχυνση (9.5). Φαίνεται ότι η συχνότητα της πρόσβασης στη Δεξαμενή Εργασίας προκαλεί τον κορεσμό ενός καναλιού στους περίπου 10 Εργαζόμενους. Στο σχήμα, καθώς ο αριθμός των καναλιών σταδιακά αυξάνει, η επιτάχυνση στη αρχή αυξάνεται ραγδαία, μετά αρχίζει να παίρνει σταθερή τιμή και τελικά μειώνεται.

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

PROGRAM Shortpath;

CONST num_worker_groups= 5;

    worker_group_size= 10;

    numworkers= num_worker_groups*worker_group_size;

 

TYPE worktype= INTEGER;

VAR workpool: ARRAY [1..num_worker_groups] OF CHANNEL OF worktype;

    count: ARRAY [1..num_worker_groups] OF INTEGER;

    CL: ARRAY [1..num_worker_groups] OF SPINLOCK;

    mastercount: INTEGER;

    M: SPINLOCK;

    nextchan: ARRAY [1..numworkers] OF INTEGER;

    i,j: INTEGER;

    startvertex: worktype;

…

 

PROCEDURE Gerwork(me: INTEGER; VAR item: worktype);

VAR worksount,emptycount,mychan: INTEGER;

BEGIN

    mychan:= (me-1) DIV worker_group_size + 1; (*Ο αριθμός καναλιού*)

    Lock(CL[mychan]);

    workcount:= count[mychan] - 1; (*Μείωση του count*)

    count[mychan]:= workcount;

    Unlock(CL[mychan]);

    IF workcount=-worker_group_size THEN

    BEGIN (*Η Ομάδα Εργαζομένων είναι αδρανής*)

        Lock(M);

        emptycount:= mastercount+1; (*Αύξηση του mastercount*)

        mastercount:= emptycount;

        Unlock(M);

        IF emptycount=num_worker_groups THEN

        BEGIN (*Τερματισμός όλων των Εργαζομένων*)

            FOR i:= 1 TO num_worker_grours DO

                FOR j:= 1 TO worker_group_size DO 

                    workpool[i]:= -1;

        END;

    END;

    item:= workpool[mychan];

END;

 

PROCEDURE Putwork(me: INTEGER; item: worktype);

VAR workcount,emptycoun,next: INTEGER;

BEGIN

    next:= nextchan[me]; (*Λαμβάνω τον αριθμό του καναλιού προορισμού*)

    Lock(CL[next]);

    workcount:= count[next]+1; (*Αύξηση του count*)

    count[next]:= workcount;

    Unlock(CL[next]);

    IF workcount= -worker_group_size+1 THEN

    BEGIN

        Lock(M);

        emptycount:= mastercount-1; (*Μείωση του mastercount*)

        mastercount:= emptycount;

        Unlock(M);

    END;

    workpool[next]:= item; (*Εγγραφή αντικειμένου στη Δεξαμενή Εργασίας*)

    nextchan[me]:= next MOD num_worker_groups+1; (*Επόμενος προορισμός*)

END;

 

PROCEDURE Worker(me: INTEGER);

VAR …

 

BEGIN

    nextchan[me]:= (me-1) DIV worker_group_size+1;

 

    … (*Η διεργασία Worker ίδια με αυτή του σχήματος 10.3*)

 

END;

 

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

    startvertex:= 1;

    workpool[1]:= startvertex; (*Ο κόμβος αφετηρία 1 μέσα στη Δεξαμενή Εργασίας*)

    (*Αρχικοποίηση όλων των αθροιστών*)

    count[1]:= 1;

    FOR i:= 2 To num_worker_groups DO

        count[i]:= 0;

    mastercount:= 0;

 

    … (*Άλλες αρχικοποιήσεις όπως και στο σχήμα 10.3*)

 

    FORALL i:= 1 TO numworkers DO

        Worker(i);

 

END.

ΣΧΗΜΑ 10.7 Δεξαμενή Εργασίας χωρίς συμφόρηση

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

ΣΧΗΜΑ 10.8 Απόδοση Αντιγράφων Εργαζομένων

Καθώς ο αριθμός των καναλιών αυξάνεται, η μείωση του ρυθμού ελάττωσης της συμφόρησης σε συνδυασμό με τα αυξανόμενα προβλήματα εξισορρόπησης φορτίου, προκαλεί την καθοδική κλίση της καμπύλης απόδοσης. Η μέγιστη επιτάχυνση 41 είναι αποτέλεσμα των 10 καναλιών, όπου έχουν ανατεθεί 6 από τους 60 Εργαζόμενους σε κάθε κανάλι. Αυτό σημαίνει ότι κάθε κανάλι λειτουργεί κατά μέσο όρο με 60% δυνατότητα απόδοσης. Σύμφωνα με τη θεωρία ουρών, ένας εξυπηρετητής με μέσο χρόνο υπηρεσίας d που λειτουργεί κατά ένα κλάσμα f της συνολικής του δυνατότητας θα προκαλέσει την ακόλουθη καθυστέρηση ουράς για την άφιξη των αντικειμένων :

Καθυστέρηση Ουράς=

O παραπάνω τύπος υποθέτει ότι οι αφίξεις ακολουθούν μια κατανομή Poisson και ο χρόνος υπηρεσίας κατανέμεται εκθετικά. Ο τύπος μπορεί να χρησιμοποιηθεί για να πάρουμε μια πρόχειρη προσέγγιση της αναμενόμενης μείωσης της απόδοσης που είναι αποτέλεσμα της συμφόρησης. Αντικαθιστώντας f= 0.6 έχουμε την αναμενόμενη καθυστέρηση (1.5d). Αν θέσουμε ως i το μέσο χρονικό διάστημα μεταξύ των προσπελάσεων στη Δεξαμενή Εργασίας από κάθε διεργασία, τότε το σημείο κορεσμού για ένα κανάλι είναι i/d. Εφόσον το παρατηρούμενο σημείο κορεσμού σε αυτή την περίπτωση είναι 10 Εργαζόμενοι, τότε d= 0.1i. Συνεπώς, η αναμενόμενη καθυστέρηση που προκαλείται από κάθε Εργαζόμενο κάθε φορά που προσπελαύνει την Δεξαμενή Εργασίας είναι 0.15i. Εφόσον αυτές οι προσπελάσεις της Δεξαμενής Εργασίας συμβαίνουν κάθε i μονάδες χρόνου, η αναμενόμενη μείωση της απόδοσης από τη συμφόρηση είναι περίπου 15%. Στο σχήμα 10.8 η μείωση της απόδοσης που παρατηρείται για την περίπτωση των 10 καναλιών είναι 32%. Η παραπάνω ανάλυση δείχνει ότι περίπου το 15% μπορεί να αποδοθεί στη συμφόρηση των καναλιών και συνεπώς το υπόλοιπο 17% πρέπει να είναι αποτέλεσμα της ανισορροπίας φορτίου.

Για να διερευνήσουμε τη φύση του προβλήματος της ανισορροπίας φορτίου, μπορούμε να προσθέσουμε μια επιπλέον διεργασία επόπτη στο πρόγραμμα του Συντομότερου Μονοπατιού. Αυτή η διεργασία περιοδικά διαβάζει και εκτυπώνει τον πίνακα count, που δηλώνει πόσα είναι τα τρέχοντα αντικείμενα σε ένα κανάλι ή πόσες αδρανείς διεργασίες περιμένουν σε ένα δεδομένο κανάλι. Η διεργασία επόπτης έχει την ακόλουθη γενική δομή:

FOR i:= 1 TO num_samples DO

BEGIN

    Duration(Interval); (*Περιμένει για “interval” μονάδες χρόνου*)

    FOR j:= 1 TO num_worker_groups DO (*Εμφάνιση του πίνακα count*)

        Write(count[j]);

    Writeln;

END;

Αυτή η διεργασία θα παίρνει δείγματα από τον πίνακα count κάθε Interval μονάδες χρόνου. Εφόσον η διεργασία εκτελείται σε διαφορετικό επεξεργαστή και δεν χρησιμοποιεί κλειδώματα ούτε προσπελαύνει κανάλια, δεν θα αναμιχθεί στην εκτέλεση του αρχικού προγράμματος κατά κανένα τρόπο. Για μέγεθος Interval 450 το αποτέλεσμα που προκύπτει φαίνεται στο σχήμα 10.9. Κάθε γραμμή αναπαριστά ένα δείγμα των μετρητών στα 10 κανάλια της Δεξαμενής Εργασίας. Τα σχετικά μεγέθη των μετρητών σε κάθε γραμμή δηλώνουν το βαθμό της ανισορροπίας φορτίου σε αυτό το σημείο στην εκτέλεση του προγράμματος. Θυμηθείτε ότι μια μη μηδενική ή αρνητική τιμή μετρητή δηλώνει τον αριθμό των εργαζομένων που περιμένουν στο δεδομένο άδειο κανάλι. Μπορούμε να παρατηρήσουμε εύκολα από το σχήμα ότι κάποια μείωση της απόδοσης συμβαίνει στα αρχικά και τελικά στάδια της εκτέλεσης και είναι αποτέλεσμα ενός συνδυασμού έλλειψης επαρκούς εργασίας και άνισης κατανομής των αντικειμένων εργασίας. Εφόσον οι αρνητικοί μετρητές δηλώνουν αδρανείς διεργασίες αυτά τα δείγματα μπορούν να χρησιμοποιηθούν για την εκτίμηση του μέσου αριθμού των αδρανών διεργασιών κατά τη διάρκεια της εκτέλεσης του προγράμματος. Η τιμή του 14% που προκύπτει δίνει μια χονδρική εκτίμηση της μείωσης της απόδοσης που είναι αποτέλεσμα της ανισορροπίας φορτίου και της έλλειψης εργασίας. τιμή αυτή είναι κοντά στο 17% που προβλέφθηκε στην παραπάνω ανάλυση της συμφόρησης.

**** ΣΧΗΜΑ 10.9 Μετρητές καναλιών στο συντομότερο μονοπάτι

(Σημείωση: Στον υπολογισμό του μέσου στο σχήμα 10.9 πρέπει να κάνουμε μια σημαντική διόρθωση. Εφόσον υπάρχουν 60 διεργασίες, χρειάζεται περίπου 900 μονάδες χρόνου για να δημιουργηθούν όλες οι διεργασίες. Συνεπώς, η πρώτη γραμμή δείγματος, που συμβαίνει μετά από 450 μονάδες χρόνου, θα βρει τα πέντε κανάλια που βρίσκονται στην δεξιά πλευρά με καθόλου διεργασίες. Έτσι, οι δεξιότεροι αριθμοί της πρώτης γραμμής πρέπει όλοι να διορθωθούν σε -6 κατά τη διάρκεια του υπολογισμού του μέσου).

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