Probabilistic Directed Writebacks for Exclusive Caches

Abstract

Energy is an increasingly important consideration in memory system design. Although caches can save energy in several ways, such as by decreasing execution time and reducing the number of main memory accesses, they also suffer from known inefficiencies: the last-level cache (LLC) tends to have a high miss ratio while simultaneously storing many blocks that are never referenced after being written back to LLC. These blocks contribute to dynamic energy while simultaneously causing cache pollution. Because these blocks are not referenced before they are evicted, we can write them directly to memory rather than to the LLC. To do so, we must predict which blocks will not be referenced. Previous approaches rely on additional state at the LLC and/or extra communication. We show that by predicting working set size per program counter (PC), we can decide which blocks have low probability of being referenced. Our approach makes the prediction based solely on the address stream as seen by the level-one data cache (L1D) and thus avoids storing or communicating PC values between levels of the cache hierarchy. We require no modifications to the LLC. We adapt Flajolet and Martin?s probabilistic counting to keep the state small: two additional bits per L1D block, with an additional 6KB prediction table. This approach yields a large reduction in number of LLC writebacks: 25% fewer for SPEC on average, 80% fewer for graph500, and 67% fewer for an in-memory hash table.