Ενας από τους βασικούς στόχους κατά τη σχεδίαση του ArrayTracer ήταν η ελαχιστοποίηση του μεγέθους των αρχείων ιχνών που παράγονται κατά τη διαδικασία ιχνοληψίας και η όσο το δυνατόν μικρότερη διαστολή του χρόνου εκτέλεσης της εφαρμογής μετά την εισαγωγή του κώδικα καθοδήγησης.
Για το λόγο αυτό καθορίστηκε η μορφή φορμών ιχνοληψίας που παρουσιάστηκαν σε προηγούμενη παράγραφο. Τα ίχνη αυτής της μορφής δεν καθορίζουν πλήρως την ακολουθία γεγονότων που λαβαίνουν χώρα κατά την εκτέλεση μιας διεργασίας. Επιπλέον δεν καθορίζεται και η καθολική σειρά των γεγονότων του συνόλου των διεργασιών της υπο μελέτη εφαρμογής.
Ενα παράδειγμα φαίνεται στο σχήμα .
Στην περίπτωση (a) βλέπουμε τον κώδικα καθοδήγησης που καθορίζει πλήρως ένα γεγονός κλήσης μιας υπορουτίνας. Παρατηρούμε ότι παράγονται δύο ίχνη, το πρώτο καθορίζει την έναρξη του γεγονότος και το δεύτερο το πέρας του.
Στην περίπτωση (b) βλέπουμε τον κώδικα καθοδήγησης που εισάγεται από το δικό μας εργαλείο. Παράγεται ένα μόνο ίχνος που περιγράφει την απόλυτη χρονική διάρκεια του γεγονότος.
Figure: Παράδειγμα μείωσης του κώδικα καθοδήγησης με χρήση του
ArrayTracer
Συνεπώς το μέγεθος των ιχνών που παράγονται περιορίζεται στο μισό, ενώ στο μισό περιορίζεται και η διαστολή του πηγαίου κώδικα με συνέπεια την μείωση της διαστολής του χρόνου εκτέλεσης.
Ολα τα παραπάνω προυποθέτουν ότι κατα τη διαδικασία της ανάλυσης θα πρέπει, με χρήση του περιορισμένου αριθμού των ιχνών να καθοριστούν τα εξής.
Για την υλοποίηση του πρώτου στόχου, κατά την ανάλυση των ιχνών δημιουργείται μια ακολουθία καταστάσεων, για κάθε διεργασία, που καταλήγει στην παραγωγή γεγονότων μορφής PICL.
Για την υλοποίηση του δεύτερου στόχου κατασκευάζονται λογικές χρονοσφραγίδες με χρήση της σχέσης διάταξης Lamport [17].
Πριν την περιγραφή της τεχνικής αυτής θα μελετήσουμε τον τρόπο που αντιμετωπίζεται το πρόβλημα της σειριοποίησης, καθώς και τη μορφή των ιχνών σε άλλα εργαλεία παρόμοια με τον ArrayTracer
Καθε γεγονός της παράλληλης βιβλιοθήκης PICL [13] αντιστοιχεί σε δύο ίχνη που αποθηκεύονται σε κάποιο αρχείο εξόδου. Το πρώτο ίχνος περιγράφει την αρχή του αντίστοιχου γεγονότος και το δεύτερο το πέρας αυτού. Επιπλέον το PICL παράγει ίχνη που αντιστοιχούν σε κλήσεις υπολογιστικών συναρτήσεων και δίνει και τη δυνατότητα στο χρήστη να καθορίζει την ιχνοληψία γεγονότων της επιλογής του.
Τέλος τα ίχνη είναι σε ASCII μορφή κάτι που επαυξάνει το μέγεθος των αρχείων που παράγονται.
Επιπλέον το PICL χρησιμοποιεί το ρολόι συστήματος του κάθε επεξεργαστή που συμμετέχει στο παράλληλο σύστημα, για την παραγωγή της χρονοσφραγίδας του κάθε ίχνους. Τα ρολόγια αυτά περιοδικά συγχρονίζονται με το ρολόι του επεξεργαστή στον οποίο εκτελείται η διεργασία που δημιούργησε όλες τις άλλες. Συνέπεια αυτής της διαδικασίας όμως είναι να επαυξάνεται ο χρόνος εκτέλεσης της εφαρμογής. Ακόμη η σειριοποίηση των ιχνών και η αποθήκευσή τους γίνεται στον επεξεργαστή που ξεκίνησε η εφαρμογή. Για το λόγο αυτό γίνεται ανταλλαγή μηνυμάτων με σκοπό την αποστολή των ιχνών στον επεξεργαστή που ξεκίνησε η εφαρμογή.
Ο ArrayTracer εξάγει ένα μόνο ίχνος για κάθε γεγονός, το οποίο περιέχει τη χρονική διάρκεια του γεγονότος, στην περίπτωση που αυτή ενδιαφέρει. Επιπλέον τα ίχνη που παράγονται είναι σε binary μορφή. Η σειριοποίηση των ιχνών επιλύνεται όπως αναφέρθηκε χρησιμοποιώντας τις σχέσεις εξάρτησης που ισχύουν μεταξύ των διεργασιών της εφαρμογής. Αναλυτικά η διαδικασία θα περιγραφεί σε επόμενη παράγραφο.
Για να μελετήσουμε τη συμπεριφορά των δύο εργαλείων εκτελέσαμε τα τρία παρακάτω πειράματα :
Χρησιμοποιήσαμε δύο σειριακές εφαρμογές, ένα αλγόριθμο λείανσης και
ένα πυρήνα που εκτελεί πολλαπλασιαμό πινάκων. Για τις δύο αυτές
εφαρμογές προγραμματίσαμε το PICL να εξάγει ένα ίχνος για κάθε
προσπέλαση μεταβλητής. Η μορφή του ίχνους είναι καθορισμένη από το
PICL για γεγονότα που καθορίζονται από το χρήστη. Το ίχνος περιέχει
χρονοσφραγίδα που καθορίζει τη χρονική στιγμή που συνέβει η
προσπέλαση.
Το αντίστοιχο ίχνος που παράγει ο ArrayTracer δεν
περιέχει χρονοσφραγίδα. Τα αποτελέσματα της σύγκρισης φαίνονται στο
σχ. .
Συνεπώς παρατηρούμε ότι η καθυστέρηση που εισάγεται από τον ArrayTracer είναι πολύ μικρή σε σχέση με αυτή του PICL. Η αναλογία του μεγέθους του παραγόμενου αρχείου είναι 1/3.79 για τον ArrayTracer. Επιπλέον από τον ArrayTracer αποφεύγεται η κλήση του λειτουργικού συστήματος για τον προσδιορισμό της χρονικής στιγμής που συνέβει το κάθε γεγονός.
Βέβαια η δυνατότητα αυτή που προσφέρεται από το PICL είναι επιπρόσθετη καθώς ο βασικός του στόχος είναι η ιχνοληψία δεδομένων που σχετίζονται με την επικοινωνία. Για το λόγο αυτό ακολουθούν τα δύο επόμενα πειράματα.
Figure: ArrayTracer vs. PICL: Πρώτο πείραμα
Στο πείραμα αυτό χρησιμοποιήσαμε ένα παραλληλοποιημένο αλγόριθμο λείανσης. Πρόκειται για ένα μοντέλλο αφέντη σκλάβου, όπου η διεργασία αφέντης κατάνεμει το πρόβλημα στις διεργασίες σκλάβους. Αυτές εκτελούν τον αλγόριθμο και επιστρέφουν τα αποτελέσματα στον αφέντη. Εκτελέσαμε την εφαρμογή σε 2, 4, 8 DEC ALPHA 3300 για 2 διαφορετικά προβλήματα μεγέθους 1000Χ1000, 2000Χ2000.
Figure: ArrayTracer vs. PICL: Δεύτερο πείραμα
Ιχνοληπτήθηκαν μόνο τα γεγονότα αποστολής και παραλαβής μηνυμάτων. Αυτό σημαίνει ότι αναμένουμε να εισάγεται μικρή καθυστέρηση τόσο από το PICL όσο και από τον ArrayTracer. Επιπλέον τα μεγέθη των ιχνών που παράγονται είναι παρόμοιου μεγέθους. Τα ίχνη που παράγει ο ArrayTracer για τα γεγονότα επικοινωνίας είναι τα μεγαλύτερα σε μέγεθος, ανάλογα με αυτά που σχετίζονται με τον κώδικα και τις προσπελάσεις μεταβλητών. Επιπλέον ο ArrayTracer εκτελεί δύο κλήσεις του λειτουργικού συστήματος για να προσδιορίσει τη χρονική διάρκεια του γεγονότος. Ανάλογες κλήσεις εκτελούνται και από το PICL, μια για τον προσιορισμό της χρονοσφραγίδας του κάθε ίχνους που παράγεται, συνολικά δύο για κάθε γεγονός επικοινωνίας.
Από τα σχ. .
,
.
παρατηρούμε ότι οι χρόνοι εκτέλεσης των εφαρμογων σε
PVM, PICL και PICL που παράγει ίχνη είναι περίπου ο ίδιος
κάτι που δικαιολογείται αφού η επικοινωνία είναι
περιορισμένη, συνεπώς δεν ιχνοληπτείται μεγάλος αριθμός
γεγονότων. Στην περίπτωση όμως του ArrayTracer ο χρόνος
εκτέλεσης παρουσιάζει σημαντική αύξηση κάτι που δεν έπρεπε να
ισχύει. Αυτό οφείλεται στο γεγονός της δημιουργίας της διεργασίας
συλλέκτη η οποία εκτελεί busy waiting. Μάλιστα μπορούμε να
παρατηρήσουμε ότι μειώνοντας τον αριθμό των επεξεργαστών του
συστήματος, αυξάνει η καθυστέρηση που εισάγεται από τον
ArrayTracer, σχ.
.
,
.
. Αυτό ισχύει
διότι αυξάνει ο υπολογιστικός χρόνος των διεργασιών και συνεπώς η
διεργασία συλλέκτης τις καθυστερεί περισσότερο.
Το πείραμα αυτό είναι αντίστοιχο με το προηγούμενο καθώς η εφαρμογή είναι η ίδια αλλά το μέγεθος του προβλήματος μικρότερο και συνεπώς ο περισσότερος χρόνος εκτέλεσης της εφαρμογής δαπανάται για επικοινωνία των διεργασιών. Για το λόγω αυτό και δεν παρατηρούμε επιτάχυνση στην εφαρμογή σε σχέση με τη σειριακή.
Εκτελέσαμε τη εφαρμογή σε PICL και ArrayTracer se 2, 4, 8 DEC ALPHA 3300. Τα μεγέθη των προβλημάτων ήταν 150Χ150, 200Χ200, 250Χ250.
Τα αποτελέσματα που προκύπτουν φαίνονται στο σχ..
Παρατηρούμε ότι ο ArrayTracer εισάγει μικρότερη καθυστέρηση από
το PICL σε όλες τις περιπτώσεις. Επίσης η διαφορά τους αυξάνει
όσο αυξάνεται ο αριθμός των επεξεργαστών στους οποίους εκτελείται η
εφαρμογή. Το γεγονός αυτό είναι μια ένδειξη για το λόγο που υπερτερεί
ο ArrayTracer. Ο πιθανός λόγος είναι ότι τα ίχνη που παράγονται
από το PICL σειριοποιούνται και γράφονται σε ένα
αρχείο στο δίσκο του επεξεργαστή που δημιουργεί όλες τις υπόλοιπες
διεργασίες. Για να γίνει αυτό ανταλάσσονται κάποια μηνύματα με
συνέπεια την αύξηση της καθυστέρησης. Αντίθετα
στην περίπτωση του ArrayTracer τα ίχνη δεν
περνάνε από διαδικασία σειριοποίησης, αλλά γράφονται στους τοπικούς
δίσκους των επεξεργαστών. Η ανταλλαγές μηνυμάτων που γίνονται με τον
συλλέκτη είναι στον ίδιο επεξεργαστή και δεν κοστίζουν αφού το μήνυμα
δεν "διανύει το σύρμα".
Τέλος επειδή η επικοινωνία είναι σταθερή όσο αυξάνει το μέγεθος του προβλήματος, τόσο μειώνεται η καθυστέρηση που εισάγεται από τα δύο εργαλεία.
Figure: ArrayTracer vs. PICL: Τρίτο πείραμα
Από το δεύτερο πείραμα προέκυψε μια σημαντική αδυναμία του ArrayTracer, καθώς όσο μειώνεται ο χρόνος που δαπανάται για εξαγωγή πληροφορίας, σε σχέση με το χρόνο εκτέλεσης της εφαρμογής, τόσο αυξάνει η καθυστέρηση που εισάγεται.
Στο τρίτο πείραμα το μέγεθος του προβλήματος είναι μικρό με συνέπεια να φαίνεται το κόστος της επικοινωνίας για την παραγωγή των ιχνών. Ο ArrayTracer υπερτερεί στην περίπτωση αυτή για λόγους που αναφέρθηκαν ήδη.
Το PGPVM [35] είναι ένα σύστημα που αναπτύχθηκε για την παράλληλη βιβλιοθήκη επικοινωνίας PVM με σκοπό την παραγωγή ιχνών σε μορφή PICL τα οποία στη συνέχεια απεικονίζονται από το Paragraph. Η αντιμετώπιση του PGPVM για την παραγωγή χρονοσφραγίδων είναι παρόμοια. Ετσι όλα τα ίχνη παράγονται από ένα εξυπηρετητή για τον οποίο ανταγωνίζονται όλες οι διεργασίες της εφαρμογής. Με τον τρόπο αυτό έχουμε καθολικό χρόνο, αλλά ασφαλώς επιπλέον καθυστέρηση λόγω της συσσώρευσης όλων των ιχνών σε ένα κεντρικό εξυπηρετητή.
Και στην περίπτωση του PVM 3.3 σε κάθε γεγονός αντιστοιχούν δύο ίχνη ένα για την αρχή και ένα για το πέρας αυτού. Αυτό σημαίνει ότι και σε αυτή την περίπτωση είναι αυξημένο το μέγεθος της πληροφορίας που παράγεται και επιπλέον δεν δίνεται η δυνατότητα στο χρήστη να επιλέξει μεταξύ των γεγονότων μιας συγκεκριμένης κατηγορίας (πχ. γεγονότα αποστολής μηνυμάτων). Αυτή τη δυνατότητα την δίνει ο ArrayTracer περιορίζοντας τον όγκο πληροφορίας. Στο PVM 3.4 έγινε μια προσπάθεια για καθορισμό από το χρήστη της μορφής των ιχνών. Ακόμη δίνεται δυνατότητα για συμπίεση και αποθήκευση των ιχνών με σκοπό την μείωση της καθυστέρησης που οφείλεται στην αποθήκευση και ανάλυση των ιχνών. Αυτές είναι δύο πολύ αξιόλογες δυνατότητες. Παρόλα αυτά δεν παρέχεται λύση στο πρόβλημα της επιλογής των γεγονότων που ιχνοληπτούνται.
Το Pablo που περιγράψαμε πιο πάνω είναι ένα από τα πιο πλήρη εργαλεία. Δίνει τη δυνατότητα στο χρήστη να καθορίσει τα γεγονότα καθώς και το είδος των ιχνών που θα περιγράφουν αυτά τα γεγονότα. Αυτό σημαίνει ότι ο χρήστης θα ρυθμίζει και το μέγεθος της πληροφορίας που παράγεται. Δηλαδή υπάρχει η δυνατότητα απεικόνισης των γεγονότων είτε όπως στο PICL είτε όπως στον ArrayTracer ανάλογα με τις συνθήκες (χώρος στο δίσκο, καθυστέρηση της εφαρμογής). Και στην περίπτωση αυτού του εργαλείου οι χρονοσφραγίδες παράγονται με τη χρήση ένος καθολικού ρολογιού. Επιπλέον τα ίχνη μπορεί να είναι είτε σε ASCII μορφή είτε σε binary.
Ορισμός : Μια ακολουθία γεγονότων χαρακτηρίζεται συνεπής προς την ακολουθία των γεγονότων που συνέβησαν κατά την εκτέλεση της εφαρμογής, όταν το σύνολο των γεγονότων αυτών είναι ίσο με το σύνολο των γεγονότων της εφαρμογής και η διάταξή τους ικανοποιεί όλες τις εξαρτήσεις, που ικανοποιούνται και από την ακολουθία γεγονότων της εφαρμογής.
Υπάρχουν οι εξής κατηγορίες εξαρτήσεων :
Αρχικός στόχος είναι η κατασκευή συνεπών διατάξεων των γεγονότων που προκύπτουν από την εκτέλεση της εφαρμογής. Η σχέση Lamport [19, 20] προσδιορίζει τη διάταξη των γεγονότων της εφαρμογής και καθορίζει μια συνεπή ακολουθία γεγονότων.
Figure: Σχέση Διάταξης Lamport
Η σχέση αυτή ονομάζεται Happened Before συμβολίζεται με
και ορίζεται ως εξής:
Εστω LC(e) η λογική χρονοσφραγίδα που αντιστοιχεί στο γεγονός e. Οι λογικές χρονοσφραγίδες παράγονται ως εξής,
,
,
όπου ,
είναι μεταβλητές που
καθορίζονται από τον χρήστη, της τάξης των nsec και δεν
επηρεάζουν ουσιαστικά την τιμή του λογικού ρολογιού καθώς οι
υπόλοιποι χρόνοι που μετρόνται είναι της τάξης του μsec.
Οι μεταβλητές αυτές χρησιμοποιούνται μόνο για τον καθορισμό
της σειράς των γεγονότων που διαρκούν μικρό χρόνο. Οι τιμές
αυτές μπορεί να τεθούν ίσες με 0 και να μην υπάρχει πρόβλημα
στην ακολουθία γεγονότων που παράγεται. Απλώς δίνουν τη
δυνατότητα στο χρήστη να καθορίσει μια μέση διάρκεια
προσπέλασης στην ιεραρχία μνήμης και μια μέση διάρκεια
εκτέλεσης μιας μεταβολής στη ροή του προγράμματος.
Το είναι η χρονοσφραγίδα του γεγονότος που προήλθε
από το προηγούμενο
ίχνος που διαβαστηκε από το ίδιο αρχείο ιχνών.
.
Είναι εμφανές ότι αφού η εξάρτηση μεταξύ των γεγονότων είναι αυτή της σειριακότητας, η τιμή της χρονοσφραγίδας εξαρτάται από την τιμή που είχε τη στιγμή που διετελέσθει το αμέσως προηγούμενο γεγονός, της ίδιας διεργασίας.
όπου TIME είναι η χρονική διάρκεια αναμονής της διεργασίας
που παρέλαβε το μήνυμα και
είναι η χρονοσφραγίδα
του γεγονότος που προήλθε
από το προηγούμενο
ίχνος που διαβάστηκε από το αρχείο ιχνών από το οποίο
προέρχεται και το ίχνος
.
if
,
if
.
Στην περίπτωση αυτή είναι εμφανής η εξάρτηση της τιμής της λογικής χρονοσφραγίδας από την ενδοδιεργασιακή επικοινωνία.
,
όπου
είναι το χρονικό
διάστημα αναμονής της
κάθε διεργασίας στο σημείο συγχρονισμού. Με τον τρόπο αυτό
εξασφαλίζουμε ότι η έξοδος από το σημείο συγχρονισμού θα γίνει
την ίδια λογική χρονική στιγμή και για τις δύο διεργασίες.
Τα βασικά πλεονεκτήματα της μεθόδου είναι :
Μειωνεκτήματα της μεθόδου είναι :