next up previous
Next: Χρήση του ArrayTracer για Up: Παραδείγματα Χρήσης του ArrayTracer Previous: Παραδείγματα Χρήσης του ArrayTracer

Χρήση του ArrayTracer για Μελέτη της Επίδοσης μιας Παράλληλης Εφαρμογής

Εισαγωγή

Οι μεθοδολογίες και τεχνικές για τον χαρακτηρισμό του φορτίου (Workload Characterization) ενός παράλληλου συστήματος σχετίζονται άμεσα με την απόδοση του [9]. Τα παράλληλα συστήματα αποτελούνται από ένα μεγάλο αριθμό επεξεργαστών που συνεργάζονται/επικοινωνούν μεταξύ τους. Η απόδοση τους εξαρτάται από τη δομή των εφαρμογών και την ικανότητά τους να οικειοποιηθούν τις δυνατότητες τους.

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

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

Περιγραφή της Εφαρμογής

Η εφαρμογή που μελετήθηκε είναι το σύστημα //ELLPACK [37]. Χρησιμοποιείται για την επίλυση μερικών διαφορικών εξισώσεων. Παρέχει τη δυνατότητα στο χρήστη, μέσω ενός συστήματος διεπαφής να κατασκευάσει τους αλγόριθμους επίλυσης των διαφορικών εξισώσεων με χρήση και συνδυασμούς των υπάρχοντων αλγορίθμων. Εκτός από το σύστημα διεπαφής το //ELLPACK περιλαμβάνει την παράλληλη βιβλιοθήκη των μεθόδων επίλυσης μερικών διαφορικών εξισώσεων (ITPACK) και ένα εργαλείο τμηματοποίησης των δεδομένων εισόδου.

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

Το υπάρχον σύστημα //ELLPACK αποτελείται από 1.234.000 γραμμές κώδικα σε C και Fortran. Το μέγεθος της παράλληλης βιβλιοθήκης είναι 128.000 γραμμές κώδικα και έχει υλοποιηθεί με την υποστήριξη των πολλών βιβλιοθηκών επικοινωνίας όπως, PICL, PARMACS, MPI, PVM [13, 12, 1]. Στα πειράματα που έγιναν χρησιμοποιήθηκε η υλοποίηση σε PVM.

Τα αποτελέσματα που θα ακολουθήσουν προέκυψαν από τη χρήση της παράλληλης υλοποίησης της βιβλιοθήκης ITPACK με PVM, για την επίλυση ενός μεγάλου μεγέθους προβλήματος (636 στοιχεία). Χρησιμοποιήθηκε ο Jacobi CG αλγόριθμος. Το πρόβλημα χωρίζεται σε Ν υποπροβλήματα, όπου Ν ο αριθμός των επεξεργαστών του παράλληλου συστήματος.

Τα συστήματα των παράλληλων επεξεργαστών που χρησιμοποιήθηκαν ήταν ομοιογενή gif. Οι πλατφόρμες επεξεργασίας ήταν DEC ALPHA 3300. Η απόδοση της εφαρμογής μελετήθηκε σε συστήματα 2, 4, 8, 16 επεξεργαστών.

Συντελεστές Απόδοσης

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

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

Μελέτη Αποτελεσμάτων

Μελέτη του παραλληλοποιημένου αλγορίθμου σε επίπεδο Επικοινωνίας

Για την περιγραφή τις μεθόδου παραλληλοποίησης του αλγορίθμου που μελετήθηκε (Jacobi CG), χρησιμοποιήθηκαν το διάγραμμα γενεαλογικού δέντρου (Generation Map), το διάγραμμα ομαδοποίησης (Group Diagram) και το διάγραμμα ζωογόνησης του αλγορίθμου (Animation Diagram) gif.

Το τελευταίο (Animation Diagram) απεικονίζει τους επεξεργαστές σαν κόμβους. Το χρώμα με το οποίο γεμίζει το εσωτερικό του κόμβου αντιστοιχεί στην δραστηριότητα που εκτελείται από τον επεξεργαστή. Η αντιστοιχία είναι η εξής :

   figure1318
Figure: Γενεαλογικός Χάρτης των Διεργασιών: Η διεργασία 0 δημιουργεί τις 1, 2, 3, 4, 5, 6, 7

