Skip to Main content Skip to Navigation
Conference papers

An Efficient Simulation Algorithm for Cache of Random Replacement Policy

Abstract : Cache is employed to exploit the phenomena of locality in many modern computer systems. One way of evaluating the impact of cache is to run a simulator on traces collected from realistic work load. However, for an important category of cache, namely those of random replacement policy, each round of the naïve simulation can only give one out of many possible results, therefore requiring many rounds of simulation to capture the cache behavior, like determining the hit probability of a particular cache reference. In this paper, we present an algorithm that efficiently approximates the hit probability in linear time with moderate space in a single round. Our algorithm is applicable to realistic processor cache parameters where the associativity is typically low, and extends to cache of large associativity. Experiments show that in one round, our algorithm collects information that would previously require up to dozens of rounds of simulation.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, August 11, 2014 - 9:06:22 AM
Last modification on : Friday, August 11, 2017 - 5:44:06 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 9:40:14 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Shuchang Zhou. An Efficient Simulation Algorithm for Cache of Random Replacement Policy. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. pp.144-154, ⟨10.1007/978-3-642-15672-4_13⟩. ⟨hal-01054982⟩



Record views


Files downloads