%0 Conference Proceedings
%T An Efficient Simulation Algorithm for Cache of Random Replacement Policy
%+ Key Laboratory of Computer System and Architecture, Institute of Computing Technology
%A Zhou, Shuchang
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B IFIP International Conference on Network and Parallel Computing (NPC)
%C Zhengzhou, China
%Y Chen Ding; Zhiyuan Shao; Ran Zheng
%I Springer
%3 Network and Parallel Computing
%V LNCS-6289
%P 144-154
%8 2010-09-13
%D 2010
%R 10.1007/978-3-642-15672-4_13
%K Simulation
%K Cache memories
%K Stochastic approximation
%Z Computer Science [cs]/Digital Libraries [cs.DL]Conference papers
%X 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.
%G English
%2 https://inria.hal.science/hal-01054982/document
%2 https://inria.hal.science/hal-01054982/file/rand_cache_sim4.pdf
%L hal-01054982
%U https://inria.hal.science/hal-01054982
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-LNCS-6289
%~ IFIP-NPC
%~ IFIP-2010