Ασκήσεις

ΕπόμενοΚεφάλαιο 9o: Επιμερισμός δεδομένων Πάνω: Κεφάλαιο 8o: Προγράμματα περάσματος μηνυμάτων Πίσω: Προγραμματιστικές Εργασίες

ΑΣΚΗΣΕΙΣ

1. Για κάθε μια από τις ακόλουθες τοπολογίες υπολογίστε την καθυστέρηση επικοινωνίας στην αποστολή ενός μηνύματος με πέντε πακέτα από τον επεξεργαστή 3 στον επεξεργαστή 20. Χρησιμοποιείστε το μοντέλο επικοινωνίας που περιγράφτηκε στην παράγραφο 8.4.1 και υποθέστε ότι η βασική καθυστέρηση επικοινωνίας είναι 10 μονάδες χρόνου.

(α) SHARED (50)

(β) FULLCONNECT(50)

(γ) LINE(50)

(δ) RING(50)

(ε) MESH(7)

(στ) MESH(4)

(ζ) TORUS(7)

(η) HYPERCUBE(5)

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

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

Send(M, i) αποστολή της τιμής που περιέχεται στη μεταβλητή M στον επεξεργαστή i

Receive(M) λαμβάνει την επόμενη εισερχόμενη επικοινωνία και την αποθηκεύει στη μεταβλητή M

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

4. Δώστε μια παρουσίαση της τεχνικής για τους πίνακες θυρών, ως τμήμα της Multi-Pascal εφαρμογής των θυρών επικοινωνίας. Αναλύστε με λεπτομέρειες καθένα από τα ακόλουθα θέματα:

(α) Τι είδους πληροφορία περιλαμβάνεται στους πίνακες θυρών;

(β) Πότε και πώς δημιουργείται ένας πίνακας θυρών;

(γ) Πότε και πώς κατανέμεται ο πίνακας θυρών στις διεργασίες;

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

(ε) Τι συμβαίνει όταν μια διεργασία επιχειρήσει να γράψει σε μια θύρα που δεν της έχει ανατεθεί ακόμα; (Βεβαιωθείτε ότι η εφαρμογή σας χειρίζεται αυτή την πιθανότητα χωρίς λάθος)

5. Στο παρόν κεφάλαιο δίνεται ο ακόλουθος τύπος όσον αφορά την καθυστέρηση επικοινωνίας για την αποστολή ενός μηνύματος με k πακέτα κατά μήκος ενός μονοπατιού με m συνδέσμους:

m ( T + P ) + ( k - 1 ) max ( T, P )

Περιγράψτε λεπτομερώς την προέλευση και δικαιολογήστε αυτό τον τύπο, δίνοντας ιδιαίτερη έμφαση στον όρο “max”.

6. Για μια τοπολογία LINE η ακόλουθη συνάρτηση υπολογίζει την καθυστέρηση επικοινωνίας για ένα μήνυμα με ένα πακέτο, ανάμεσα στον επεξεργαστή αφετηρίας και προορισμού:

FUNCTION Delay(Source, Destination: INTEGER): INTEGER;


CONST D= 10; (*Βασική καθυστέρηση σε ένα γειτονικό επεξεργαστή*)


BEGIN


    Delay:= D*ABS(Destination-Source);


END;

Για κάθε μία από τις ακόλουθες τοπολογίες γράψτε μια αντίστοιχη συνάρτηση που θα υπολογίζει την καθυστέρηση επικοινωνίας για ένα πακέτο ανάμεσα στον επεξεργαστή αφετηρίας και προορισμού:

(α) RING(100)

(β) FULLCONNECT(100)

(γ) MESH(10)

(δ) HYPERCUBE(7)

7. Θεωρείστε μια νέα τοπολογία συστήματος κατανεμημένης μνήμης στη μορφή του δυαδικού δένδρου. Ο επεξεργαστής 0 στην ρίζα είναι απευθείας συνδεδεμένος με δυο επεξεργαστές. Καθένας από αυτούς τους επεξεργαστές είναι επίσης συνδεδεμένος με δυο επιπλέον επεξεργαστές. Η τοπολογία TREE έχει τη μορφή ενός πλήρους δυαδικού δένδρου με έναν επεξεργαστή σε κάθε κόμβο και φύλλο του δένδρου. Η τοπολογία χαρακτηρίζεται από μια παράμετρο που δίνει το βάθος του δένδρου. Για αυτή την τοπολογία δένδρου γράψτε μια συνάρτηση “Delay”, όπως αυτή περιγράφτηκε στην άσκηση 6.

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

(α) Για μια τοπολογία MESH2(m), γράψτε τις ακόλουθες συναρτήσεις της Multi-Pascal:

