next up previous
Next: Μηχανισμός ανίχνευσης ελλειπούς πληροφορίας Up: Τμήμα Ανάλυσης των Ιχνών Previous: Φόρμες Ιχνοληψίας

Λογικές Χρονοσφραγίδες

Εισαγωγή: Βασικοί στόχοι του ArrayTracer.

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

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

Ενα παράδειγμα φαίνεται στο σχήμα gif.

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

Στην περίπτωση (b) βλέπουμε τον κώδικα καθοδήγησης που εισάγεται από το δικό μας εργαλείο. Παράγεται ένα μόνο ίχνος που περιγράφει την απόλυτη χρονική διάρκεια του γεγονότος.

   figure483
Figure: Παράδειγμα μείωσης του κώδικα καθοδήγησης με χρήση του ArrayTracer

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

Ολα τα παραπάνω προυποθέτουν ότι κατα τη διαδικασία της ανάλυσης θα πρέπει, με χρήση του περιορισμένου αριθμού των ιχνών να καθοριστούν τα εξής.

  1. Η πλήρης ακολουθία γεγονότων που συμβαίνουν κατά την διάρκεια εκτέλεσης της κάθε διεργασίας της εφαρμογής.
  2. Η καθολική ακολουθία γεγονότων που προκύπτει με τον συγκερασμό των πιο πάνω ακολουθιών. Η δυσκολία στην περίπτωση αυτή έγκειται στον προσδιορισμό της σχετικής σειράς εκτέλεσης των γεγονότων.

Για την υλοποίηση του πρώτου στόχου, κατά την ανάλυση των ιχνών δημιουργείται μια ακολουθία καταστάσεων, για κάθε διεργασία, που καταλήγει στην παραγωγή γεγονότων μορφής PICL.

Για την υλοποίηση του δεύτερου στόχου κατασκευάζονται λογικές χρονοσφραγίδες με χρήση της σχέσης διάταξης Lamport [17].

Πριν την περιγραφή της τεχνικής αυτής θα μελετήσουμε τον τρόπο που αντιμετωπίζεται το πρόβλημα της σειριοποίησης, καθώς και τη μορφή των ιχνών σε άλλα εργαλεία παρόμοια με τον ArrayTracer

ArrayTracer vs PICL

Καθε γεγονός της παράλληλης βιβλιοθήκης PICL [13] αντιστοιχεί σε δύο ίχνη που αποθηκεύονται σε κάποιο αρχείο εξόδου. Το πρώτο ίχνος περιγράφει την αρχή του αντίστοιχου γεγονότος και το δεύτερο το πέρας αυτού. Επιπλέον το PICL παράγει ίχνη που αντιστοιχούν σε κλήσεις υπολογιστικών συναρτήσεων και δίνει και τη δυνατότητα στο χρήστη να καθορίζει την ιχνοληψία γεγονότων της επιλογής του.

Τέλος τα ίχνη είναι σε ASCII μορφή κάτι που επαυξάνει το μέγεθος των αρχείων που παράγονται.

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

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

Για να μελετήσουμε τη συμπεριφορά των δύο εργαλείων εκτελέσαμε τα τρία παρακάτω πειράματα :

1ο Πείραμα:

Χρησιμοποιήσαμε δύο σειριακές εφαρμογές, ένα αλγόριθμο λείανσης και ένα πυρήνα που εκτελεί πολλαπλασιαμό πινάκων. Για τις δύο αυτές εφαρμογές προγραμματίσαμε το PICL να εξάγει ένα ίχνος για κάθε προσπέλαση μεταβλητής. Η μορφή του ίχνους είναι καθορισμένη από το PICL για γεγονότα που καθορίζονται από το χρήστη. Το ίχνος περιέχει χρονοσφραγίδα που καθορίζει τη χρονική στιγμή που συνέβει η προσπέλαση. Το αντίστοιχο ίχνος που παράγει ο ArrayTracer δεν περιέχει χρονοσφραγίδα. Τα αποτελέσματα της σύγκρισης φαίνονται στο σχ. gif.

Συνεπώς παρατηρούμε ότι η καθυστέρηση που εισάγεται από τον ArrayTracer είναι πολύ μικρή σε σχέση με αυτή του PICL. Η αναλογία του μεγέθους του παραγόμενου αρχείου είναι 1/3.79 για τον ArrayTracer. Επιπλέον από τον ArrayTracer αποφεύγεται η κλήση του λειτουργικού συστήματος για τον προσδιορισμό της χρονικής στιγμής που συνέβει το κάθε γεγονός.

