Next              Up                Back               Contents

Επόμενο:10.2 Αλγόριθμος Συντομότερου Μονοπατιού Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων


 

10.1 Δεξαμενές Εργασίας

 

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

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

 

image

 

ΣΧΗΜΑ 10.1 Αντίγραφα εργαζομένων

 

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

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

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

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

Ο τερματισμός αποτελεί πρόβλημα γιατί είναι μια καθολική ιδιότητα που εξαρτάται από την κατάσταση της Δεξαμενής Εργασίας και όλους τους εργαζόμενους κατά την ίδια χρονική στιγμή. Φυσικά, ένας αλγόριθμος Αντιγράφων Εργαζομένων “θέλει” να τελειώνει όταν δεν υπάρχει άλλη δουλειά να κάνει, και αυτό συμβαίνει όταν δεν υπάρχουν άλλες περιγραφές εργασιών για να προσπελαστούν. Φυσικά, η Δεξαμενή Εργασίας πρέπει να είναι άδεια για να τερματιστεί ο αλγόριθμος. Όμως, ακόμα και όταν η Δεξαμενή Εργασίας είναι άδεια ένας ενεργός εργαζόμενος μπορεί να θέλει να προσθέσει κάποιες νέες υπολογιστικές εργασίες στη Δεξαμενή. Έτσι, η συνθήκη τερματισμού απαιτεί ότι η Δεξαμενή εργασίας είναι άδεια και όλες οι διεργασίες εργαζόμενοι είναι αδρανείς (περιμένοντας για την επόμενη υπολογιστική εργασία). Αυτή η συνθήκη τερματισμού είναι ιδιόρρυθμη στον έλεγχο, ειδικά στην περίπτωση των συστημάτων κατανεμημένης μνήμης. Ο σκοπός κάθε υλοποίησης είναι πρώτα να κάνουμε αποδοτικό τον έλεγχο τερματισμού, έτσι ώστε να μην καθυστερεί τον αλγόριθμο ή προκαλεί σημεία συμφόρησης της απόδοσης. Ένας δευτερεύων στόχος είναι να κάνουμε τον έλεγχο τερματισμού απλό και κομψό, για να ελαχιστοποιεί την προγραμματιστική προσπάθεια και να μειώνει την πιθανότητα λαθών στον κώδικα.


     Next              Up                Back               Contents

Επόμενο:10.2 Αλγόριθμος Συντομότερου Μονοπατιού Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων