Reverse engineering of cache replacement policies in Intel microprocessors and their evaluation

Performance modeling techniques need accurate cache models to produce useful estimates. However, properties required for building such models, like the replacement policy, are often not documented. In this paper, using a set of carefully designed microbenchmarks, we reverse engineer a precise model of caches found in recent Intel processors that enables accurate prediction of their cache performance by simulation. In particular, we identify two variants of pseudo-LRU that, unlike previously documented policies, employ randomization. We evaluate their performance and demonstrate that it differs significantly from known pseudo-LRU variants on some benchmarks.