Cache Content Duplication

Abstract

Η σημασία της κρυφής μνήμης και της ιεραρχίας μνήμης αυξήθηκε τα τελευταία χρόνια λόγο της μεγάλης διαφοράς στην επίδοση που υπάρχει μεταξύ των επεξεργαστών και της μνήμης, και έγινε ακόμα ποιο σημαντική λόγο των πολυνηματικών επεξεργαστών και τον πολυεπεξεργαστών. Για να καλύψουν αυτό το κενό οι κρυφές μνήμες έχουν γίνει το αντικείμενο πολλών ερευνητικών μελετών με στόχο να βελτιώσουν την επίδοση τους αλλά επίσης και την απόδοση τους στην ισχύ και στον χώρο που καταλαμβάνουν. Αυτή διατριβή αναγνωρίζει ένα νέο φαινόμενο στις κρυφές μνήμες το οποίο μας δίνει την δυνατότητα να βελτιώσουμε την επίδοση και την απόδοση τους και το ονομάζουμε Επανάληψη Περιεχομένου Κρυφής Μνήμης (CCD). Το CCD συμβαίνει όταν έχουμε μια αστοχία για ένα τμήμα δεδομένων σε μια κρυφή μνήμη και το περιεχόμενο αυτού του τμήματος υπάρχει ήδη σε κάποιο άλλο τμήμα δεδομένων που βρίσκεται εκείνη την ώρα στην κρυφή μνήμη. Οι κρυφές μνήμες που έχουν την δυνατότητα να αναγνωρίζουν το CCD μπορούν να έχουν μικρότερη ποινή χρόνου σε μια αστοχία φέρνοντας τα δεδομένα από την ίδια την κρυφή μνήμη αντί να γίνεται πρόσβαση σε κάποιο χαμηλότερο επίπεδο στην ιεραρχία μνήμης. Επίσης μπορούμε να έχουμε λιγότερες αστοχίες μνήμης αν αφήνουμε μόνο τα μοναδικά τμήματα δεδομένων να μπαίνουν στην κρυφή μνήμη. Η χρησιμότητα του CCD εξετάζεται σε όλα τα επίπεδα της ιεραρχίας μνήμης. Πρώτον, δείχνουμε ότι το CCD είναι συχνό φαινόμενο για τις κρυφές μνήμες εντολών και ότι ένας ιδανικός μηχανισμός ανίχνευσης του CCD έχει την δυνατότητα να αυξήσει την επίδοση ενός μοντέρνου επεξεργαστή με 16KB κρυφή μνήμη εντολών (8-way και 8 εντολές ανά τμήμα δεδομένων) συχνά περισσότερο από 10% και μέχρι και 36%. Επίσης προτείνουμε τον CATCH, ένα μηχανισμό υλικού για να αναγνωρίζει δυναμικά το CCD στις κρυφές μνήμες εντολών. Τα πειραματικά αποτελέσματα για έναν μοντέρνο επεξεργαστή έδειξαν ότι ο CATCH με 1.38ΚΒ κόστος μπορεί να καλύψει κατά μέσο όρο το 58% της επίδοσης του ιδανικού μηχανισμού. Δεύτερον, εξετάσαμε ακόμα μια περίπτωση του CCD την οποία αποκαλούμε Κλωνοποίηση Κώδικα. Η Κλωνοποίηση Κώδικα συμβαίνει όταν τρέχουμε πολλαπλά αντίγραφα του ίδιου εκτελέσιμου ή όταν τρέχουμε πολλαπλές οντότητες της ίδιας εφαρμογής. Τα αποτελέσματα δείχνουν ότι η Κλωνοποίηση Κώδικα μπορεί να μειώσει την επίδοση μιας εφαρμογής. Συγκεκριμένα αν έχουμε αντίγραφα του ίδιου εκτελέσιμου η επίδοση μπορεί να μειωθεί μέχρι και 11% σε υπάρχουσες πλατφόρμες. Επιπλέον δείχνουμε ότι ο CATCH μπορεί να βοηθήσει την επίδοση εξουδετερώνοντας την επανάληψη που προκύπτει από την Κλωνοποίησης Κώδικα. Τρίτον, ερευνούμε την δυνατότητα του CCD στις κρυφές μνήμες δεδομένων. Τα αποτελέσματα δείχνουν ότι οι κρυφές μνήμες δεδομένων έχουν πολλές ενημερώσεις στα τμήματα δεδομένων και έτσι κάνουν την ανίχνευση του CCD και την δημιουργία σταθερών συσχετίσεων μεταξύ δύο τμημάτων δεδομένων πολύ δύσκολη. Αν ένα τμήμα δεδομένων ενημερωθεί, τότε όλες οι σχέσεις επανάληψης με αυτό το τμήμα πρέπει να ακυρωθούν. Η ανάλυση μας έδειξε επίσης ότι υπάρχουν πολλά τμήματα με όλα τα δεδομένα τους μηδενικά και ήδη υπάρχουσες τεχνικές για αυτή την περίπτωση παρέχουν καλές λύσεις. Τέλος, αυτή η διατριβή εξετάζει το φαινόμενο του CCD στις κρυφές μνήμες τελευταίου επιπέδου (LLCs). Οι LLCs ενημερώνονται λιγότερο συχνά (η κρυφή μνήμη πρώτου επιπέδου δρα σαν φίλτρο) και έχουν λιγότερα μηδενικά επειδή περισσότερο αποθηκεύουν τμήματα δεδομένων που αντικαταστάθηκαν από τα ψηλότερα επίπεδα στην ιεραρχία μνήμες και ήδη ενημερώθηκαν με τιμές διάφορες του μηδέν. Τα αποτελέσματα υποδεικνύουν ότι το CCD είναι πολύ συχνό για διάφορα μεγέθη τμημάτων, από 4 μέχρι 64 bytes, και έχει την δυνατότητα να βελτιώσει την επίδοση ενός επεξεργαστή και να μειώσει την κατανάλωση ενέργειας του. Προτείνουμε ένα νέο σχεδιασμό κρυφής μνήμης, την Κρυφή Μνήμη με Αναγνώριση Επανάληψης Δεδομένων, για να ανιχνεύουμε και να εξουδετερώνουμε το CCD στις LLCs. Τα αποτελέσματα δείχνουν ότι η Κρυφή Μνήμη με Αναγνώριση Επανάληψης Δεδομένων μπορεί να δώσει μια μέτρια βελτίωση στην επίδοση αλλά μπορεί να μειώσει το γινόμενο της Ενέργειας με την Καθυστέρηση σημαντικά, 10% κατά μέσον όρον και μέχρι 15% στην καλύτερη περίπτωση, για τα πειράματα με πολλαπλές εφαρμογές.

