Β.8 ΣΤΑΤΙΣΤΙΚΑ ΑΠΟΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΩΝ

Επόμενο:Β.9 ΑΠΕΙΚΟΝΙΣΗ ΑΠΟΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΟΣ Πάνω: Παράρτημα Β Πίσω: B.7 ΕΜΦΑΝΙΣΗ ΚΑΙ ΙΧΝΗΛΑΤΗΣΗ ΤΙΜΩΝ ΜΕΤΑΒΛΗΤΩΝ

Β.8 ΣΤΑΤΙΣΤΙΚΑ ΑΠΟΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΩΝ

Στο σύστημα προσομοίωσης της Multi-Pascal κάθε πρόγραμμα μεταφράζεται πρώτα στην γλώσσα μιάς αφηρημένης παράλληλης ψευδο-μηχανής. Αυτός ο ψευδο-κώδικας στη συνέχεια διερμηνεύεται, δηλαδή μεταφράζεται και εκτελείται ψευδο-εντολή προς ψευδο-εντολή στη μηχανή στόχου μέσω ενός διερμηνέα Pascal. Η κάθε ψευδο-εντολή έχει εκτιμηθεί οτι κοστίζει ορισμένους κύκλους μηχανής (μονάδες χρόνου της αφηρημένης ψευδο-μηχανής). Μιά απλή εντολή κοστίζει μία μονάδα χρόνου ενώ μιά σύνθετη εντολή μπορεί να κοστίσει μέχρι έξι (6) μονάδες χρόνου. Κατά τη διερμηνεία του ψευδο-κώδικα η Multi-Pascal κρατά λογαριασμό του συνολικού χρόνου που απαιτείται τόσο γιά κάθε επεξεργαστή ξεχωριστά όσο και γιά το πρόγραμμα στο σύνολό του.

Με τη βοήθεια αυτών των υπολογισμών η Multi-Pascal στο τέλος της εκτέλεσης κάθε προγράμματος εμφανίζει τα παρακάτω στατιστικά στοιχεία

SEQUENTIAL EXECUTION TIME - Χρόνος Aκολουθιακής Εκτέλεσης, το άθροισμα του χρονικού κόστους των ψευδο-εντολών, δηλαδή ο συνολικός χρόνος εκτέλεσης εάν οι ψευδο-εντολές εκτελούνταν σε έναν επεξεργαστή.

PARALLEL EXECUTION TIME - Χρόνος Παράλληλης Εκτέλεσης, το χρόνικό κόστος των ψευδο-εντολών όπως μετρήθηκε στη συγκεκριμένη παράλληλη αρχιτεκτονική που επιλέχθηκε.

SPEEDUP - Επιτάχυνση, ο λόγος των χρόνων ακολουθιακής προς παράλληλη εκτέλεση.

NUMBER OF PROCESSORS USED - Αριθμός επεξεργαστών στη συγκεκριμένη παράλληλη αρχιτεκτονική που επιλέχθηκε.

Η Ωφέλιμη Χρήση (Utilization) προκύπτει από τον λόγο επιτάχυνσης προς αριθμό επεξεργαστών. Είναι προφανές οτι η επιτάχυνση είναι πάντα μικρότερη ή το πολύ ίση με τον αριθμό των επεξεργαστών, άρα και η ωφέλιμη χρήση είναι πάντα μικρότερη της μονάδας. Ωφέλιμη χρήση κοντά στη μονάδα σημαίνει πλήρη σχεδόν χρήση όλων των επεξεργαστών άρα μέγιστη δυνατή επιτάχυνση.

B.8.1 Η εντολή TIME

Εκτός από τα γενικά στοιχεία απόδοσης του αλγορίθμου που αναφέρθηκαν ήδη η Multi-Pascal προσφέρει αρκετές εντολές γιά την ακτίμηση της απόδοσης του προγράμματος σε διάφορες φάσεις της εκτέλεσής του. Μιά από αυτές είναι η εντολή TIME που μπορεί να χρησιμοποιηθεί καθε φορά που η εκτέλεση του προγράμματος αναστέλεται γιά να εμφανίσει τον παράλληλο χρόνο που πέρασε από την έναρξη της εκτέλεσης του προγράμματος ή από το τελευταίο σημείο παύσης. Γιά παράδειγμα

*ΤΙΜΕ

 

Since Start of Program:

Elapsed Time: 3450

Number of Processors Used: 14

Speedup: 10.7

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

*BREAK 24

 

*BREAK 28

 

*RUN

 

Break at 24 In Procedure ODDEVEN

Process Number 0

 

*CONTINUE

 

Break at 28 In Procedure ODDEVEN

Process Number 0

 

*ΤΙΜΕ

 

Since Start of Program:

Elapsed Time: 2890

Number of Processors Used: 20

Speedup: 5.4

 

Since Last Breakpoint:

Elapsed Time: 670

Speedup: 18.3

