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

11.5 Συμπίεση Εργασίας

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

11.5.1 Νέα υλοποίηση της Getwork

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

Αυτή η νέα υλοποίηση της Getwork απαιτεί κάποια εσωτερική τροποποίηση. Η προηγούμενη έκδοση της Getwork διαβάζει αντικείμενα από την θύρα επικοινωνίας μέχρι να βρει το πρώτο αντικείμενο εργασίας. Η νέα έκδοση πρέπει να διαβάζει αντικείμενα εργασίας μέχρι να αδειάσει η θύρα. Κάθε αντικείμενο που συναντιέται στέλνεται στην ειδική διαδικασία “Compression” (συμπίεση) που υπάρχει στον εργαζόμενο. Σε αυτή την περίπτωση η διαδικασία συμπίεσης απλά καταγράφει το ελάχιστο των αντικειμένων εργασίας. Καθώς τα αντικείμενα εργασίας διαβάζονται από την θύρα, η Getwork μπορεί να βρει μηνύματα επιβεβαίωσης τα οποία επίσης πρέπει να απομακρύνονται. Όταν η θύρα είναι τελικά εντελώς άδεια η Getwork επιστρέφει το συμπιεσμένο αντικείμενο εργασίας στον εργαζόμενο. Βέβαια, η ανίχνευση τερματισμού και το δένδρο των ενεργών εργαζομένων πρέπει να αποτελούν τμήμα των υπολογισμών της Getwork.

Ο πιο απλός τρόπος να περιγράψουμε τη δομή της νέας διαδικασίας Getwork είναι με ένα σχεδιάγραμμα αλλαγής κατάστασης, σαν αυτό που παρουσιάζεται στο σχήμα 11.8. Οι τρεις καταστάσεις είναι Έτοιμη (Ready), Ενεργή (Active) και Αδρανής (Idle). Κάθε μια αναπαριστά μια πιθανή κατάσταση αλλαγής που ορίζεται από την συνθήκη που προκαλεί αυτή την αλλαγή και την ενέργεια που λαμβάνεται ως αποτέλεσμα της αλλαγής. Η συνθήκη φαίνεται πρώτη με κεφαλαία γράμματα και αναφέρεται στον τύπο του αντικειμένου που βρέθηκε πρώτο στην θύρα επικοινωνίας. Η ενέργεια που συμβαίνει κατά τη διάρκεια της αλλαγής φαίνεται μέσα στην παρένθεση. Η αίτηση του εργαζόμενου για νέο αντικείμενο εργασίας τον εισάγει στο διάγραμμα στην κατάσταση έτοιμος, δηλώνοντας ότι είναι έτοιμος να λάβει ένα νέο αντικείμενο εργασίας. Το πρώτο αντικείμενο εργασίας που λαμβάνεται προκαλεί σε αυτόν την αλλαγή στην κατάσταση ενεργός κατά τη διάρκεια της οποίας όλα τα αντικείμενα εργασίας απομακρύνονται από τη θύρα και συμπιέζονται. Όταν η θύρα αδειάσει η διαδικασία Getwork θα επιστρέψει στον εργαζόμενο.

ΣΧΗΜΑ 11.8 Διαδικασία Getwork με συμπίεση εργασίας

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

11.5.2 Ασύγχρονοι Αλγόριθμοι

Το υπόδειγμα των Κατανεμημένων Εργαζομένων με συμπίεση εργασίας μπορεί να χρησιμοποιηθεί για την υλοποίηση μιας σημαντικής κατηγορίας παράλληλων αλγορίθμων που ονομάζονται ασύγχρονοι επαναληπτικοί αλγόριθμοι. Στο κεφάλαιο 6 εξετάσαμε την περίπτωση των σύγχρονων επαναληπτικών αλγορίθμων που χρησιμοποιούνται συχνά για την επίλυση συστημάτων εξισώσεων. Σε τέτοιους αλγόριθμους υπάρχει ένα διάνυσμα κατάστασης X=(x₁, x₂,…, x_n) του οποίου η τιμή υπολογίζεται επαναληπτικά μέχρι η αλλαγή να γίνει μικρότερη από την επιθυμητή ανοχή. Η τελική τιμή του X είναι η λύση των εξισώσεων. Αυτό το είδος των επαναληπτικών αλγορίθμων μπορεί εύκολα να παραλληλιστεί με την ανάθεση ενός ή περισσοτέρων αντικειμένων του διανύσματος κατάστασης σε κάθε επεξεργαστή. Με αυτή τη μέθοδο οι επεξεργαστές πρέπει να συγχρονίζονται μετά από κάθε επανάληψη για να εξασφαλίζουν ότι όλες οι τιμές του νέου διανύσματος κατάστασης έχουν υπολογιστεί πριν να προχωρήσουν στην επόμενη επανάληψη.

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

