3.2 Κρυφή Μνήμη

Επόμενο:3.3 Πολλαπλά Τμήματα Μνήμης Πάνω:Κεφάλαιο 3ο : Αρχιτεκτονική συστημάτων διαμοιραζόμενης μνήμης. Πίσω: 3.1 Συστήματα βασιζόμενα σε διαύλους

3.2 Κρυφή Μνήμη

3.2.1 Κρυφές Μνήμες με απλό Επεξεργαστή.

Στους απλούς επεξεργαστές, υπάρχει μια σημαντική τεχνική για την μείωση του ρυθμού πρόσβασης του επεξεργαστή στην μνήμη, που είναι η χρήση της κρυφής μνήμης. Η κρυφή μνήμη είναι ένα μικρό τμήμα μνήμης με υψηλή ταχύτητα που έχει απευθείας σύνδεση με τον επεξεργαστή. Οι συχνά χρησιμοποιούμενες τιμές δεδομένων αποθηκεύονται στην κρυφή μνήμη, απ’ όπου μπορούν να προσπελαστούν πολύ πιο γρήγορα απ’ ότι οι τιμές δεδομένων που αποθηκεύονται στην μεγαλύτερη αλλά πιο αργή κύρια μνήμη. Το μέγεθος της κύριας μνήμης στα τυπικά συστήματα υπολογιστών μετριέται σε megabytes, ενώ το μέγεθος της κρυφής μνήμης μετριέται σε kilobytes. Από τη στιγμή που η κρυφή μνήμη είναι πολύ μικρότερη, είναι δυνατόν για την κατασκευή της να χρησιμοποιηθεί ακριβή αλλά πιο γρήγορη τεχνολογία υλικού απ’ ότι για κατασκευή της κύριας μνήμης.

Η βασική αρχή πίσω από ένα αυτόνομο, ενιαίο σύστημα επεξεργαστή παρουσιάζεται στο Σχήμα 3.1. Κάθε καταχώρηση στην κρυφή μνήμη περιέχει ένα ζευγάρι διεύθυνση - δεδομένα. Η διεύθυνση αντιστοιχεί σε πραγματική διεύθυνση της κύριας μνήμης, και τα δεδομένα είναι τα περιεχόμενα του συγκεκριμένου κελιού της κύριας μνήμης. Για παράδειγμα, στο Σχήμα 3.1 η πρώτη καταχώρηση στην κρυφή μνήμη λέει ότι η διεύθυνση 1000 της κύριας μνήμης περιέχει την τιμή δεδομένων 75. Η δεύτερη καταχώρηση στην κρυφή μνήμη λέει ότι η διεύθυνση 3500 της κύριας μνήμης περιέχει την τιμή δεδομένων 2. Αυτές οι καταχωρήσεις στην κρυφή μνήμη, είναι αντίγραφα από μερικές θέσεις της κύριας μνήμης. Όταν ο επεξεργαστής προσπελαύνει την μνήμη, πρώτα ελέγχει τα περιεχόμενα της κρυφής μνήμης για να δει αν η τιμή είναι αποθηκευμένη εκεί. Αν είναι, η τιμή προσπελαύνεται με μεγάλη ταχύτητα από την κρυφή μνήμη, και έτσι εξασφαλίζεται η αναγκαιότητα η κύρια μνήμη να προσπελαύνεται πιο σπάνια. Από τη στιγμή που η κρυφή μνήμη είναι δομημένη σαν συσχετιστική, όλες οι καταχωρήσεις στην κρυφή μνήμη μπορούν να αναζητηθούν με μια μόνο ενέργεια με πολύ μεγάλη ταχύτητα. Όταν υπάρχει μια συγκεκριμένη αναφορά μνήμης από έναν επεξεργαστή στην κρυφή μνήμη αυτό ονομάζεται ευστοχία της κρυφής μνήμης. Αν η αναφορά μνήμης δεν βρίσκεται στην κρυφή μνήμη, και επομένως πρέπει να πάει στην κύρια μνήμη αυτό ονομάζεται αστοχία της κρυφής μνήμης. Η κρυφή μνήμη έχει ένα περιορισμό μεγέθους και δεν μπορεί να κρατάει αντίγραφα απ’ όλες τις θέσεις της κύριας μνήμης που χρησιμοποιούνται από το πρόγραμμα. Επομένως, μερικές αστοχίες μνήμης είναι αναπόφευκτες. Όμως μελέτες έχουν δείξει ότι τα προγράμματα υπολογιστών έχουν να επιδείξουν μια ιδιότητα που ονομάζεται τοπικότητα της πρόσβασης μνήμης. Αυτό σημαίνει ότι οι θέσεις μνήμης που προσπελάστηκαν στο άμεσο παρελθόν είναι και αυτές που είναι πιο πιθανό να προσπελαστούν στο άμεσο μέλλον.

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

ΣΧΗΜΑ 3.1 Η κρυφή μνήμη σε απλό επεξεργαστή

