Επόμενο:10.1 Δεξαμενές Εργασίας Πάνω: Περιεχόμενα Πίσω: Ασκήσεις
Κεφάλαιο 10o : Αντίγραφα Εργαζομένων
Στους περισσότερους παράλληλους αλγορίθμους το πλήθος των υπολογιστών είναι γνωστό εκ των προτέρων και έτσι αυτοί μπορούν να επιμεριστούν στους διαθέσιμους επεξεργαστές κατά ένα λογικό και ισορροπημένο τρόπο. Αυτός ο επιμερισμός των υπολογιστών συνήθως στηρίζεται στη δομή των δεδομένων με ένα μέρος των δεδομένων να ανατίθεται σε κάθε επεξεργαστή. Αυτό το είδος του παραλληλισμού των δεδομένων χρησιμοποιείται τόσο σε πολυεπεξεργαστές όσο και σε συστήματα κατανεμημένης μνήμης.
Όμως, υπάρχει μια σημαντική κατηγορία αλγορίθμων στους οποίους οι υπολογιστικές εργασίες δεν είναι γνωστές εκ των προτέρων, αλλά δημιουργούνται δυναμικά καθώς εκτελείται το πρόγραμμα. Οι αλγόριθμοι Συνδυαστικής Αναζήτησης είναι τυπικό παράδειγμα αυτής της κατηγορίας - ο χώρος επίλυσης ενός προβλήματος διερευνάται μέσω μονοπατιών αναζήτησης που δημιουργούνται και απορρίπτονται δυναμικά. Το γνωστό πρόβλημα του Περιοδεύοντος Πωλητή είναι ένα παράδειγμα τέτοιων προβλημάτων συνδυαστικής αναζήτησης. Καθώς το πρόγραμμα του Περιοδεύοντος Πωλητή εκτελείται, διάφορες διαδρομές δημιουργούνται και εξαλείφονται με ένα δυναμικό τρόπο. Επίσης οι αλγόριθμοι αναζήτησης γραφημάτων έχουν αυτή την ιδιότητα της δυναμικής δημιουργίας των υπολογιστικών εργασιών. Ένα τυπικό παράδειγμα είναι το Πρόβλημα του Συντομότερου Μονοπατιού κατά τη διάρκεια του οποίου υπο-γραφήματα μέσα στο γράφημα σταδιακά εισάγονται ή αντικαθίστανται από συντομότερα μονοπάτια.
Σε τέτοιους αλγόριθμους με δυναμική δημιουργία εργασιών, το υπολογιστικό φορτίο δεν μπορεί να επιμεριστεί στους επεξεργαστές από την αρχή. Για να επιτύχουμε εξισορρόπηση φορτίου, οι υπολογιστικές εργασίες πρέπει να ανατίθενται σε επεξεργαστές δυναμικά καθώς δημιουργούνται κατά τη διάρκεια εκτέλεσης του προγράμματος. Αυτό επιτυγχάνεται καλύτερα χρησιμοποιώντας έναν νέο τύπο παράλληλου προγραμματισμού που ονομάζεται Αντίγραφα Εργαζομένων. Ίδιες διεργασίες-Εργαζόμενοι ανατίθενται για να εκτελεστούν σε κάθε φυσικό επεξεργαστή και οι υπολογιστικές εργασίες ανατίθενται δυναμικά σε Εργαζόμενους καθώς το πρόγραμμα εκτελείται.
Στο υπόδειγμα των Αντιγράφων Εργαζομένων χρησιμοποιείται μια αφηρημένη δομή δεδομένων που ονομάζεται Δεξαμενή Εργασίας. Μια Δεξαμενή Εργασίας είναι μια συλλογή από περιγραφές εργασιών, με κάθε περιγραφή να καθορίζει μια συγκεκριμένη υπολογιστική εργασία που μπορεί να πραγματοποιείται από οποιονδήποτε από τους εργαζόμενους. Όταν ένας Εργαζόμενος γίνει ανενεργός, παίρνει μια νέα περιγραφή εργασίας από τη Δεξαμενή Εργασίας και στη συνέχεια πραγματοποιεί τον απαιτούμενο υπολογισμό. Κατά τη διάρκεια της εκτέλεσης μιας εργασίας οι Διεργασίες Εργαζόμενοι μπορεί να δημιουργήσουν νέες εργασίες με τις αντίστοιχες περιγραφές, οι οποίες προστίθενται στη Δεξαμενή Εργασίας.
Ο κύριος σκοπός του κεφαλαίου είναι η εφαρμογή των Αντιγράφων Εργαζομένων και των Δεξαμενών Εργασίας σε συστήματα διαμοιραζόμενης μνήμης. Το κεφάλαιο 11 ασχολείται με Αντίγραφα Εργαζομένων σε συστήματα κατανεμημένης μνήμης. Για τις εφαρμογές συστημάτων διαμοιραζόμενης μνήμης τα κανάλια της Multi-Pascal μπορούν να χρησιμοποιηθούν ως η βάση των Δεξαμενών Εργασίας, γιατί αυτά έχουν τη δυνατότητα να συλλέγουν και να κατανέμουν δεδομένα. Όμως, μπορεί να προκύψει ένα σημαντικό πρόβλημα απόδοσης: η συμφόρηση καναλιών. Αν ένα μόνο κανάλι χρησιμοποιείται από όλες τις Διεργασίες Εργαζομένους τότε η συμφόρηση θα μειώσει το συνολικό αριθμό των εργαζομένων. Αυτό το πρόβλημα συμφόρησης λύνεται με την αποκέντρωση της Δεξαμενής Εργασίας σε ένα αριθμό ξεχωριστών καναλιών. Το βασικό θέμα εφαρμογής στην περίπτωση αυτή είναι η εξισορρόπηση φορτίου των διαφορετικών καναλιών, έτσι ώστε όλες οι Διεργασίες Εργαζόμενοι να απασχολούνται.
Το άλλο σημαντικό θέμα είναι ο τερματισμός των Αντιγράφων Εργαζομένων. Οι εργαζόμενοι πρέπει να τερματίσουν τη λειτουργία τους όταν είναι όλοι ανενεργοί και η Δεξαμενή Εργασίας είναι άδεια. Καθώς η Δεξαμενή Εργασίας αποκεντρώνεται, το πρόβλημα τερματισμού γίνεται πιο δύσκολο. Είναι σημαντική η ελαχιστοποίηση της επιπλέον επιβάρυνσης υπολογισμού που δημιουργείται από τον έλεγχο τερματισμού και επίσης η διασφάλιση ότι ο έλεγχος τερματισμού δεν παράγει ανταγωνισμό στη μνήμη. Όταν εφαρμόζονται τα Αντίγραφα Εργαζομένων σε συστήματα κατανεμημένης μνήμης το θέμα του κατανεμημένου τερματισμού γίνεται ιδιαίτερα ενδιαφέρον. Αυτό είναι και το κεντρικό θέμα του κεφαλαίου 11.
Το παρόν κεφάλαιο αρχίζει με μια γενική επισκόπηση των Αντιγράφων Εργαζομένων και της έννοιας της Δεξαμενής Εργασίας. Στη συνέχεια δίνεται ένα συγκεκριμένο παράδειγμα αλγορίθμου που χρησιμοποιεί τα Αντίγραφα Εργαζομένων: ένας παράλληλος αλγόριθμος Συντομότερου Μονοπατιού. Παρακάτω παρουσιάζονται διάφορα θέματα εφαρμογής των Δεξαμενών Εργασίας, με πρωτεύον σκοπό την εξιρορρόπηση φορτίου και τον τερματισμό. Η απόδοση αυτής της εφαρμογής αναλύεται στο κείμενο του παράλληλου αλγορίθμου Συντομότερου Μονοπατιού.
Επόμενο:10.1 Δεξαμενές Εργασίας Πάνω: Περιεχόμενα Πίσω: Ασκήσεις