Για να αυξήσουμε την αποδοτικότητα μπορούμε να επιτρέψουμε στους επεξεργαστές να προχωρήσουν στην επόμενη επανάληψη πριν να λάβουν όλες τις νέες τιμές. Κάθε τιμή που δεν φτάσει έγκαιρα θα χρησιμοποιηθεί στις επόμενες επαναλήψεις. Αυτό το είδος αλγόριθμου ονομάζεται ασύγχρονος αλγόριθμος, γιατί δεν υπάρχει συγχρονισμός μετά από κάθε επανάληψη. Η κύρια δυσκολία τέτοιων ασύγχρονων αλγορίθμων είναι ότι οι συνθήκες που απαιτούνται για την σύγκλιση μπορεί να είναι πιο αυστηρές. Παρόλα αυτά υπάρχουν πολλοί σημαντικοί παράλληλοι αλγόριθμοι που μπορούν να μοντελοποιηθούν κατά αυτό τον ασύγχρονο τρόπο. Για περισσότερες λεπτομέρειες δες Bertsekas και Tsitsiklis [1989].

Υποθέστε ότι έχουμε n επεξεργαστές και σε κάθε i επεξεργαστή έχει ανατεθεί η τιμή x_i από το διάνυσμα κατάστασης X. Κάθε επεξεργαστής έχει το δικό του τοπικό αντίγραφο του διανύσματος κατάστασης και ξαναϋπολογίζει το x_i από αυτό το τοπικό διάνυσμα κατάστασης κατά τη διάρκεια κάθε επανάληψης. Μετά από αυτόν τον επανυπολογισμό ο επεξεργαστής i διαδίδει την νέα τιμή του x_i σε όλους τους άλλους επεξεργαστές. Στην ασύγχρονη μοντελοποίηση ο επεξεργαστής δεν χρειάζεται να περιμένει για όλες τις νέες τιμές του διανύσματος κατάστασης. Απλά διαβάζει τις νέες τιμές που έχουν φτάσει και προχωράει στον επόμενο υπολογισμό του x_i. Με αυτόν τον τρόπο οι νέες τιμές του διανύσματος κατάστασης κινούνται σταθερά μέσα στο δίκτυο επικοινωνίας και απορροφούνται από τους επεξεργαστές καθώς φτάνουν σε αυτούς. Κανένας επεξεργαστής δεν περιμένει για τις καθυστερημένες τιμές. Συνεπώς, ο υπολογισμός μπορεί να επικαλυφθεί εντελώς από την επικοινωνία και έτσι να μειωθεί ο συνολικός χρόνος εκτέλεσης.

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

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

Worker Process i:

 

VAR X: ARRAY [1..n] OF REAL; (*Τοπικό αντίγραφο του διανύσματος κατάστασης*)

 

BEGIN


REPEAT


    Compute new xi from current state vector X;


    IF ABS(new xi - old xi) > tolerance THEN

    BEGIN

        FOR destination:= 1 TO n DO (*Αποστολή αντιγράφου σε όλους*)

            Putwork(destination, new xi);

        Copy new xi into X[i]

    END;

    Call Getwork to read all state vector values from my port;

UNTIL done;

END;

Για το πρόγραμμα του Συντομότερου Μονοπατιού η λειτουργία της συμπίεσης εργασίας είναι να καταγράφει το ελάχιστο των αντικειμένων εργασίας που διαβάζονται από τη θύρα. Για αυτή την ασύγχρονη επανάληψη η λειτουργία της συμπίεσης εργασίας έχει σχέση με την εγγραφή κάθε αντικειμένου εργασίας στην κατάλληλη θέση του τοπικού διανύσματος κατάστασης X. Κάθε αντικείμενο εργασίας πρέπει να έχει δύο μέρη, τον δείκτη προς το διάνυσμα κατάστασης και την νέα του τιμή. Η λειτουργία της διαδικασία Getwork είναι ίδια με αυτή του σχήματος 11.8 και συμπεριλαμβάνει και την ανίχνευση τερματισμού. Η διαδικασία Putwork είναι ουσιαστικά η ίδια με την αρχική έκδοση που αναπτύχθηκε για το πρόγραμμα του Συντομότερου Μονοπατιού χωρίς την συμπίεση εργασίας (δες σχήμα 11.5). Το υπόδειγμα των Κατανεμημένων Εργαζομένων μπορεί να εφαρμοστεί στην υλοποίηση ασύγχρονων αλγορίθμων παρόλο που με μια πρώτη ματιά φαίνονται ότι είναι αρκετά διαφορετικοί. Μια από τις εργασίες προγραμματισμού στο τέλος του κεφαλαίου ασχολείται με το γράψιμο ενός προγράμματος Κατανεμημένων Εργαζομένων για την ασύγχρονη λύση ενός συστήματος γραμμικών εξισώσεων.

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