Ασκήσεις

Επόμενο:Κεφάλαιο 4o : Επικοινωνία διεργασιών Πάνω: Κεφάλαιο 3ο :Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω:Αναφορές

ΑΣΚΗΣΕΙΣ

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

2. Φανταστείτε δύο γενικές τεχνικές για την σύνδεση συσκευών εισόδου-εξόδου (I/O) σε ένα σύστημα διαμοιραζόμενης μνήμης βασισμένο σε δίαυλο όπου:

α. Οι συσκευές εισόδου-εξόδου συνδέονται απευθείας στον κοινό δίαυλο και προσπελαύνουν τη διαμοιραζόμενη μνήμη διαμέσου του διαύλου.

β. Οι συσκευές εισόδου-εξόδου συνδέονται σε ένα ξεχωριστό δίαυλο εισόδου-εξόδου που έχει άμεση προσπέλαση στις θέσεις μνήμης μέσα στη διαμοιραζόμενη μνήμη.

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

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

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

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

6. Η λύση, που παρουσιάζεται σε αυτό κεφάλαιο, για τη διατήρηση της συνοχής της κρυφής μνήμης είναι μια τεχνική απευθείας-εγγραφής σε κάθε λειτουργία εγγραφής σε ένα τμήμα της κρυφής μνήμης. Για την αποφυγή της αναγκαιότητας μιας απευθείας-εγγραφής, ορισμένα συστήματα διαμοιραζόμενης μνήμης περιλαμβάνουν ένα bit ετικέτας (tag bit) σε κάθε τμήμα της κρυφής μνήμης, που δείχνει αν και άλλες κρυφές μνήμες έχουν αντίγραφο του ίδιου τμήματος. Ένα bit ετικέτας με τιμή 1 σημαίνει ότι δεν υπάρχουν άλλα αντίγραφα ενώ ένα bit ετικέτας με τιμή 0 σημαίνει ότι υπάρχουν και άλλα αντίγραφα.

Κατά τη διάρκεια μιας λειτουργίας εγγραφής σε κάποιο τμήμα της κρυφής μνήμης, εξετάζεται η τιμή του bit ετικέτας. Εάν η ετικέτα είναι ίση με 0 τότε εφαρμόζεται η συνήθης τεχνική απευθείας-εγγραφής. Ωστόσο, αν η ετικέτα είναι ίση με 1 τότε η εγγραφή εκτελείται τοπικά μόνο μέσα στη κρυφή μνήμη δίχως χρήση του διαύλου ή της διαμοιραζόμενης μνήμης. Η διαμοιραζόμενη μνήμη θα ενημερωθεί αργότερα, χρησιμοποιώντας τη συνηθισμένη τεχνική ανάστροφης-εγγραφής της κρυφής μνήμης.

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

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

7. Στα σχεδιαγράμματα 3.4 και 3.5 φαίνεται, πως η τεχνική της χρονομετάθεσης πετυχαίνει την εξάλειψη του ανταγωνισμού πρόσβασης της μνήμης όταν χρησιμοποιούνται πολλαπλά τμήματα μνήμης. Υπάρχουν πολλές σημαντικές συνθήκες που πρέπει να ικανοποιηθούν ώστε να επιτευχθεί αυτό το πρότυπο έλλειψης ανταγωνισμού:

α. Οι παρακείμενες διευθύνσεις μνήμης πρέπει να διασκορπιστούν με μια σειρά μέσα στα τμήματα.

β. Κάθε επεξεργαστής προσπελαύνει σειριακά τις διαδοχικές διευθύνσεις μνήμης.

γ. Ο αριθμός των επεξεργαστών πρέπει να μικρότερος από ή ίσος με τον αριθμό των τμημάτων μνήμης.

δ. Οι επεξεργαστές πρέπει να προσπελαύνουν την μνήμη με την ίδια συχνότητα.

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