Η κρυφή μνήμη είναι πιο χρήσιμη για λειτουργίες ανάγνωσης απ’ ότι για λειτουργίες εγγραφής. Κάθε μονάδα δεδομένων στην κρυφή μνήμη είναι ένα αντίγραφο μιας θέσης μνήμης στην κύρια μνήμη. Όταν πραγματοποιείται μια λειτουργία εγγραφής σε μια τμήμα στην κρυφή μνήμη, τότε το γνήσιο αντίγραφο στην κύρια μνήμη δεν ενημερώνεται. Υπάρχουν δύο γενικές προσεγγίσεις που ασχολούνται με αυτό θέμα στον σχεδιασμό της κρυφής μνήμης. Σύμφωνα με την πρώτη προσέγγιση, όταν μια καινούργια τιμή γράφεται στην κύρια μνήμη τότε ταυτόχρονα γράφεται και στην κρυφή μνήμη. Αυτό ονομάζεται τεχνική απ’ ευθείας εγγραφής (write-through). Σύμφωνα με την δεύτερη προσέγγιση, η καινούργια τιμή γράφεται μόνο στην κρυφή μνήμη και το αντίγραφο στην κύρια μνήμη παραμένει προσωρινά ανημέρωτο. Όταν μια καταχώρηση στην κρυφή μνήμη τελικά αντικαθίστανται επειδή δεν χρησιμοποιείται, τότε το μη ενημερωμένο αντίγραφο της κύριας μνήμης ενημερώνεται. Αυτή η τεχνική ονομάζεται ανάστροφη εγγραφή (write-back). Με οποιαδήποτε τεχνική καταναλώνεται κάποιος χρόνος πρόσβασης στην μνήμη. Ευτυχώς, στα τυπικά προγράμματα υπολογιστών, μόνο 20 τοις εκατό από τις συνολικές προσβάσεις στην μνήμη είναι λειτουργίες εγγραφής και το 80 τοις εκατό είναι λειτουργίες ανάγνωσης.

Αυτή το απλό μοντέλο της λειτουργίας της κρυφής μνήμης είναι αρκετό για την κατανόηση της επίδρασης της στην απόδοση του προγράμματος. Περαιτέρω συζήτηση για τις λεπτομέρειες σχεδιασμού της κρυφής μνήμης είναι έξω από τους σκοπούς αυτού του βιβλίου. Για μια εξαιρετική εισαγωγική συζήτηση για την τεχνολογία σχεδιασμού της κρυφής μνήμης, ο αναγνώστης παραπέμπεται στον Stone[1987].

3.2.2 Κρυφές Μνήμες σε Συστήματα Διαμοιραζόμενης Μνήμης.

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

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

Ένα ενδιαφέρον θέμα για την κρυφή μνήμη στα συστήματα διαμοιραζόμενης μνήμης, είναι ότι αρκετά αντίγραφα από το ίδιο τμήμα της κύριας μνήμης μπορεί να εμφανίζονται σε διαφορετικές κρυφές μνήμες. Για παράδειγμα, υποθέστε ότι ο Επεξεργαστής 1 διαβάζει την διεύθυνση μνήμης 1000 από την διαμοιραζόμενη μνήμη. Στη συνέχεια δημιουργείται ένα αντίγραφο στην τοπική κρυφή μνήμη του Επεξεργαστή 1. Αν οι Επεξεργαστές 2 και 3 επίσης διαβάσουν την διεύθυνση μνήμης 1000 από την διαμοιραζόμενη μνήμη, τότε και οι δικές τους τοπικές κρυφές μνήμες θα αποκτήσουν επίσης ένα αντίγραφο. Έτσι, θα υπάρχουν τέσσερα διαφορετικά αντίγραφα από την ίδια θέση μνήμης (1000) της διαμοιραζόμενης μνήμης - ένα αντίγραφο στην ίδια την διαμοιραζόμενη μνήμη και τρία επιπρόσθετα αντίγραφα στους Επεξεργαστές 1, 2 και 3. Όσο οι προσπελάσεις στην διεύθυνση 1000 είναι λειτουργίες μόνο ανάγνωσης δεν δημιουργείται πρόβλημα από την ύπαρξη πολλαπλών αντιγράφων. Κάθε επεξεργαστής μπορεί να εξακολουθεί να εκτελεί λειτουργίες ανάγνωσης χρησιμοποιώντας το δικό του αντίγραφο στην τοπική κρυφή μνήμη, χωρίς να χρειάζεται να προσπελάσει την διαμοιραζόμενη μνήμη.

Όμως, αν κάποιος επεξεργαστής εκτελέσει μια λειτουργία εγγραφής στη θέση μνήμης 1000, τότε θα δημιουργηθεί πρόβλημα. Όλα τα αντίγραφα πρέπει να παραμείνουν ίδια. Δεν είναι αποδεκτό να αλλάξει ένα αντίγραφο, αν δεν αλλάξουν και τα υπόλοιπα. Από τη στιγμή που υπάρχουν πολλαπλά αντίγραφα του ίδιου τμήματοςμνήμης, αυτά πρέπει να παραμείνουν όλα ίδια. Αυτό το γενικό πρόβλημα χειρισμού πολλών αντιγράφων από το ίδιο τμήμα μνήμης καλείται πρόβλημα συνοχής της κρυφής μνήμης (cache coherence). Υπάρχουν πολλές λύσεις γι’ αυτό το πρόβλημα, οι οποίες έχουν υλοποιηθεί σε ποικίλα εμπορικά και πειραματικά συστήματα διαμοιραζόμενης μνήμης. Όλες όμως αυτές οι λύσεις συνεπάγονται επιπρόσθετο κόστος (υλικού και χρόνου) στο σύστημα και επομένως υποβαθμίζουν την απόδοση του.

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

ΣΧΗΜΑ 3.2 Κρυφή μνήμη σε σύστημα διαμοιραζόμενης μνήμης