Επόμενο:Κεφάλαιο 11o: Κατανεμημένη Ανίχνευση Τερματισμού Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Προγραμματιστικές Εργασίες

ΑΣΚΗΣΕΙΣ

1. Δώστε μια σύντομη περιγραφή του υποδείγματος Αντιγράφων Εργαζομένων του παράλληλου προγραμματισμού.

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

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

4. Στη διεργασία Worker του σχήματος 10.3 το κλείδωμα L[w] χρησιμοποιείται για να πραγματοποιήσει αμοιβαίο αποκλεισμό στην πρόσβαση στο mindist[w].

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

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

5. Στον παράλληλο αλγόριθμο Συντομότερου Μονοπατιού του σχήματος 10.3 το γράφημα αναπαρίστανται με τον δι-διάστατο πίνακα weight. Θεωρείστε μια εναλλακτική αναπαράσταση του γραφήματος στην οποία κάθε κόμβος έχει μια συνδεδεμένη λίστα με τις εξερχόμενες ακμές. Κάθε ακμή στη λίστα είναι μια εγγραφή που περιέχει τον κόμβο προορισμού και την απόσταση προς αυτόν τον κόμβο. Ξαναγράψτε τη διαδικασία Worker χρησιμοποιώντας αυτή τη νέα αναπαράσταση του γραφήματος. Μπορείτε να ακολουθήσετε κάποιον από τους ακόλουθους ορισμούς:

TYPE edgepnt=^edge;

        edge=RECORD

             destination: INTEGER; (*Αριθμός κόμβου*)

             weight: INTEGER; (*Απόσταση*)

             link: edgepnt; (*Δείκτης στην επόμενη ακμή*)

             END;

VAR graph: ARRAY [1..n] OF edgepnt; (*Δείκτης στην λίστα edge*)

Ο πίνακας graph περιέχει δείκτες που δείχνουν στην λίστα ακμών για κάθε κόμβο. Για τον κόμβο i το graph[i] δείχνει στην αρχή της λίστας ακμών του κόμβου i.

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

7. Στην υλοποίηση του σχήματος 10.7 των Δεξαμενών Εργασίας σε σύστημα διαμοιραζόμενης μνήμης ποιες ιδιότητες των εργαζομένων καθορίζουν μια καλή επιλογή του μεγέθους της Ομάδας Εργαζομένων; Εξηγείστε γιατί κάποιοι αλγόριθμοι Αντιγράφων Εργαζομένων απαιτούν μεγαλύτερο ή μικρότερο μέγεθος ομάδας σε σχέση με αυτό του αλγορίθμου του Συντομότερου Μονοπατιού.

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

9. Σε κάποια προγράμματα Αντιγράφων Εργαζομένων μπορεί να είναι χρήσιμο να τερματιστεί το πρόγραμμα ενώ ακόμα υπάρχουν αντικείμενα στην Δεξαμενή Εργασίας. Για παράδειγμα, αυτή η περίπτωση μπορεί να προκύψει σε ένα δένδρο ή ένα γράφημα αναζήτησης όταν ο στόχος της αναζήτησης έχει επιτευχθεί. Για αυτό το λόγο μπορεί να προστεθεί στην υλοποίηση της Δεξαμενής Εργασίας μια νέα διαδικασία, η “Terminate”, η οποία μπορεί να καλείται από κάθε εργαζόμενο για να σταματήσει άμεσα τους υπολογισμούς. Δώστε ένα λεπτομερές σχέδιο για αυτή τη διαδικασία Terminate και επίσης περιγράψτε όποιες τροποποιήσεις χρειάζονται στις διαδικασίες Getwork και Putwork.

10. Στην υλοποίηση της Δεξαμενής Εργασίας που περιγράφτηκε στην παράγραφο 10.4 μια διεργασία Εργαζόμενος καθυστερείται αν το κανάλι που έχει ανατεθεί στην Ομάδα του είναι άδειο. Θεωρείστε την ακόλουθη τροποποίηση: αν ένας εργαζόμενος βρει ότι το κανάλι του είναι άδειο, τότε ανιχνεύει τα άλλα κανάλι για να βρει κάποιο με αντικείμενα εργασίας. Ξαναγράψτε τις περιγραφές υψηλού επιπέδου των Getwork και Putwork έχτι ώστε να υλοποιούν αυτή την τροποποίηση.