The importance of caches and memory hierarchy has increased over time due to the growing gap between processor and memory performance, and it has become more important in Simultaneous Multithreading processors and Chip-multiprocessors. To cover this memory gap, caches have been the subject of numerous studies aiming to improve their performance as well as their power and area efficiency. This thesis identifies a new phenomenon in caches that has the potential to improve cache performance and efficiency: the Cache Content Duplication (CCD). CCD occurs when there is a miss for a block in a cache and the entire content of the missed block is already in the cache in a block with a different tag. Caches aware of content-duplication can have lower miss penalty by fetching, on a miss to a duplicate block, directly from the cache instead of accessing lower in the memory hierarchy, and can have lower miss rates by allowing only blocks with unique content to enter a cache. The usefulness of CCD is also examined at all levels of the memory hierarchy. First, we show that CCD is a frequent phenomenon for instruction caches and that an idealized duplication detection mechanism for instruction caches has the potential to increase performance of an out- of-order processor, with a 16KB, 8-way, 8 instructions per block instruction cache, often by more than 10% and up to 36%. We also propose CATCH, a hardware mechanism for dynamically detecting CCD for instruction caches. Experimental results for an out-of-order processor show that a duplication-detection mechanism with a 1.38KB cost captures on average 58% of the CCD’s idealized potential. Second, we examine another case of CCD which we call Text Cloning. Text Cloning can occur when running multiple copies of the same binary, Extrinsic Text Cloning, or when running multiple instances of the same application in a Virtually Indexed Virtually Tagged cache, Intrinsic Text Cloning. Results show that both Intrinsic Text Cloning and Extrinsic Text Cloning can reduce an application’s performance. Specifically, Extrinsic Text Cloning causes up to 11% slowdown on existing platforms. Furthermore, we show that CATCH can benefit performance by eliminating the duplication due to Intrinsic Text Cloning and Extrinsic Text Cloning. Third, we investigate the potential of CCD for L1 data caches. The results indicate that caches exhibit a high amount of dirty blocks thus making the CCD detection and creating stable correlations between different blocks very difficult. If a block is written, all duplicate relations to that block need to be invalidated. Our analysis also shows that zero runs are very frequent in L1 data caches and, therefore, previously proposed zero detection mechanisms can provide good solutions. Finally, this thesis considers the CCD phenomenon for Last Level Caches (LLCs). The LLCs are written less frequently (L1 data cache acts as a filter) and have less zero runs because they mostly store evicted cache blocks that have already written with non-zero values. Results indicate that CCD is very frequent for various block granularities, from 4 to 64 bytes, and has potential to improve processors performance or save energy. A new cache design, the Content Duplication Aware Cache, is proposed to detect and eliminate CCD in LLCs. The results indicate that the Content Duplication Aware Cache can improve performance moderately but can reduce Energy Delay product considerably, 10% on average and up to 15% at most, for multiprogram workloads.