Βλέπουμε οτι η επιτάχυνση μεταξύ των γραμμών 24 και 28 είναι πολύ καλύτερη από ότι η συνολική επιτάχυνση. Αυτό σημαίνει ότι στο τμήμα του προγράμματος μεταξύ των γραμμών 1 και 24 εμφανίζει καποια προβλήματα.

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

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

*STEP 4

 

Break at 24 in Procedure COMPARE

Step Time is 50. Process running 100 percent.

Tο μήνυμα σημειώνει οτι η εκτέλεση 4 γραμμών απαίτησε 50 χρονικές μονάδες κατά τις οποίες η βηματική διεργασία είχε ωφέλιμη χρήση 100%. Εάν η βηματική διεργασία είχε γιά κάποιο λόγο σταματήσει προσωρινά να εκτελείται τότε η ωφέλιμη χρήση θα ήταν λιγότερη του 100%.

Ο χρόνος εκτέλεσης είναι επίσης διαθέσιμος στα προγράμματα της Multi-Pascal με τη βοήθεια ειδικών συναρτήσεων. Η συνάρτηση CLOCK επιστρέφει τον παράλληλο χρόνο που έχει διανυθεί ενώ η συνάρτηση SEQTIME επιστρέφει τον αντίστοιχο ακολουθιακό χρόνο. Οι τιμές που επιστρέφουν και οι δύο συναρτήσεις είναι πραγματικοί αριθμοί και μπορούν να εκτυπωθούν σαν τιμες μεταβλητών μέσα από προγράμματα της Multi-Pascal. Ετσι, για παράδειγμα, το πρόγραμμα του Σχήματος 2.3. μπορεί να μετατραπεί όπως παρακάτω

PROGRAM RankSort;

VAR ...

parstart, seqstart: REAL;

 

PROCEDURE PutinPlace(src: INTEGER);

...

 

BEGIN

    FOR i := 1 TO n DO

        Readln(values[i]);

    parstart := CLOCK; seqstart := SEQTIME

    FORALL i := 1 TO n DO

        PutinPlace(i);

    Writeln('Speedup is ', (SEQTIME-seqstart)/(CLOCK-parstart));

END.

B.8.2 H εντολή UTILIZATION

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

*UTILIZATION

 

PERCENT UTILIZATION

    PROCESSOR          SINCE START          SINCE LAST BREAK

        0                  63                      51

        1                  61                      76

        2                  62                      79

        3                  64                      84

        4                  66                      89

        5                  67                      91

        6                  67                      91

        7                  65                      89

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

*UTILIZATION <αριθμός επεξεργαστή>:<αριθμός επεξεργαστή>

Έτσι η εντολή

*UTILIZATION 20:30

εμφανίζει την ωφέλιμη χρήση των επεξεργαστών με αριθμούς 20 έως 30.

Β.8.3 Χρόνος ακολουθιακής εκτέλεσης

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

Επι πλέον, το παράλληλο πρόγραμμα μπορεί να περιέχει τμήματα ακραιφνώς παράλληλα, όπως κλειδώματα μεταβλητών, λειτουργίες συγχρονισμού, επικοινωνίες με πέρασμα μηνυμάτων και πιθανές καθυστερήσεις, κλπ. Για παράδειγμα στο κεφάλαιο 6 περιγράφεται μιά διαδικασία φράγμματος γιά τον συγχρονισμό παράλληλων διεργασιών. Σε ένα ακολουθιακό πρόγραμμα τέτοιος συγχρονισμός δεν είναι απαραίτητος, άρα ο χρόνος εκτέλεσης της διαδικασίας δεν πρέπει να προσμετρηθεί στον ακολουθιακό χρόνο. Γι' αυτό το λόγο η Multi-Pascal διαθέτει ένα ζεύγος εντολών προς τον διερμηνέα που επιτρέπουν την προσωρινή διακοπή μέτρησης του ακολουθιακού χρόνου. Η εντολή %SEQOΝ ορίζει την έναρξη μέτρησης και η εντολή %SEQOFF τη διακοπή μέτρησης. Η χρήση τους φαίνεται στο παρακάτω παράδειγμα

PROCEDURE Barrier;

VAR ...

BEGIN

    %SEQOFF;

    ...

    %SEQON;

END;

B.8.4 H εντολή ALARM

Μερικές φορές γιά λόγους ελέγχου είναι χρήσιμο να σταματήσουμε την εκτέλεση του προγράμματος σε συγκεκριμένη χρονική στιγμή θέτοντας ένα κατάλληλο σημείο συναγερμού. Αυτό μπορεί να επιτευχθεί με την εντολή ALARM. Η γενική μορφή της εντολής είναι

*ALARM <μονάδες χρόνου>

Έτσι, γιά να σταματήσουμε ένα πρόγραμμα σε 1500 μονάδες χρόνου γράφουμε

*ALARM 1500