Βέβαια η δυνατότητα αυτή που προσφέρεται από το PICL είναι επιπρόσθετη καθώς ο βασικός του στόχος είναι η ιχνοληψία δεδομένων που σχετίζονται με την επικοινωνία. Για το λόγο αυτό ακολουθούν τα δύο επόμενα πειράματα.

     figure515
Figure: ArrayTracer vs. PICL: Πρώτο πείραμα

2ο Πείραμα:

Στο πείραμα αυτό χρησιμοποιήσαμε ένα παραλληλοποιημένο αλγόριθμο λείανσης. Πρόκειται για ένα μοντέλλο αφέντη σκλάβου, όπου η διεργασία αφέντης κατάνεμει το πρόβλημα στις διεργασίες σκλάβους. Αυτές εκτελούν τον αλγόριθμο και επιστρέφουν τα αποτελέσματα στον αφέντη. Εκτελέσαμε την εφαρμογή σε 2, 4, 8 DEC ALPHA 3300 για 2 διαφορετικά προβλήματα μεγέθους 1000Χ1000, 2000Χ2000.

       figure528
Figure: ArrayTracer vs. PICL: Δεύτερο πείραμα

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

Από τα σχ.  tex2html_wrap2241 .gif, tex2html_wrap2242 .gif παρατηρούμε ότι οι χρόνοι εκτέλεσης των εφαρμογων σε PVM, PICL και PICL που παράγει ίχνη είναι περίπου ο ίδιος κάτι που δικαιολογείται αφού η επικοινωνία είναι περιορισμένη, συνεπώς δεν ιχνοληπτείται μεγάλος αριθμός γεγονότων. Στην περίπτωση όμως του ArrayTracer ο χρόνος εκτέλεσης παρουσιάζει σημαντική αύξηση κάτι που δεν έπρεπε να ισχύει. Αυτό οφείλεται στο γεγονός της δημιουργίας της διεργασίας συλλέκτη η οποία εκτελεί busy waiting. Μάλιστα μπορούμε να παρατηρήσουμε ότι μειώνοντας τον αριθμό των επεξεργαστών του συστήματος, αυξάνει η καθυστέρηση που εισάγεται από τον ArrayTracer, σχ.  tex2html_wrap2243 .gif, tex2html_wrap2244 .gif. Αυτό ισχύει διότι αυξάνει ο υπολογιστικός χρόνος των διεργασιών και συνεπώς η διεργασία συλλέκτης τις καθυστερεί περισσότερο.

3ο Πείραμα

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

Εκτελέσαμε τη εφαρμογή σε PICL και ArrayTracer se 2, 4, 8 DEC ALPHA 3300. Τα μεγέθη των προβλημάτων ήταν 150Χ150, 200Χ200, 250Χ250.

Τα αποτελέσματα που προκύπτουν φαίνονται στο σχ.gif. Παρατηρούμε ότι ο ArrayTracer εισάγει μικρότερη καθυστέρηση από το PICL σε όλες τις περιπτώσεις. Επίσης η διαφορά τους αυξάνει όσο αυξάνεται ο αριθμός των επεξεργαστών στους οποίους εκτελείται η εφαρμογή. Το γεγονός αυτό είναι μια ένδειξη για το λόγο που υπερτερεί ο ArrayTracer. Ο πιθανός λόγος είναι ότι τα ίχνη που παράγονται από το PICL σειριοποιούνται και γράφονται σε ένα αρχείο στο δίσκο του επεξεργαστή που δημιουργεί όλες τις υπόλοιπες διεργασίες. Για να γίνει αυτό ανταλάσσονται κάποια μηνύματα με συνέπεια την αύξηση της καθυστέρησης. Αντίθετα στην περίπτωση του ArrayTracer τα ίχνη δεν περνάνε από διαδικασία σειριοποίησης, αλλά γράφονται στους τοπικούς δίσκους των επεξεργαστών. Η ανταλλαγές μηνυμάτων που γίνονται με τον συλλέκτη είναι στον ίδιο επεξεργαστή και δεν κοστίζουν αφού το μήνυμα δεν "διανύει το σύρμα".

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

      figure567
Figure: ArrayTracer vs. PICL: Τρίτο πείραμα

Συμπέρασμα :

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

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

Στο τρίτο πείραμα το μέγεθος του προβλήματος είναι μικρό με συνέπεια να φαίνεται το κόστος της επικοινωνίας για την παραγωγή των ιχνών. Ο ArrayTracer υπερτερεί στην περίπτωση αυτή για λόγους που αναφέρθηκαν ήδη.

ArrayTracer vs PGPVM