11. Θεωρείστε μια τροποποίηση στην υλοποίηση του σχήματος 10.7 των Δεξαμενών Εργασίας για συστήματα διαμοιραζόμενης μνήμης στην οποία η αρχική τιμή του δείκτη nextchan κάθε εργαζομένου υπολογίζεται τυχαία. Αναλύστε τα πλεονεκτήματα αυτής της τροποποίησης. Περιγράψτε με λεπτομέρεια τις αλλαγές που είναι απαραίτητες στο πρόγραμμα 10.7 έτσι ώστε να υλοποιεί αυτή την τροποποίηση.

12. Το σχήμα 10.8 δείχνει μια απώλεια της επιτάχυνσης της τάξης του 42% χρησιμοποιώντας 20 Ομάδες Εργαζομένων. Χρησιμοποιήστε θεωρητική ανάλυση για να προσεγγίσετε πόση από αυτή την απώλεια οφείλεται σε συμφόρηση καναλιών.

13. Υποθέστε ότι ένα πρόγραμμα Αντιγράφων Εργαζομένων έχει S όριο κορεσμού για το μέγεθος μιας ομάδας εργασίας. Αν το πραγματικό μέγεθος των ομάδων εργασίας είναι .5S, ποια είναι η αναμενόμενη μείωση της απόδοσης από τη συμφόρηση των καναλιών; (Η απάντησή σας πρέπει να είναι σε όρους του S).

14. Χρησιμοποιώντας το σχήμα 10.9 εκτιμήστε πόση μείωση της απόδοσης είναι αποτέλεσμα της έλλειψης επαρκούς εργασίας και πόση της ανισορροπίας φορτίου.

15. Σε μια εναλλακτική μοντελοποίηση του υποδείγματος των Αντιγράφων Εργαζομένων η Δεξαμενή Εργασίας μπορεί να αντικατασταθεί από αναδρομή στους εργαζόμενους. Σε αυτή τη μοντελοποίηση η διαδικασία Worker έχει μια παράμετρο-τον κόμβο στον οποίο λειτουργεί. Αφού τελειώσει με την μοναδική αυτή είσοδο του ενός κόμβου, ο εργαζόμενος τερματίζει. Έτσι δεν χρειάζεται η κλήση της Getwork. Επίσης, αντί να καλεί την Putwork(me,w) για να τοποθετεί κάθε κόμβο w στην Δεξαμενή Εργασίας, ο εργαζόμενος εκτελεί την ακόλουθη εντολή για να δημιουργήσει ένα νέο εργαζόμενο:

FORK Worker(w); (*Δημιουργία νέου εργαζόμενου για τον κόμβο w*)

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

16. Βρείτε μια λύση με το χέρι για το πρόβλημα των Ν Βασιλισσών για n=4.

17. Για το πρόγραμμα των Ν Βασιλισσών του σχήματος 10.12 χρησιμοποιήστε την Multi-Pascal για να εκτιμήσετε εμπειρικά το όριο κορεσμού για τους εργαζόμενους σε μια μόνο ομάδα εργασίας Χρησιμοποιήστε δύο διαφορετικές μεθόδους μέτρησης για να βεβαιωθείτε ότι η εκτίμησή σας είναι ακριβής. Η τεχνική μέτρησης σας πρέπει να είναι ιδιαίτερα προσεκτική, έτσι ώστε να μετράει το όριο κορεσμού και όχι κάτι άλλο.

Επόμενο:Κεφάλαιο 11o: Κατανεμημένη Ανίχνευση Τερματισμού Πάνω: Κεφάλαιο 10o : Αντίγραφα Εργαζομένων Πίσω: Προγραμματιστικές Εργασίες