Αρχικά όπως φαίνεται στο σχ. gif, η διεργασία γονέας, που εκτελείται στον επεξεργαστή 0, δημιουργεί μια ακολουθία διεργασιών στις οποίες ανατίθεται η επίλυση ενός υποπροβλήματος του αρχικού προβλήματος. Αρα πρόκειται για παραλληλισμό αφέντη-εργάτη (master-slave). Στη συνέχεια, στο σχ.  tex2html_wrap2547 .gif η διεργασία αφέντης κατανέμει το πρόβλημα στους επιμέρους εργάτες στέλνοντας ένα αρχικό μήνυμα σε όλους. Ακολουθεί συγχρονισμός των διεργασιών όπως φαίνεται στο σχ.  tex2html_wrap2548 .gif. Αυτό γίνεται για την όσο το δυνατόν καλύτερη χρησιμοποίησης του παράλληλου συστήματος.

       figure1329
Figure: Επικοινωνία μεταξύ των Επεξεργαστών : Τα 4 βασικά βήματα

Κατά τη διάρκεια εκτέλεσης του αλγορίθμου, η κάθε διεργασία ανταλλάσσει μηνύματα μόνο με μερικές από το σύνολο των διεργασιών, αυτές αποτελούν τις γειτονικές της διεργασίες, σχ.  tex2html_wrap2549 .gif, 7.  tex2html_wrap2550 .gif. Κατά τον τερματισμό δεν επιστρέφονται αποτελέσματα στην διεργασία αφέντης.

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

Κατανομή Προσπελάσεων Μεταβλητών

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

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

       figure1349
Figure: Κατανομή Προσπελάσεων των Μεταβλητών της εφαρμογής για ένα Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές

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

Συνεπώς παρατηρούμε ότι στην περίπτωση του συστήματος 2 επεξεργαστών σχ.  tex2html_wrap2559 .gif η κατανομή των προσπελάσεων στη ιεραρχία μνήμης είναι πλήρως ομοιόμορφη για όλους τους επεξεργαστές του συστήματος. Καθώς όμως αυξάνουν οι κόμβοι του συστήματος σε 4 σχ.  tex2html_wrap2560 .gif, 8 σχ.  tex2html_wrap2561 .gif και 16, σχ.  tex2html_wrap2562 .gif, σταδιακά χαλάει η πλήρης ομοιομορφία.

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

Μελέτη με βάση τον Χρόνο Εκτέλεσης της Εφαρμογής

Το διάγραμμα Raw Time αναπαριστά 3 ιστογράμματα. Σε καθένα από αυτά, στον οριζόντιο άξονα απεικονίζονται οι διεργασίες της εφαρμογής και στον κάθετο άξονα οι λωρίδες απεικονίζεται ο χρόνος που δαπανήθηκε για υπολογισμούς (Computation Time), με τη σκούρα απόχρωση, ο χρόνος που δαπανήθηκε για επικοινωνία (Communication Time), με τη μεσαία απόχρωση, ο χρόνος που δαπανήθηκε για συγχρονισμό των διεργασιών, με την ανοιχτόχρωμη απόχρωση.

Το διάγραμμα Utilization Summary αναπαριστά για την κάθε διεργασία το επί τοις εκατό ποσοστό του χρόνου που εκτελούσε υπολογισμούς (με τη μεσαία απόχρωση), που περίμενε να επικοινωνήσει με κάποια άλλη (με τη σκούρα απόχρωση) και του χρόνου που δαπανήθηκε για συγχρονισμό, επί του συνολικού χρόνου εκτέλεσής της.

Το διάγραμμα Utilization Count περιγράφει τον αριθμό των επεξεργαστών που βρίσκονται σε κάθε μια από τις καταστάσεις, εκτέλεσης υπολογισμών (Busy), επικοινωνίας (Idle), συγχρονισμού (Overhead) σε συνάρτηση με το χρόνο.

Το διάγραμμα Utilization Profile περιγράφει τα επί τοις εκατό ποσοστά του χρόνου εκτέλεσης, κατά τα οποία ένας αριθμός επεξεργαστών του συστήματος εκτελούσε ταυτόχρονα χρήσιμη εργασία (βρίσκόταν ταυτόχρονα σε κατάσταση Busy).

       figure1381
Figure: Χρόνος Εκτέλεσης Διεργασιών (Communication, Computation, Synchronization time) σε ένα Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές

gif

Μελετώντας τα διαγράμματα του χρόνου εκτέλεσης, σχ. 

παρατηρούμε τα εξής.

