A multiple queue replacement exploiting frequency for low level caches

Cache replacements play a vital role in cache misses and miss penalty reductions. We illustrate Cache replacements including Least Recently Used (LRU), Least Frequently Used (LFU), and combinations of both, by discussing how these replacements were used to exploit the recency and frequency information. We compare a series of studies by which we and other researchers have proposed the effectiveness of these replacements. This dissertation discusses the results from these earlier studies, proposes a Frequency based Multiple Queue (FMQ) replacement that is designed to improve potential performance to our Frequency based Single Queue (FSQ) replacement, and, in the process, sheds some light on those unsolved problems of the FSQ replacement from our earlier studies. The FMQ exploits frequency for low level caches (LLC) with low hardware overhead and minimum design changes. Cache lines in each cache set are arranged in multiple queues for replacement decisions. An incoming line randomly enters one of the queues from the bottom instead of placing the incoming line at the top of the queue. On a cache miss, one queue is randomly selected from the multiple queues and the victim line is chosen from either the bottom or the top of the queue. On a cache hit, the hit cache line exchanges its position with the cache line above in the queue, and moves its way to the top of the queue. The frequency information is stored through the location of the cache lines in the queue. On average, the FMQ achieves a 12% Miss Per Kilo-Instruction (MPKI) reduction over a conventional 1MB 16-way unified L2 cache. FMQ simplifies the circuit design compared to the traditional LRU. The storage requirement for the FMQ is reduced to 48%.