Στο παράδειγμα των σχεδιαγραμμάτων 3.4 και 3.5, οι επεξεργαστές αναφέρονται σε διευθύνσεις με την ίδια συχνότητα και ξεκινούν την εκτέλεση την ίδια χρονική στιγμή. Οι συνθήκες που μόλις αναφέρθηκαν δεν είναι απαραίτητο να ισχύουν. Όσο οι 4 συνθήκες που παρουσιάζονται στην παραπάνω λίστα ικανοποιούνται, οι επεξεργαστές μπορούν να ξεκινούν οποιαδήποτε στιγμή και να προσπελαύνουν παρακείμενες θέσεις μνήμης με οποιαδήποτε συχνότητα. Όταν κάθε επεξεργαστής προσπελαύνει τη μνήμη για πρώτη φορά, μπορεί να αντιμετωπίσει ορισμένες καθυστερήσεις εάν ξεκινήσει με κάποιο τμήμα μνήμης που προσπελαύνεται εκείνη τη στιγμή από κάποιο άλλο επεξεργαστή. Ωστόσο, έπειτα από ορισμένες αρχικές καθυστερήσεις, ο επεξεργαστής σύντομα θα εισέλθει σε μια σειρά με τους υπόλοιπους επεξεργαστές και δεν θα υπάρχει πρόσθετος ανταγωνισμός πρόσβασης μνήμης.

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

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

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

γ. Γενικά, για n επεξεργαστές και n τμήματα μνήμης, πόσα στάδια απαιτούνται στο δίκτυο πεταλούδας;

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

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

10. Σχεδιάστε ένα στάδιο ενός δικτύου διαπλοκής-εναλλαγής για την σύνδεση 16 επεξεργαστών με 16 τμήματα μνήμης.

11. Στα δίκτυα διασύνδεσης επεξεργαστή-μνήμης, είναι απαραίτητο για ένα συγκεκριμένο επεξεργαστή να μεταδώσει κάτι σε όλους τους άλλους επεξεργαστές. Στο δίκτυο διαπλοκής-εναλλαγής που υπάρχει στο σχεδιάγραμμα 3.8, δείξτε με ποίο τρόπο ο επεξεργαστής P0 θα μπορούσε να χρησιμοποιήσει το δίκτυο για να μεταδώσει μια τιμή στους υπόλοιπους επεξεργαστές. Ποιοι μεταγωγείς πρέπει να χρησιμοποιηθούν και πως θα μετακινηθούν δεδομένα μέσα στο δίκτυο; Προσπαθήστε να μειώσετε το πλήθος της δραστηριότητας μέσα στο δίκτυο προκειμένου να επιτευχθεί η διάδοση. (Βοήθεια: Η διάδοση μπορεί να γίνει χρησιμοποιώντας μόνο 7 από τους 12 μεταγωγείς).

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

12. Ορισμένοι παράλληλοι υπολογιστές έχουν ιεραρχικό σύστημα μνήμης. Οι επεξεργαστές ομαδοποιούνται σε τοπικές συστάδες των 8-16 επεξεργαστών. Κάθε τοπική συστάδα διαθέτει τη δική της διαμοιραζόμενη μνήμη, προσπελάσιμη μόνο από τους επεξεργαστές εκείνης της συστάδας. Οι συστάδες συνδέονται σε μια γενική διαμοιραζόμενη μνήμη που είναι προσπελάσιμοι από όλους τους επεξεργαστές. Ο χρόνος προσπέλασης στη τοπική μνήμη της συστάδας είναι ταχύτερος από το χρόνο προσπέλασης στη γενική διαμοιραζόμενη μνήμη.

Σε τέτοια συστήματα, ορισμένες φορές παρατηρείται μια ιδιαίτερα ενδιαφέρουσα ανωμαλία απόδοσης. Φανταστείτε μια εφαρμογή που χρησιμοποιεί ασύγχρονο παραλληλισμό δεδομένων. Η εφαρμογή εκτελείται στον Η/Υ, πρώτα με ένα επεξεργαστή, μετά με δύο επεξεργαστές, με 3 επεξεργαστές και ούτω καθεξής. Καθώς αυξάνεται ο αριθμός των επεξεργαστών που χρησιμοποιούνται, ο χρόνος εκτέλεσης μειώνεται όπως είναι αναμενόμενο. Από κάποιο σημείο και έπειτα, η προσθήκη ενός ακόμα επεξεργαστή προκαλεί ξαφνικά μια δραματική αύξηση του συνολικού χρόνου εκτέλεσης του προγράμματος. Συνεχίζοντας την προσθήκη επεξεργαστών μετά την ξαφνική αύξηση, ο χρόνος εκτέλεσης βαθμιαία θα μειωθεί και πάλι.

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