Το PGPVM [35] είναι ένα σύστημα που αναπτύχθηκε για την παράλληλη βιβλιοθήκη επικοινωνίας PVM με σκοπό την παραγωγή ιχνών σε μορφή PICL τα οποία στη συνέχεια απεικονίζονται από το Paragraph. Η αντιμετώπιση του PGPVM για την παραγωγή χρονοσφραγίδων είναι παρόμοια. Ετσι όλα τα ίχνη παράγονται από ένα εξυπηρετητή για τον οποίο ανταγωνίζονται όλες οι διεργασίες της εφαρμογής. Με τον τρόπο αυτό έχουμε καθολικό χρόνο, αλλά ασφαλώς επιπλέον καθυστέρηση λόγω της συσσώρευσης όλων των ιχνών σε ένα κεντρικό εξυπηρετητή.

ArrayTracer vs PVM 3.3

Και στην περίπτωση του PVM 3.3 σε κάθε γεγονός αντιστοιχούν δύο ίχνη ένα για την αρχή και ένα για το πέρας αυτού. Αυτό σημαίνει ότι και σε αυτή την περίπτωση είναι αυξημένο το μέγεθος της πληροφορίας που παράγεται και επιπλέον δεν δίνεται η δυνατότητα στο χρήστη να επιλέξει μεταξύ των γεγονότων μιας συγκεκριμένης κατηγορίας (πχ. γεγονότα αποστολής μηνυμάτων). Αυτή τη δυνατότητα την δίνει ο ArrayTracer περιορίζοντας τον όγκο πληροφορίας. Στο PVM 3.4 έγινε μια προσπάθεια για καθορισμό από το χρήστη της μορφής των ιχνών. Ακόμη δίνεται δυνατότητα για συμπίεση και αποθήκευση των ιχνών με σκοπό την μείωση της καθυστέρησης που οφείλεται στην αποθήκευση και ανάλυση των ιχνών. Αυτές είναι δύο πολύ αξιόλογες δυνατότητες. Παρόλα αυτά δεν παρέχεται λύση στο πρόβλημα της επιλογής των γεγονότων που ιχνοληπτούνται.

ArrayTracer vs Pablo

Το Pablo που περιγράψαμε πιο πάνω είναι ένα από τα πιο πλήρη εργαλεία. Δίνει τη δυνατότητα στο χρήστη να καθορίσει τα γεγονότα καθώς και το είδος των ιχνών που θα περιγράφουν αυτά τα γεγονότα. Αυτό σημαίνει ότι ο χρήστης θα ρυθμίζει και το μέγεθος της πληροφορίας που παράγεται. Δηλαδή υπάρχει η δυνατότητα απεικόνισης των γεγονότων είτε όπως στο PICL είτε όπως στον ArrayTracer ανάλογα με τις συνθήκες (χώρος στο δίσκο, καθυστέρηση της εφαρμογής). Και στην περίπτωση αυτού του εργαλείου οι χρονοσφραγίδες παράγονται με τη χρήση ένος καθολικού ρολογιού. Επιπλέον τα ίχνη μπορεί να είναι είτε σε ASCII μορφή είτε σε binary.

Σχέση Διάταξης Lamport

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

Υπάρχουν οι εξής κατηγορίες εξαρτήσεων :

  1. Εξαρτήσεις που οφείλονται στη σειριακότητα της κάθε διεργασίας που εκτελείται.
  2. Εξαρτήσεις που οφείλονται στην ενδοδιεργασιακή επικοινωνία.

Αρχικός στόχος είναι η κατασκευή συνεπών διατάξεων των γεγονότων που προκύπτουν από την εκτέλεση της εφαρμογής. Η σχέση Lamport [19, 20] προσδιορίζει τη διάταξη των γεγονότων της εφαρμογής και καθορίζει μια συνεπή ακολουθία γεγονότων.

      figure615
Figure: Σχέση Διάταξης Lamport

Η σχέση αυτή ονομάζεται Happened Before συμβολίζεται με tex2html_wrap_inline2251 και ορίζεται ως εξής:

Χρήση σχέσεων αναδιάταξης για την δημιουργία λογικών χρονοσφραγίδων

Εστω LC(e) η λογική χρονοσφραγίδα που αντιστοιχεί στο γεγονός e. Οι λογικές χρονοσφραγίδες παράγονται ως εξής,

Πλεονεκτήματα - Μειονεκτήματα :

Τα βασικά πλεονεκτήματα της μεθόδου είναι :

Μειωνεκτήματα της μεθόδου είναι :


next up previous
Next: Μηχανισμός ανίχνευσης ελλειπούς πληροφορίας Up: Τμήμα Ανάλυσης των Ιχνών Previous: Φόρμες Ιχνοληψίας

zaras@ics.forth.gr