Ασκήσεις

Επόμενο:Κεφάλαιο 7o : Αρχιτεκτονική συστημάτων κατανεμημένης μνήμης Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: Προγραμματιστικές Εργασίες

ΑΣΚΗΣΕΙΣ

1. Οι σηματοφορείς αποτελούν μια δημοφιλή τεχνική συγχρονισμού στις παράλληλες γλώσσες προγραμματισμού. Το 5^ο κεφάλαιο παρουσιάζει ένα γενικό ορισμό των σηματοφορέων και τις λειτουργίες που συνδέονται με αυτούς - την αναμονή και το σήμα. Υποθέστε ότι αντί για μεταβλητές κανάλια η Multi-Pascal έχει μεταβλητές σηματοφορέων. Ξαναγράψτε την διαδικασία Barrier για τη μέθοδο του κεντρικού αθροιστή και χρησιμοποιήστε σηματοφορείς αντί για κλειδώματα.

2. Στο κεφάλαιο 5 παρουσιάζεται η δημοφιλής τεχνική συγχρονισμού, οι σηματοφορείς, και οι λειτουργίες που συνδέονται με αυτούς - η αναμονή και το σήμα. Χρησιμοποιώντας έναν πίνακα σηματοφορέων αντί για πίνακα καναλιών, ξαναγράψτε τη διαδικασία Barrier που χρησιμοποιεί τη μέθοδο δυαδικού δένδρου.

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

Άφιξη - ξεκλείδωτη

Αναχώρηση - κλειδωμένη

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

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


(*Τοπικά διαμοιραζόμενες μεταβλητές*)


VAR count : Integer;


    L : Spinlock;

 

PROCEDURE Barrier;


BEGIN


    Lock(L);


    count := count + 1;


    Unlock(L);


    While count ‹ n do; (*Ενεργός Αναμονή μέχρι την άφιξη όλων των διεργασιών *)

END;

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

5. Πιο πριν στο κεφάλαιο δείξαμε πως μπορεί να μετατραπεί η διαδικασία του κεντρικού αθροιστή με φράγμα, έτσι ώστε να πραγματοποιήσει την συλλογή και τη διάδοση των Boolean τιμών. Κάθε διεργασία περνά μια Boolean παράμετρο σε μια συνάρτηση Aggregate, η οποία εκτελεί τη λογική πράξη AND σε όλες και επιστρέφει το αποτέλεσμα - που είναι Boolean τιμή. Μια άλλη τεχνική είναι η δημιουργία μιας ειδικής διεργασίας Aggregate, η οποία έχει ένα κανάλι όπου όλες οι διεργασίες γράφουν την Boolean τιμή τους. Η διεργασία Aggregate υπολογίζει την πράξη AND όλων των Boolean και μετά στέλνει ένα αντίγραφο του αποτελέσματος σε κάθε διεργασία, χρησιμοποιώντας έναν πίνακα καναλιών, με κάθε στοιχείο του να έχει ανατεθεί και σε μια διεργασία. Γράψτε και ελέξτε αυτή τη διεργασία συλλογής χρησιμοποιώντας το σύστημα της Multi-Pascal.

6. Μετατρέψτε τη διαδικασία δυαδικού δένδρου με φράγμα σε μια συνάρτηση συλλογής που επιτυγχάνει την ίδια O(logn) απόδοση. Ελέγξτε τη συνάρτηση με το σύστημα της Multi-Pascal.

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

8. Η διαδικασία δυαδικού δένδρου με φράγμα του σχήματος 6.10 δουλεύει μόνο να το n είναι δύναμη του 2. Παρουσιάστε κάποιες απλές τροποποιήσεις σε αυτή τη διαδικασία, έτσι ώστε να δουλεύει για κάθε τιμή του n. Αν το n δεν είναι δύναμη του 2, τότε μετά από κάποιους γύρους κάποιες διεργασίες νικητές θα δουν ότι στο τουρνουά δεν έχουν χαμένους αντιπάλους Στην περίπτωση αυτή θα ανακηρύξουν τους εαυτούς τους νικητές και θα συνεχίσουν στον επόμενο γύρο. Για την επίτευξη αυτού θα χρειαστούν κάποιες πολύ μικρές μετατροπές στη διαδικασία. Ελέγξτε τη νέα διαδικασία χρησιμοποιώντας το σύστημα της Multi-Pascal. Χρησιμοποιήστε μια δήλωση FORALL που δημιουργεί κάποιες διεργασίες που θα καλούν τη διαδικασία φράγματος.

9. Στην τεχνική τουρνουά για τη δημιουργία φράγματος είναι ενδιαφέρον ότι ο αριθμός των γύρων στους οποίους κάθε διεργασία κερδίζει είναι ακριβώς ίσος με τον αριθμό των προηγούμενων μηδενικών στον δυαδικό αριθμό της διεργασίας. Τα προηγούμενα μηδενικά είναι όλα τα 0 bits που συναντιούνται όταν κινούμαστε από τα δεξιά προς τα αριστερά μέχρι να βρούμε το πρώτο 1 bit.

(α) Εξηγείστε γιατί συμβαίνει αυτό.

(β) Γράψτε μια συνάρτηση FindTrail που υπολογίζει και επιστρέφει τον αριθμό των προηγούμενων μηδενικών σε μια δυαδική μορφή του I.

Αυτή η περίπτωση των προηγούμενων μηδενικών μπορεί να γίνει ρουτίνα ώστε να γίνει περισσότερο αποδοτική η διαδικασία δημιουργίας του δυαδικού δένδρου. Η διαδικασία χρησιμοποιεί τον νέο πίνακα ακεραίων, τον trailzero, που περιέχει τον αριθμό των προηγούμενων μηδενικών κάθε διεργασίας. Έτσι, η διεργασία i μπορεί να βρει πόσα προηγούμενα μηδενικά έχει με το να δει το στοιχείο trailzero[i]. Στη διαδικασία φράγματος μπορούμε να αλλάξουμε τους βρόχους WHILE με βρόχους FOR.

(γ) Γράψτε μια νέα διαδικασία φράγματος που κάνει χρήση του πίνακα trailzero.

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

10. Το πρόγραμμα Jacobi του σχήματος 6.11 χρησιμοποιεί την τεχνική του τοπικού φράγματος για συγχρονισμό. Έστω οι ακόλουθες τροποποιήσεις της διαδικασίας τοπικού φράγματος :


PROCEDURE LocalBarrier (i : Integer);


VAR dummy : Integer;

 

BEGIN


    If i > 1 then dummy := lower[i];

    If i < n then

    BEGIN

        dummy := higher[i];

        lower[i+1] := 1;

    END;

    If i > 1 then higher[i-1] := 1;

END;

Δείξτε ότι αυτή η νέα διαδικασία θα καταλήξει σε αδιέξοδο.

11. Το πρόγραμμα Jacobi του σχήματος 6.11 χρησιμοποιεί μια τεχνική τοπικού φράγματος για συγχρονισμό. Έστω οι ακόλουθες τροποποιήσεις στη διαδικασία φράγματος :


PROCEDURE LocalBarrier (i : Integer);


VAR dummy : Integer;

 

BEGIN


    If i > 1 then

    BEGIN

        higher[i-1] := 1;

        dummy ;= lower[i];

    END;

    If i < n then

    BEGIN

        lower[i+1] := 1;

        dummy := higher[i];

    END;

END;

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

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