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.
Type de document :
Communication dans un congrès
Chen Ding; Zhiyuan Shao; Ran Zheng. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. Springer, Lecture Notes in Computer Science, LNCS-6289, pp.144-154, 2010, Network and Parallel Computing. 〈10.1007/978-3-642-15672-4_13〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054982
Contributeur : Hal Ifip <>
Soumis le : lundi 11 août 2014 - 09:06:22
Dernière modification le : vendredi 11 août 2017 - 17:44:06
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 21:40:14

Fichier

rand_cache_sim4.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Shuchang Zhou. An Efficient Simulation Algorithm for Cache of Random Replacement Policy. Chen Ding; Zhiyuan Shao; Ran Zheng. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. Springer, Lecture Notes in Computer Science, LNCS-6289, pp.144-154, 2010, Network and Parallel Computing. 〈10.1007/978-3-642-15672-4_13〉. 〈hal-01054982〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

316