Οι μεθοδολογίες και τεχνικές για τον χαρακτηρισμό του φορτίου (Workload Characterization) ενός παράλληλου συστήματος σχετίζονται άμεσα με την απόδοση του [9]. Τα παράλληλα συστήματα αποτελούνται από ένα μεγάλο αριθμό επεξεργαστών που συνεργάζονται/επικοινωνούν μεταξύ τους. Η απόδοση τους εξαρτάται από τη δομή των εφαρμογών και την ικανότητά τους να οικειοποιηθούν τις δυνατότητες τους.
Για το χαρακτηρισμό του φορτίου ενός παράλληλου συστήματος θα πρέπει να ακολουθηθούν ορισμένα βασικά βήματα που αποτελούν μια μεθοδολογία μελέτης των διαφόρων εφαρμογών.
Η εφαρμογή που μελετήθηκε είναι το σύστημα //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 αλγόριθμος. Το πρόβλημα χωρίζεται σε Ν υποπροβλήματα, όπου Ν ο αριθμός των επεξεργαστών του παράλληλου συστήματος.
Τα συστήματα των παράλληλων επεξεργαστών που χρησιμοποιήθηκαν
ήταν ομοιογενή . Οι πλατφόρμες
επεξεργασίας ήταν DEC ALPHA 3300. Η απόδοση της εφαρμογής μελετήθηκε
σε συστήματα 2, 4, 8, 16 επεξεργαστών.
Οι συντελεστές απόδοσης, που χρησιμοποιήθηκαν και θα απεικονιστούν στη συνέχεια, για την μελέτη της εφαρμογής είναι οι εξής :
Με βάση τους παραπάνω χρόνους εκτιμάται η επιτάχυνση της εφαρμογής, η κατανομή του χρόνου εκτέλεσης σε υπολογισμούς και επικοινωνία, η χρησιμοποίηση των επεξεργαστών του συστήματος. Με την μελέτη των αποτελεσμάτων που προκύπτουν και με δεδομένους τους πόρους που διαθέτει, ο χρήστης μπορεί να επιλέξει το σύστημα που τον εξυπηρετεί καλύτερα τόσο από πλευράς επιτάχυνσης όσο και από πλευράς οικονομίας σε υπολογιστική ισχύ.
Η συλλογή των δεδομένων έγινε με την χρήση του ArrayTracer [10]. Επίσης η ανάλυση που ακολούθησε έγινε με χρήση του ιδίου εργαλείου. Ο κώδικας καθοδήγησης που εισήχθει παράγει ίχνη που αντιστοιχούν σε γεγονότα που αφορούν, τις προσπελάσεις στις μεταβλητές της εφαρμογής, την επικοινωνία μεταξύ των διεργασιών, την ομαδοποίηση των διεργασιών, τον τρόπο επεξεργασίας των δεδομένων από την κάθε διεργασία (κλήσεις υπορουτινών και συναρτήσεων) και τέλος τις αλλαγές στη ροή του προγράμματος.
Για την περιγραφή τις μεθόδου παραλληλοποίησης του αλγορίθμου
που μελετήθηκε (Jacobi CG), χρησιμοποιήθηκαν το διάγραμμα
γενεαλογικού δέντρου (Generation Map), το διάγραμμα
ομαδοποίησης (Group Diagram) και το διάγραμμα
ζωογόνησης του αλγορίθμου (Animation Diagram) .
Το τελευταίο (Animation Diagram) απεικονίζει τους επεξεργαστές σαν κόμβους. Το χρώμα με το οποίο γεμίζει το εσωτερικό του κόμβου αντιστοιχεί στην δραστηριότητα που εκτελείται από τον επεξεργαστή. Η αντιστοιχία είναι η εξής :
Figure: Γενεαλογικός Χάρτης των Διεργασιών: Η διεργασία 0 δημιουργεί
τις 1, 2, 3, 4, 5, 6, 7
Αρχικά όπως φαίνεται στο σχ. , η διεργασία γονέας,
που εκτελείται στον επεξεργαστή 0,
δημιουργεί μια ακολουθία διεργασιών στις οποίες ανατίθεται η επίλυση
ενός υποπροβλήματος του αρχικού προβλήματος. Αρα πρόκειται για
παραλληλισμό αφέντη-εργάτη (master-slave). Στη συνέχεια,
στο σχ.
.
η διεργασία
αφέντης κατανέμει το πρόβλημα στους επιμέρους εργάτες στέλνοντας ένα
αρχικό μήνυμα σε όλους. Ακολουθεί συγχρονισμός των διεργασιών όπως
φαίνεται στο σχ.
.
. Αυτό γίνεται για την όσο το δυνατόν
καλύτερη χρησιμοποίησης του παράλληλου συστήματος.
Figure: Επικοινωνία μεταξύ των Επεξεργαστών : Τα 4 βασικά βήματα
Κατά τη διάρκεια εκτέλεσης του αλγορίθμου, η κάθε διεργασία
ανταλλάσσει μηνύματα μόνο με μερικές από το σύνολο των διεργασιών,
αυτές αποτελούν τις γειτονικές της διεργασίες,
σχ. .
, 7.
.
.
Κατά τον τερματισμό δεν επιστρέφονται αποτελέσματα στην
διεργασία αφέντης.
Ο τρόπος παραλληλοποίησης είναι ο κατάλληλος για υπολογιστικές εφαρμογές και η απόδοσή του εξαρτάται από το μέγεθος του προβλήματος. Από αυτό εξαρτάται και ο κατάλληλος αριθμός εργατών που θα χρησιμοποιηθεί, αυτό θα το διαπιστώσουμε παρακάτω.
Τα διαγράμματα που ακολουθούν παρουσιάζουν τα αποτελέσματα που προέκυψαν από τη μελέτη της εφαρμογής που περιγράψαμε, σε επίπεδο προσπελάσεων μεταβλητών.
Οπως αναφέρθηκε στο κεφ.5 το Variables Streak διάγραμμα παρουσιάζει, αναλυτικά τον αριθμό των προσπελάσεων των μεταβλητών της εφαρμογής από τον κάθε επεξεργαστή. Στον οριζόντιο άξονα απεικονίζονται οι επεξεργαστές και στον κάθετο άξονα ο αριθμός προσπελάσεων. Σε κάθε επεξεργαστή αντιστοιχούν δύο λωρίδες. Οι προσπελάσεις ανάγνωσης απεικονίζονται στην πάνω λωρίδα, ενώ οι προσπελάσεις εγγραφής στην κάτω λωρίδα.
Figure: Κατανομή Προσπελάσεων των Μεταβλητών της εφαρμογής για ένα
Παράλληλο Σύστημα με 2, 4, 8, 16 Επεξεργαστές
Στο Variables Matrix διάγραμμα έχουμε μια διαφορετική απεικόνιση στον τρόπο προσπέλασης των μεταβλητών της εφαρμογής από τους επεξεργαστές του συστήματος. Κάθε στοιχείο του πίνακα αντιστοιχεί στον επεξεργαστή που αναγράφεται στο κέντρο του στοιχείου. Οι μεταβολές στους χρωματισμούς και στο είδος του χρωματισμού fill style αντιστοιχούν στον αριθμό προσπελάσεων που έγιναν. Αυτή η αναπαράσταση στηρίζεται στον κώδικα χρωμάτων που εμφανίζεται στην βάση του διαγράμματος. Οι αποχρώσεις αντιστοιχούν σε αριθμό των προσπελάσεων των μεταβλητών, κατά αύξουσα σειρά, από αριστερά προς τα δεξιά.
Συνεπώς παρατηρούμε ότι στην περίπτωση του συστήματος 2
επεξεργαστών σχ. .
η κατανομή των προσπελάσεων στη
ιεραρχία μνήμης
είναι πλήρως ομοιόμορφη για όλους τους επεξεργαστές του
συστήματος. Καθώς όμως αυξάνουν οι κόμβοι του συστήματος
σε 4 σχ.
.
, 8 σχ.
.
και 16,
σχ.
.
, σταδιακά χαλάει η πλήρης ομοιομορφία.
Αυτό το γεγονός οφείλεται στο γεγονός της τμηματοποίησης του προβλήματος που δεν γίνεται σε υποπροβλήματα του ιδίου μεγέθους αλλά υποπροβλήματα που διαφέρουν λίγο στο μέγεθος, ώστε να ικανοποιούνται ορισμένοι περιορισμοί απαραίτητοι για τη σωστή επίλυση.
Το διάγραμμα Raw Time αναπαριστά 3 ιστογράμματα. Σε καθένα από αυτά, στον οριζόντιο άξονα απεικονίζονται οι διεργασίες της εφαρμογής και στον κάθετο άξονα οι λωρίδες απεικονίζεται ο χρόνος που δαπανήθηκε για υπολογισμούς (Computation Time), με τη σκούρα απόχρωση, ο χρόνος που δαπανήθηκε για επικοινωνία (Communication Time), με τη μεσαία απόχρωση, ο χρόνος που δαπανήθηκε για συγχρονισμό των διεργασιών, με την ανοιχτόχρωμη απόχρωση.
Το διάγραμμα Utilization Summary αναπαριστά για την κάθε διεργασία το επί τοις εκατό ποσοστό του χρόνου που εκτελούσε υπολογισμούς (με τη μεσαία απόχρωση), που περίμενε να επικοινωνήσει με κάποια άλλη (με τη σκούρα απόχρωση) και του χρόνου που δαπανήθηκε για συγχρονισμό, επί του συνολικού χρόνου εκτέλεσής της.
Το διάγραμμα Utilization Count περιγράφει τον αριθμό των επεξεργαστών που βρίσκονται σε κάθε μια από τις καταστάσεις, εκτέλεσης υπολογισμών (Busy), επικοινωνίας (Idle), συγχρονισμού (Overhead) σε συνάρτηση με το χρόνο.
Το διάγραμμα Utilization Profile περιγράφει τα επί τοις εκατό ποσοστά του χρόνου εκτέλεσης, κατά τα οποία ένας αριθμός επεξεργαστών του συστήματος εκτελούσε ταυτόχρονα χρήσιμη εργασία (βρίσκόταν ταυτόχρονα σε κατάσταση Busy).
Figure: Χρόνος Εκτέλεσης Διεργασιών (Communication, Computation,
Synchronization time) σε ένα Παράλληλο Σύστημα με
2, 4, 8, 16 Επεξεργαστές
Στο σύστημα με 2 επεξεργαστές σχ. .
παρατηρούμε ότι
ο χρόνος που δαπανάται για την ενδοεπικοινωνία είναι πολύ μικρός σε
σχέση με το χρόνο για υπολογισμούς, επιπλέον ο χρόνος συγχρονισμού
είναι απειροελάχιστος.
Στο σύστημα με 4 επεξεργαστές σχ.
.
ο χρόνος που δαπανάται για την επικοινωνία αυξάνει σε αναλογία με το
χρόνο για υπολογισμούς ο οποίος ελαττώνεται για την κάθε διεργασία
(προφανώς αυτό ισχύει διότι το πρόβλημα χωρίζεται σε περισσότερα
κομμάτια).
Παρόλη την αύξηση του χρόνου επικοινωνίας η αναλογία
Computation/Communication time παραμένει καλή.
Στο σύστημα με 8 επεξεργαστές ο χρόνος επικοινωνίας αυξάνει αρκετά,
σχ.
.
,
στο σύστημα με 16 επεξεργαστές βλέπουμε
να γίνεται αρκετά μεγαλύτερος του χρόνου που δαπανάται για υπολογισμούς
με αποτέλεσμα να κυριαρχεί στο χρόνο εκτέλεσης της κάθε διεργασίας
όπως φαίνεται στο σχ.
.
.
Αυτό σημαίνει ότι μεταξύ των συστημάτων με 4 και 8 επεξεργαστές πρέπει να αναζητήσουμε αυτό που παρουσιάζει την καλύτερη επιτάχυνση σε σχέση με τον αριθμό επεξεργαστών που χρησιμοποιούνται.
Figure: Utilization Summary: Επιμέρους χρησιμοποίηση των Επεξεργαστών σε
ένα Παράλληλο Σύστημα με
2, 4, 8, 16 Επεξεργαστές
Figure: Utilization Count: Ταυτόχρονη χρησιμοποίηση των Επεξεργαστών σε
ένα Παράλληλο Σύστημα με
2, 4, 8, 16 Επεξεργαστές
Το ίδιο ισχύει και στις άλλες περιπτώσεις που μελετήθηκαν
Figure: Utilization Profile: Διαγράμματα ποσοστού ταυτόχρονης
χρησιμοποίησης σε ένα Παράλληλο Σύστημα με
2, 4, 8, 16 Επεξεργαστές
παρατηρούμε ότι στο σύστημα των 2 επεξεργαστών, σχ. , για
το 80% του χρόνου
και οι δύο επεξεργαστές εργάζονται ταυτόχρονα.
Η επιτάχυνση αναμένεται πολύ κοντά στη μέγιστη επιτάχυνση για το σύστημα με δύο επεξεργαστές.
Στην περίπτωση του συστήματος των 4 επεξεργαστών,
σχ. , παρατηρούμε ότι για το μεγαλύτερο ποσοστό του χρόνου
εκτέλεσης και οι 4 επεξεργαστές εργαζόταν ταυτόχρονα. Βέβαια το
ποσοστό αυτό ελαττώνεται σε 40%. Συνεπώς αναμένουμε μικρή αύξηση της
επιτάχυνσης της εφαρμογής
Στην περίπτωση του συστήματος των 8, σχ. ,
επεξεργαστών μειώνεται
δραματικά το ποσοστό του χρόνου που όλοι οι επεξεργαστές του
συστήματος εργάζονται ταυτόχρονα. Μάλιστα στο μεγαλύτερο ποσοστό του
χρόνου, 20%, μόνο 3 εργάζονται ταυτόχρονα.
Η επιτάχυνση της εφαρμογής πάλι θα παρουσιάσει ελάχιστη αύξηση
Τέλος στο σύστημα των 16 επεξεργαστών τα ποσοστά ταυτόχρονης χρησιμοποίησης μειώνονται δραματικά. Στην περίπτωση αυτή το πολύ 6 επεξεργαστές εργάζονται ταυτόχρονα για ένα μικρό ποσοστό του χρόνου εκτέλεσης.
Πρέπει να παράτηρήσουμε την αύξηση του ποσοστού του χρόνου που κανείς επεξεργαστής του συστήματος δεν εκτελεί χρήσιμη εργασία. Το ποσοστό αυτό οφείλεται στον χρόνο που δαπανάται για τον συγχρονισμό των επεξεργαστών, στην αρχή της εκτέλεσης της εφαρμογής. Το ποσοστό αυτό αυξάνει, όσο περισσότεροι είναι οι επεξεργαστές που πρέπει να συγχρονιστούν.
Αρα συμπεραίνουμε ότι στην προηγούμενη περίπτωση των 8 επεξεργαστών έχουμε φτάσει στη μέγιστη τιμή της επιτάχυνσης, παρόλα αυτά η κατανομή φορτίου δεν είναι η καλύτερη καθώς, οι επεξεργαστές δεν χρησιμοποιούνται παρά μόνο στο 40%. Συνεπώς μια μέση λύση, χρόνου εκτέλεσης κοντά στον ελάχιστο δυνατό και καλύτερης χρήσης της υπολογιστικής δύναμης παρέχεται από το σύστημα με 4 επεξεργαστές. Στο σημείο αυτό η επιλογή εξαρτάται από τα μέσα που μπορούμε να διαθέσουμε και το κατά πόσο επιθυμούμε οικονομία σε υπολογιστική δύναμη ή ταχύτητα εκτέλεσης.
Στην περίπτωση της μελέτης μιας πραγματικής εφαρμογής όπως το ITPACK o ArrayTracer ανταποκρίθηκε επιτυχώς, τόσο στην εισαγωγή κώδικα καθοδήγησης, σε ιδιαίτερα πολύπλοκα τμήματα κώδικα, όσο και στην συλλογή μεγάλης ποσότητας ιχνών. Επιπλέον η διαδικασία εισαγωγής κώδικα καθοδήγησης πραγματοποιήθηκε μόνο μια φορά και στη συνέχεια όλα τα πειράματα έγιναν με χρήση των "καθοδηγούμενων" από τον ArrayTracer βιβλιοθηκών του ITPACK. Αυτές ακριβώς οι βιβλιοθήκες μπορούν να χρησιμοποιηθούν και στη μελέτη άλλων προβλημάτων επίλυσης μερικών διαφορικών εξισώσεων.
Η καθυστέρηση του κώδικα κυμάνθηκε από 2 (σύστημα 2 επεξεργαστών) έως 6.17 ( σύστημα 16 επεξεργαστών). Σχετικά χαμηλές τιμές με δεδομένο ότι η παραγόμενη πληροφορία ήταν αρκετή για τη μελέτη της επαρκή εφαρμογής.
Το μοναδικό πρόβλημα που παρουσιάστηκε ήταν στην επιλογή των σημείων εισαγωγής του κώδικα καθοδήγησης. Χρειάστηκε μια εξοικείωση με την εφαρμογή, η οποία πιθανόν με άλλα εργαλεία να μην απαιτείται.