Reducing non-optimal LRU decision frequency in chip multiprocessors

Least recently used (LRU) is a widely used replacement policy as it offers simplicity and relatively acceptable performance. However, there is a considerable performance gap between LRU and Belady´s theoretical optimal replacement policy in highly associative caches. We study non-optimal LRU decisions (NODs) in chip multiprocessors and investigate NOD distribution within multithreaded applications. We introduce hasty blocks (H-blocks) and predictable blocks (P-blocks) as more inclusive extensions of previously suggested classifications. Based on our findings we present speculative replacement algorithm (SRA) to identify and reduce NOD frequency. We discuss implementation issues and show that with a small 1k entries table we could successfully identify about 90% of H-blocks and half of the P-Blocks. When SRA algorithm is combined with previously suggested techniques it reduces an extra 7% of the cache miss rate on average.