Next              Up                Back                    Contents

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


 

11.6 Περίληψη

 

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

Υπάρχουν κάποιες μεγάλες κατηγορίες προγραμμάτων Κατανεμημένων Εργαζομένων που καθορίζουν την υλοποίηση των Getwork και Putwork. Η υλοποίηση της Putwork εξαρτάται από το αν οι εργαζόμενοι είναι διακριτοί ή όχι. Αν οι Εργαζόμενοι είναι μη-διακριτοί τότε κάθε αντικείμενο εργασίας μπορεί γενικά να σταλεί σε οποιονδήποτε εργαζόμενο. Συνεπώς, η διαδικασία Putwork μπορεί ελεύθερα να κατανείμει τα νέα αντικείμενα εργασίας με στόχο την εξισορρόπηση φορτίου στους εργαζόμενους. Ένα παράδειγμα τέτοιου προγράμματος είναι το πρόβλημα των Ν Βασιλισσών, που περιγράψαμε στο κεφάλαιο 10 στα πλαίσια των Αντιγράφων Εργαζομένων σε σύστημα διαμοιραζόμενης μνήμης. Η ίδια τεχνική εκ περιτροπής κατανομής εργασίας που χρησιμοποιήσαμε τότε μπορεί εύκολα να προσαρμοστεί στην υλοποίηση των Κατανεμημένων Εργαζομένων του προβλήματος των Ν Βασιλισσών, ή σε οποιοδήποτε άλλο πρόγραμμα Κατανεμημένων Εργαζομένων με μη-διακριτούς εργαζόμενους. Ένα άλλο παράδειγμα τέτοιου προγράμματος είναι το πρόβλημα του Περιοδεύοντος Παραγωγού, που αποτελεί μια από τις εργασίες προγραμματισμού στο τέλος του κεφαλαίου.

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

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

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

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


     Next              Up                Back                    Contents

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