11.4 Ανάλυση Απόδοσης

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

11.4 Ανάλυση Απόδοσης

11.4.1 Παράγοντες που επηρεάζουν την απόδοση

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

Το σχήμα δεν παρουσιάζει τη δημιουργία της διεργασίας και τη φάση κατανομής των δεδομένων εφόσον αυτό το θέμα απόδοσης αναλύθηκε στο κεφάλαιο 9. Η συνολική επιτάχυνση που επιτυγχάνεται από αυτό το υπολογιστικό μέρος του προγράμματος είναι 19, χρησιμοποιώντας 31 εργαζόμενους. Μπορούμε να δούμε ότι αυτή η μείωση της επιτάχυνσης κατά 38% οφείλεται σε πολλούς παράγοντες. Στην αρχή χρειάζεται κάποιος χρόνος για να παραχθεί η εργασία που θα δεσμεύσει όλους τους εργαζόμενους. Θυμηθείτε ότι ο κόμβος 1 είναι το μοναδικό αντικείμενο εργασίας όταν αρχίζει η εκτέλεση. Ο εργαζόμενος 1 θα δημιουργήσει σταδιακά νέα αντικείμενα εργασίας και θα τα κατανείμει στους κατάλληλους εργαζομένους, οι οποίοι επίσης θα αρχίσουν να δημιουργούν νέα αντικείμενα εργασίας.

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

Αρχική δημιουργία της εργασίας 12%

Μη-ισορροπημένο φορτίο 20%

Ανίχνευση τερματισμού 6%

11.4.2 Καθυστέρηση επικοινωνίας

Το στιγμιότυπο της απόδοσης του σχήματος 11.6 πραγματοποιήθηκε με την βασική καθυστέρηση επικοινωνίας ίση με 0. Έχει ενδιαφέρον η ανάλυση της επιρροής της καθυστέρησης επικοινωνίας στην απόδοση του προγράμματος. Η καθυστέρηση επικοινωνίας προκαλεί μια χρονική καθυστέρηση μεταξύ της αποστολής και της λήψης των αντικειμένων εργασίας.

**** ΣΧΗΜΑ 11.6 Πρόγραμμα Συντομότερου Μονοπατιού χωρίς καθυστέρηση

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

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

Η θέση ενός δεδομένου εργαζόμενου στον δένδρο των ενεργών εργαζομένων δηλώνει πόσο έχει επηρεαστεί από την καθυστέρηση επικοινωνίας. Κάθε εργαζόμενος λαμβάνει το πρώτο αντικείμενο εργασίας του από τον γονέα του, οποίος το λαμβάνει με τη σειρά του από τον γονέα του επίσης κ.ο.κ. Ένας εργαζόμενος στο επίπεδο 3 πρέπει να περιμένει τρία βήματα επικοινωνίας πριν να λάβει το πρώτο αντικείμενο εργασίας του. Για παράδειγμα, στο σχήμα 11.3 ο εργαζόμενος W18 θα περιμένει για τρία βήματα επικοινωνίας: W1 ως W2, W2 ως W3 και W3 ως W18. Η μορφή αυτού του δένδρου ενεργών εργαζομένων εξαρτάται από τη δομή του συγκεκριμένου γραφήματος και επίσης από τη δυναμική του προγράμματος. Για να πάρουμε μια ιδέα σχετικά με την αναμενόμενη μείωση της απόδοσης σε ένα μεγάλο εύρος προγραμμάτων, ας κάνουμε τις παρακάτω απλές υποθέσεις:

1. Το δένδρο των ενεργών εργαζομένων είναι ένα πλήρες δυαδικό δένδρο.

2. Κάθε εργαζόμενος μπορεί να εμφανιστεί οπουδήποτε μέσα στο δένδρο.

Αυτές οι υποθέσεις επιτρέπουν μια ακριβή ανάλυση με τη χρήση της θεωρίας των πιθανοτήτων για τον υπολογισμό την αναμενόμενη μείωση της απόδοσης που είναι αποτέλεσμα των καθυστερήσεων επικοινωνίας. Σχετικά με την δεύτερη υπόθεση η αναμενόμενη καθυστέρηση για κάθε βήμα επικοινωνίας στο δένδρο είναι η μέση καθυστέρηση επικοινωνίας όλων των ζευγών των επεξεργαστών στο σύστημα κατανεμημένης μνήμης. Για ένα σύστημα κατανεμημένης μνήμης Υπερκύβου με διάσταση d και βασική καθυστέρηση επικοινωνίας D, αναμενόμενη καθυστέρηση είναι dD/2. Συνεπώς, ένας εργαζόμενος σε επίπεδο i θα έχει idD/2 αναμενόμενη καθυστέρηση επικοινωνίας από την ρίζα. Αυτό είναι αποτέλεσμα του γεγονότος ότι οι προσδοκίες ενός αθροίσματος τυχαίων μεταβλητών είναι το άθροισμα των προσδοκιών.

Για να βρούμε την αναμενόμενη καθυστέρηση από την ρίζα προς όλους τους εργαζόμενους η έκφραση idD/2 πρέπει να τεθεί ως ο μέσος όρος σε όλο το δένδρο. Εφόσον i είναι το επίπεδο του δένδρου αυτός ο μέσος όρος μπορεί να υπολογιστεί ως dD/2 επί το μέσο βάθος του δένδρου. Από την πρώτη υπόθεση παίρνουμε ότι το δένδρο είναι ένα πλήρες δυαδικό δένδρο. Ένας Υπερκύβος με διάσταση d έχει 2^d επεξεργαστές και συνεπώς αποδίδει ένα δένδρο με d-1 βάθος. Μια πολύ καλή προσέγγιση του μέσου βάθους ενός οποιουδήποτε δυαδικού δένδρου είναι το συνολικό βάθος μείον 1, δηλαδή στην περίπτωση μας d-2. Συνεπώς, η αναμενόμενη καθυστέρηση επικοινωνίας που συναντά κάθε Εργαζόμενος στην λήψη του πρώτου αντικειμένου εργασίας είναι:

Αναμενόμενη Καθυστέρηση Δημιουργίας του Δένδρου:

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

Αναμενόμενη Καθυστέρηση Τερματισμού του Δένδρου:

Μετά την απαλοιφή του δένδρου ενεργών εργαζομένων, ο εργαζόμενος 1 θα στείλει ένα μήνυμα στην διεργασία επόπτη που εκτελείται στον επεξεργαστή 0, ο οποίος θα στείλει στην συνέχεια μηνύματα τερματισμού προς όλες τις διεργασίες εργαζόμενους (δες σχήμα 11.5). Μετά τον τερματισμό κάθε εργαζόμενος στέλνει ένα μήνυμα στην πρωτεύουσα διεργασία στον επεξεργαστή 0. Συνεπώς, η συνολική καθυστέρηση επικοινωνίας κατά τη διάρκεια αυτής της τελικής φάσης τερματισμού είναι το διπλάσιο της διαμέτρου του δικτύου επικοινωνίας: 2dD. Αν προσθέσουμε και αυτή την καθυστέρηση στις αναμενόμενες καθυστερήσεις δημιουργίας και καταστροφής του δένδρου τότε:

Συνολική Αναμενόμενη Καθυστέρηση Επικοινωνίας: Dd²

Αυτή η έκφραση δίνει μια γενική ιδέα της αναμενόμενης αύξησης στον συνολικό χρόνο εκτέλεσης του προγράμματος που είναι αποτέλεσμα των καθυστερήσεων επικοινωνίας του συστήματος κατανεμημένης μνήμης. Παρουσιάζουν επίσης ενδιαφέρον οι παρατηρούμενες καθυστερήσεις στο πρόγραμμα του Συντομότερου Μονοπατιού. Το ίδιο δείγμα γραφήματος που χρησιμοποιήσαμε για τη δημιουργία του στιγμιότυπου του σχήματος 11.6 χρησιμοποιείται και στην Multi-Pascal για τον προσδιορισμό του χρόνου εκτέλεσης του προγράμματος για ένα μεγάλο εύρος καθυστερήσεων επικοινωνίας. Τα αποτέλεσμα φαίνονται στο σχήμα 11.7. Ο οριζόντιος άξονας είναι η βασική καθυστέρηση επικοινωνίας D, που παίρνει τιμές από το 0 μέχρι το 100. Ο κάθετος άξονας δείχνει το χρόνο εκτέλεσης του υπολογιστικού μέρους του προγράμματος και δεν περιλαμβάνει τη δημιουργία της διεργασίας και την κατανομή των αρχικών δεδομένων, όπως και στο σχήμα 11.6.

ΣΧΗΜΑ 11.7 Απόδοση του συντομότερου μονοπατιού

Με την επιλογή συμφόρηση ανενεργή η καμπύλη απόδοσης φαίνεται να είναι γραμμική με κλήση 23. Η παραπάνω μαθηματική ανάλυση έγινε χωρίς να λάβουμε υπόψη μας τη συμφόρηση. Εφόσον ο Υπερκύβος έχει διάσταση 5, η ανάλυση προβλέπει αναμενόμενη αύξηση του χρόνου εκτέλεσης ίση με 25D. Αυτή η προβλεπόμενη κλήση του 25D είναι εκπληκτικά κοντά στην παρατηρούμενη κλήση 23, λαμβάνοντας υπόψη ότι η ανάλυσή μας βασίστηκε στην υπόθεση ότι το δένδρο των ενεργών εργαζομένων είναι ένα πλήρες δυαδικό δένδρο, που στην ουσία δεν είναι και το θέμα του προγράμματος. Παρόλα αυτά η πραγματική καθυστέρηση στην δημιουργία και την καταστροφή του δένδρου είναι κοντά στην πρόβλεψη.

Με την επιλογή συμφόρηση ενεργή το σχήμα δείχνει μια σημαντική αύξηση του χρόνου εκτέλεσης, ειδικά στις υψηλότερες τιμές της βασικής καθυστέρησης επικοινωνίας. Αυτή η συμφόρηση συμβαίνει κατά τη διάρκεια της τελικής φάσης του τερματισμού όταν ο επόπτης στέλνει τα μηνύματα τερματισμού προς όλες τις διεργασίες. Αν η βασική καθυστέρηση επικοινωνίας είναι μεγάλη τότε δημιουργείται κάποια συμφόρηση καθώς όλα τα μηνύματα φεύγουν από την διεργασία 0. Ένα παρόμοιο είδος συμφόρησης προκύπτει μετά τον τερματισμό των διεργασιών και όταν τα μηνύματα τερματισμού επιστρέφουν πίσω στην πρωτεύουσα διεργασία που εκτελείται στον επεξεργαστή 0. Αυτό το πρόβλημα συμφόρησης μπορεί να μειωθεί σημαντικά αν μεταβάλλουμε τον επόπτη ώστε να χρησιμοποιεί μια διάδοση Υπερκύβου για τα μηνύματα τερματισμού. Το θέμα αυτό αφορά μια από τις ασκήσεις στο τέλος του κεφαλαίου.

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

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

Ένα άλλο σημαντικό θέμα είναι η επίδραση της αύξησης το φόρτου εργασίας στο πρόβλημα της εξισορρόπησης του φορτίου. Στο σχήμα 11.6 η ανισορροπία φορτίου είχε σαν αποτέλεσμα την μείωση της επιτάχυνσης κατά 20%. Επίσης φάνηκε ότι η ανισορροπία φορτίου γινόταν μικρότερη καθώς αυξανόταν ο φόρτος εργασίας. Για να αναλύσουμε περισσότερο το θέμα της εξισορρόπησης φορτίου ας θεωρήσουμε την τυχαία κατανομή n αντικειμένων εργασίας σε p επεξεργαστές. Αν ένας μεγάλος αριθμός κόμβων έχει ανατεθεί σε κάθε εργαζόμενο, τότε η τυχαία κατανομή μπορεί να θεωρηθεί σαν ένα λογικό μοντέλο. Σε αυτή την περίπτωση, μπορούμε να δούμε κάποια ειδικά χαρακτηριστικά της φύσης του προβλήματος της εξισορρόπησης φορτίου. Καθένα από τα n αντικείμενα εργασίας ανατίθονται σε έναν δεδομένο εργαζόμενο με πιθανότητα 1/p. Συνεπώς, ο συνολικός φόρτος εργασίας που ανατίθεται σε έναν εργαζόμενο είναι το άθροισμα των n δοκιμών Bernoulli, με πιθανότητα 1/p. Από τις ιδιότητες των δοκιμών Bernoulli το αναμενόμενο μέγεθος του φόρτου εργασίας είναι n/p. Αυτό είναι αντίστοιχο με τη διαίσθησή μας ότι ο μέσος φόρτος εργασίας είναι το συνολικό πλήθος των αντικειμένων εργασίας δια τον αριθμό των εργαζομένων.

Η ανισορροπία φορτίου προκύπτει από τις μεταβολές στον αριθμό των αντικειμένων εργασίας που έχουν ανατεθεί σε κάθε εργαζόμενο. Αν κάποιοι εργαζόμενοι λάβουν περισσότερα αντικείμενα εργασίας τότε θα πρέπει να υπολογίζουν για μεγαλύτερο χρονικό διάστημα, σε σχέση με άλλους που θα τελειώσουν πολύ νωρίτερα. Το αποτέλεσμα είναι ένα χρονικό διάστημα κατά το οποίο πολλοί εργαζόμενοι είναι αδρανείς μειώνοντας έτσι τη μέση χρήση επεξεργαστή και αυξάνοντας το χρόνο εκτέλεσης του προγράμματος. Στο μοντέλο κατανομής φορτίου Bernoulli μια καλή εκτίμηση της αναμενόμενης μεταβολής του φόρτου εργασίας που ανατίθεται σε κάθε εργαζόμενο είναι η τυπική απόκλιση, που σε αυτή την περίπτωση είναι (n/p)^1/2. Αυτό σημαίνει ότι το μέγεθος της μεταβολής αναμένεται να αυξηθεί καθώς αυξάνεται ο συνολικός αριθμός φόρτου εργασίας n. Όμως, η αναμενόμενη μεταβολή μειώνεται ως ποσοστό του μέσου φόρτου εργασίας ανά εργαζόμενο. Ο μέσος φόρτος εργασίας αυξάνεται γραμμικά σύμφωνα με το n, αλλά η μεταβολή παρουσιάζει αύξηση μόνο ως τετραγωνική ρίζα του n. Συνεπώς, η μείωση της απόδοσης που έχει σχέση με την ανισορροπία φορτίου πρέπει να μειώνεται καθώς ο συνολικός φόρτος εργασίας αυξάνεται για ένα δοσμένο αριθμό εργαζομένων.