13. Φανταστείτε ένα ασύγχρονο, παράλληλο αλγόριθμο στον οποίο κάθε διεργασία μπορεί να προσπελάσει ένα ορισμένο, τοπικό τμήμα μιας βάσης δεδομένων δίχως να επικαλύπτονται εν μέρει ορισμένες διεργασίες. Για αυτό, κάθε μονάδα δεδομένων μπορεί να προσπελαθεί από μία το πολύ διεργασία κατά τη διάρκεια της εκτέλεσης του προγράμματος. Σε ένα τέτοιο αλγόριθμο δεν φαίνεται να υπάρχει η πιθανότητα να υπάρξει ανταγωνισμός πρόσβασης στην μνήμη αφού δεν επιτρέπεται σε πολλαπλές διεργασίες να προσπελάσουν την ίδια μονάδα δεδομένων. Ωστόσο, σε ορισμένα παράλληλα συστήματα, ένας τέτοιος αλγόριθμος μπορεί να προκαλέσει ανταγωνισμό πρόσβασης στη μνήμη. Εξηγείστε για ποιο λόγο συμβαίνει αυτό. Μπορεί ο ανταγωνισμός πρόσβασης στη μνήμη να συμβεί σε συστήματα βασισμένα σε δίαυλο; Μπορεί να συμβεί σε συστήματα διαμοιραζόμενης μνήμης με πολλαπλά τμήματα μνήμης;

ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ

6. Οι βασικότεροι λόγοι της διάδοσης της λειτουργίας ανάγνωσης είναι ότι η κρυφή μνήμη που θέλει το αντίγραφο από την κύρια μνήμη, πρέπει να το πάρει στην τελευταία του μορφή, δηλαδή πρέπει η κρυφή μνήμη του συκεκριμένου επεξεργαστή, να δει αν αυτό έχει τροποποιηθεί μσε μια άλλη κρυφή μνήμη. Έτσι η κρυφή μνήμη που θέλει το αντίγραφο (ανάγνωση) στέλνει σήμα στο δίαυλο για ανάγνωση, γιασ να πάρει το τροποποιημένο αντίγραφο από τη κρυφή μνήμη που είχε το tag bit της ίσο με 1.

7. α. Οι παρακείμενες διευθύνσεις μνήμης πρέπει να διασκορπιστούν με μια σειρά μέσα στα τμήματα. Αληθής ισχυρισμός εφόσον στην περίπτωση της διαμοιραζόμενης μνήμης σε πολλαπλά τμήματα (modules) ο κάθε επεξεργαστής έχει το δικό του χωρίς να προσπελαύνει άλλα. Έτσι δεν υπάρχει περίπτωση ανταγωνισμού δύο ή περισσοτέρων επεξεργαστών για μια θέση μνήμης.

β.Κάθε επεξεργαστής προσπελαύνει σειριακά τις διαδοχικές διευθύνσεις μνήμης. Στην περίπτωση των memory modules, όπου τα δεδομένα είναι διαμοιραζόμενα, ο κάθε επεξεργαστής προσπελαύνει σειριακά το δικό του memory module. Έτσι ικανοποιούνται και η ανάγκη του επεξεργαστή για σειριακή προσπέλαση και της μνήμης για επεξεργασία. Δεν χρειάζεται σηλαδή ένας επεξεργαστής να προσπελάσει διαφορετικές θέσεις μνήμης, για να εκτελέσει το παράλληλο πρόγραμμα.

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

δ. Οι επεξεργαστές πρέπει να προσπελαύνουν τη μνήμη με την ίδια συχνότητα. Αν π.χ. έχουμε οκτώ memory modules και τέσσερις επεξεργαστές από τους οποίους οι δύο με χαμηλότερη συχνότητα, τότε θα έχουμε καθυστέρηση σ'αυτούς τους δύο με χαμηλότερη συχνότητα με αποτέλεσμα οι γρήγοροι να τους φτάνουν και να ανταγωνίζονται μ'αυτους στην πρόσβαση των memory modules. Πρέπει όλοι να έχουν την ίδια συχνότητα και να τελειώνουν στην ίδιο χρόνο για να μην υπάρχει σύγκρουση στις αιτήσεις εγγραφής και ανάγνωσης.