FUNCTION Procnum μετατρέπει μια θέση συντεταγμένης σε αριθμό επεξεργαστή

FUNCTION Position μετατρέπει έναν αριθμό επεξεργαστή σε μια θέση συντεταγμένης

(β) Για μια τοπολογία MESH3(m) γράψτε τις ακόλουθες συναρτήσεις της Multi-Pascal:

FUNCTION Procnum μετατρέπει μια θέση συντεταγμένης σε έναν αριθμό επεξεργαστή

FUNCTION Position μετατρέπει έναν αριθμό επεξεργαστή σε μια θέση συντεταγμένης

9. Στο τμήμα 10.1 του Παραρτήματος περιγράφεται ένας τυπικός αλγόριθμος δρομολόγησης Υπερκύβου.

(α) Δείξτε ότι αυτός ο αλγόριθμος πάντα οδηγεί σε ένα μονοπάτι ελάχιστου μήκους από την αφετηρία στον προορισμό.

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

10. Παρακάτω δίνεται ένα Παράλληλο πρόγραμμα Παραγοντικού για ένα σύστημα κατανεμημένης μνήμης:

PROGRAM Factorial;


VAR i, j, n, middle: INTEGER;


    prod, fact: REAL;


BEGIN


    Write(‘Input number: ‘);


    Readln(n);


    middle:= n DIV 2;


    FORK


    BEGIN


        prod:= 1;


        FOR i:= n DOWNTO middle DO prod:= prod*i;


    END;


    FORK


    BEGIN


        fact:= 1;


        FOR j:= middle-1 DOWNTO 2 DO fact:= fact*j;


    END;


    JOIN; JOIN;


    Writeln(‘Factorial is ‘, fact*prod:1);


END.

(α) Εκτελέστε αυτό το πρόγραμμα για να προσδιορίσετε το χρόνο εκτέλεσης και την επιτάχυνση του προγράμματος

(β) Τροποποιήστε το πρόγραμμα έτσι ώστε να προσαρμόζεται στην τεχνική του περάσματος μηνυμάτων. Εκτελέστε το τροποποιημένο πρόγραμμα χρησιμοποιώντας αρχιτεκτονική FULLCONNECT για να προσδιορίσετε το χρόνο εκτέλεσης και την επιτάχυνσή του.

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

12. Εκτελέστε το ακόλουθο πρόγραμμα για να προσδιορίσετε το χρόνο εκτέλεσης και την επιτάχυνσή του:

PROGRAM Pipeline;


TYPE pipetype: CHANNEL OF INTEGER;


VAR PIPE: ARRAY [1..3] OF pipetype;


    i: INTEGER;

 


PROCEDURE Process(VAR in, out: INTEGER);


VAR value: INTEGER;


BEGIN


    REPEAT


        value:= pipe[in];


        pipe[out]:= value;


    UNTIL value= -1;


END;

 


BEGIN


    FORK Process(1, 2);


    FORK Process(2, 3);


    FOR i:= 1 TO 100 DO


        pipe[1]:= i;


    pipe[1]:= -1;


END.

Αλλάξτε την αρχιτεκτονική του παραπάνω προγράμματος σε RING(10). Χωρίς την αλλαγή κάποιου άλλου τμήματος του προγράμματος, προσθέστε τα στοιχεία PORT και @ για να βελτιώσετε την απόδοση στην τοπολογία RING. Εκτελέστε ξανά το πρόγραμμα για να προσδιορίσετε το χρόνο εκτέλεσης και την επιτάχυνσή του.

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

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

15. Στο κεφάλαιο 6 παρουσιάστηκαν τρεις τεχνικές εφαρμογής Φράγματος: η μέθοδος Κεντρικού Αθροιστή, η Τεχνική Τουρνουά και η μέθοδος Τοπικού Φράγματος. Ποιες από αυτές τις τεχνικές είναι κατάλληλη για σύστημα κατανεμημένης μνήμης; Αιτιολογήστε την απάντησή σας.

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

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

18. Στο κεφάλαιο 2 παρουσιάστηκε ένα απλό παράλληλο πρόγραμμα πολλαπλασιασμού μητρών. Μετατρέψτε αυτό το πρόγραμμα στην τεχνική του περάσματος μεταβλητών, έτσι ώστε να εκτελείται σε σύστημα κατανεμημένης μνήμης.

19. Στο κεφάλαιο 4 παρουσιάστηκε ένα παράλληλο πρόγραμμα Προς τα Πίσω Αντικατάστασης. Μετατρέψτε αυτό το πρόγραμμα, ώστε να εκτελείται τοπολογία Δακτυλίου συστήματος κατανεμημένης μνήμης.