Speeding up single pass simulation of PLRUt caches

CPU caches have become an essential component in many computer systems as they can significantly increase system performance by alleviating the effects of memory latency. For many designers part of the system design flow is the selection of an appropriately configured cache, a task which can be performed using cache simulators. Exploring the entire design space through precise cache simulation is a lengthy process, and while certain cache replacement policies have been optimised for fast simulation execution (such as LRU and FIFO), no effective optimisations have been proposed for an extremely effective replacement policy: Pseudo Least Recently Used tree-based, also known as PLRUt. In this paper we are the first to present a number of characteristics of the PLRUt replacement policy that lend themselves to the design of an optimised hash table-based cache simulator. We demonstrate that our optimised simulator is up to 1.93x faster than an un-optimised implementation.