Οι μονάδες χρόνου του σημείου συναγερμού μετρούνται πάντα από την αρχή της εκτέλεσης ενός προγράμματος και όχι από πιθανά ενδιάμεσα σημεία παύσης. Μόλις η Multi-Pascal μετρήσει 1500 μονάδες χρόνου η εκτέλεση θα διακοπεί με το μήνυμα

Time is 1500. Alarm Went Off.

Η ακύρωση του σημείου συναγερμού γίνεται γίνεται με την εντολή

*ALARM 1500

H εντολή DISPLAY εκτός από τα σημεία παύσης και της μεταβλητές ίχνους, εμφανίζει και την κατάσταση του σημείου συναγερμού.

Β.8.5 H εντολή VARIATION

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

*VARIATION ON

Αφού εισαχθεί αυτή η εντολή ο χρήστης μπορεί να ξεκινήσει την εκτέλεση του προγράμματος κανονικά. Ομως μόλις ο χρήστης εισάγει την εντολή RUN η Multi-Pascal του ζητά έναν ακέραιο αριθμό ο οποίος χρησιμοποιείται γιά την εκκίνηση μιάς γεννήτριας τυχαίων αριθμών. Η γεννήτρια παράγει γιά καθε επεξεργαστή i έναν συντελεστή ei (μεταξύ του 0 και του 1), ο οποίος αυξάνει την ταχύτητα του επεξεργαστή κατά 1/ei. Αυτός ο συντελεστής μένει ενεργός σε όλη τη διάρκεια της συγκεκριμένης εκτέλεσης. Σε επόμενη εκτέλεση ο χρήστης μπορεί να εισάγει διαφορετικό ακέραιο γιά την εκκίνηση της γεννήτριας που θα παράγει διαφορετικές σχετικές ταχύτητες στους επεξεργαστές.

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

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

Η διακύμανση των σχετικών ταχυτήτων ακυρώνεται με την εντολή

*VARIATION OFF

B.8.6 Η εντολή DURATION

Η Multi-Pascal διαθέτει μιά ενσωματωμένη διαδικασία αναστολής της εκτέλεσης ενός προγράμματος για συγκεκριμένο χρονικό διάστημα. Η γενική μορφή της διαδικασίας είναι

DURATION(<έκφραση>);

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

H διαδικασία DURATION είναι ιδαίτερα χρήσιμη γιά τον διαχωρισμό του χρόνου δημιουργίας διεργασιών από τον χρόνο των καθαρών υπολογισμών. Όταν η Multi-Pascal δημιουργεί ένα μεγάλο αριθμό διεργασιών-παιδιών τότε υπάρχει σημαντική χρονική διαφορά μεταξύ της δημιουργίας της πρώτης και της τελευταίας διεργασίας. Επι πλέον οι πρώτες διεργασίες αρχίζουν να εκτελούνται αμέσως μόλις δημιουργηθούν ενώ παράλληλα συνεχίζεται η δημιουργία άλλων διεργασιών. Έτσι ο χρόνος δημιουργίας διεργασιών δεν μπορεί να απομονωθεί από τον χρόνο εκτέλεσης. Η διαδικασία DURATION μπορεί να δώσει μιά λύση αναγκάζοντας όλες τις διεργασίες παιδιά να περιμένουν την ολοκλήρωση της φάσης της δημιουργίας πριν ξεκινήσουν την φάση της εκτέλεσης.

Θεωρείστε γιά παράδειγμα τη παρακατω δομή δημιουργίας διεργασιών

BEGIN

    ...

    FORALL i := 1 TO 100 DO

        Compute (i);     

    ...

END.

Tο πρώτο βήμα είναι να ελέγξουμε σε πόσες χρονικές στιγμές ολοκληρώνεται η δημιουργία των 100 διεργασιών. Θέτοντας ένα κατάλληλο σημείο παύσης έστω οτι διαπιστώνουμε οτι η δημιουργία ολοκληρώνεται σε 6000 χρονικές μονάδες. Στη συνέχεια τροποποιούμε το πρόγραμμα όπως παρακάτω

PROCEDURE Compute(i : INTEGER);

VAR ...

BEGIN

    DURATION (TRUNC(6000-CLOCK));

    ...

END;

Όταν το σημείο εκτέλεσης μιάς διεργασίας φθάσει στη διαδικασία DURATION τότε η διεργασία θα σταματήσει γιά 6000-CLOCK χρονικές μονάδες, όπου CLOCK είναι ο τρέχων χρόνος του συστήματος. Έτσι ανεξάρτητα από το πότε μιά από τις 100 διεργασίες-παιδιά θα φθάσει στην εκτέλεση της διαδικασάις DURATION είναι σίγουρο οτι όλες θα σταματήσουν και θα περιμένουν μέχρι τη χρονική στιγμή 6000. Γιά να βρούμε τον χρόνο εκτέλεσης του υπολοίπου προγράμματος δεν έχουμε παρά να το εκτελέσουμε κανονικά και να αφαιρέσουμε 6000 μονάδες χρόνου.