Στο σύστημα με 2 επεξεργαστές σχ.  tex2html_wrap2579 .gif παρατηρούμε ότι ο χρόνος που δαπανάται για την ενδοεπικοινωνία είναι πολύ μικρός σε σχέση με το χρόνο για υπολογισμούς, επιπλέον ο χρόνος συγχρονισμού είναι απειροελάχιστος. Στο σύστημα με 4 επεξεργαστές σχ.  tex2html_wrap2580 .gif ο χρόνος που δαπανάται για την επικοινωνία αυξάνει σε αναλογία με το χρόνο για υπολογισμούς ο οποίος ελαττώνεται για την κάθε διεργασία (προφανώς αυτό ισχύει διότι το πρόβλημα χωρίζεται σε περισσότερα κομμάτια). Παρόλη την αύξηση του χρόνου επικοινωνίας η αναλογία Computation/Communication time παραμένει καλή. Στο σύστημα με 8 επεξεργαστές ο χρόνος επικοινωνίας αυξάνει αρκετά, σχ.  tex2html_wrap2581 .gif, στο σύστημα με 16 επεξεργαστές βλέπουμε να γίνεται αρκετά μεγαλύτερος του χρόνου που δαπανάται για υπολογισμούς με αποτέλεσμα να κυριαρχεί στο χρόνο εκτέλεσης της κάθε διεργασίας όπως φαίνεται στο σχ.  tex2html_wrap2582 .gif.

Αυτό σημαίνει ότι μεταξύ των συστημάτων με 4 και 8 επεξεργαστές πρέπει να αναζητήσουμε αυτό που παρουσιάζει την καλύτερη επιτάχυνση σε σχέση με τον αριθμό επεξεργαστών που χρησιμοποιούνται.

       figure1403
Figure: Utilization Summary: Επιμέρους χρησιμοποίηση των Επεξεργαστών σε ένα Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές

gif

Μελετώντας τα διαγράμματα της επιμέρους χρησιμοποίησης των επεξεργαστών, σχ. ,

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

       figure1421
Figure: Utilization Count: Ταυτόχρονη χρησιμοποίηση των Επεξεργαστών σε ένα Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές

gif

Μελετώντας τα διαγράμματα της ταυτόχρονης χρησιμοποίησης των επεξεργαστών, σχ. ,

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

Το ίδιο ισχύει και στις άλλες περιπτώσεις που μελετήθηκαν

       figure1437
Figure: Utilization Profile: Διαγράμματα ποσοστού ταυτόχρονης χρησιμοποίησης σε ένα Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές

gif

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

παρατηρούμε ότι στο σύστημα των 2 επεξεργαστών, σχ. gif, για το 80% του χρόνου και οι δύο επεξεργαστές εργάζονται ταυτόχρονα.

Η επιτάχυνση αναμένεται πολύ κοντά στη μέγιστη επιτάχυνση για το σύστημα με δύο επεξεργαστές.

Στην περίπτωση του συστήματος των 4 επεξεργαστών, σχ. gif, παρατηρούμε ότι για το μεγαλύτερο ποσοστό του χρόνου εκτέλεσης και οι 4 επεξεργαστές εργαζόταν ταυτόχρονα. Βέβαια το ποσοστό αυτό ελαττώνεται σε 40%. Συνεπώς αναμένουμε μικρή αύξηση της επιτάχυνσης της εφαρμογής

Στην περίπτωση του συστήματος των 8, σχ. gif, επεξεργαστών μειώνεται δραματικά το ποσοστό του χρόνου που όλοι οι επεξεργαστές του συστήματος εργάζονται ταυτόχρονα. Μάλιστα στο μεγαλύτερο ποσοστό του χρόνου, 20%, μόνο 3 εργάζονται ταυτόχρονα. Η επιτάχυνση της εφαρμογής πάλι θα παρουσιάσει ελάχιστη αύξηση

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

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

Συμπεράσματα.

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

Κριτική του Εργαλείου μελέτης

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

Η καθυστέρηση του κώδικα κυμάνθηκε από 2 (σύστημα 2 επεξεργαστών) έως 6.17 ( σύστημα 16 επεξεργαστών). Σχετικά χαμηλές τιμές με δεδομένο ότι η παραγόμενη πληροφορία ήταν αρκετή για τη μελέτη της επαρκή εφαρμογής.

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


next up previous
Next: Χρήση του ArrayTracer για Up: Παραδείγματα Χρήσης του ArrayTracer Previous: Παραδείγματα Χρήσης του ArrayTracer

zaras@ics.forth.gr