A Taxonomy for Cache Memory Misses
Resumo
One way to understand the causes of cache memory misses is to use a classification for them. Usually statistical models such as the 3C model are used to make the classification. In the present work a new definition for the 3C model: compulsory, capacity and conflict misses are given. The corresponding operational definitions are given, which are based on the use of the LRU stack distances. The proposed model is called a deterministic 3C model or D3C. The D3C model classifies the memory references in an individual way, conforming a taxonomy, and then it is possible to analyze when a memory reference belongs to a given category. Also the passage of a given memory reference from one category to another when some cache parameter is modified may be studied. The D3C model does not present anomalies such as negative conflict miss rales, as in the 3C model. Several patterns for memory access are theoretically analyzed for the 3C and D3C models, showing that the results given by the D3C model are intuitive and have easy interpretation. The 3C model underestimates the conftict misses and overestimates the capacity misses when compared with the D3C model. This difference comes from the references that hit in the cache under study and miss in a fully associative cache of the same size with LRU replacement policy. The amount of these references was measured using SPEC95 benchmarks in trace driven simulations. It is shown that high percent values are obtained for these references for usual cache configurations, and therefore these references have an important participation in the cache statistics.
Referências
HAMKALO. J. L.; CERNUSCHI-FRIAS. B. Theoretical Analysis of Cache Statistics for the Simple Loop Model. International Journal of Computers & Applications. v.21. n. 1. p.13-18. 1999.
Hill. M. D.; SMITH, A. J. Evaluating Associativity in CPU Caches. IEEE Trans. on Computer. C-38, n.12. p.1612-1630, 1995.
LEBECK. A. R.; WOOD. D. A. Cache Profiling and the SPEC Benchmarks a Case Study. IEEE Computer, v.27, n. 10, p. 15- 26, 1994.
PATTERSON, D. A.; HENNESSY, J. L. Computer Architecture a Quantitative Approach, San Mateo, California: Morgan Kaufmann Publishers, 1995.
SMITH. A. J. Cache Memories. ACM Computing Surveys, v. 14, n.3. p.473-530, 1982.
SMITH, J. E.; GOODMAN. J. R. Instruction Cache Replacement Policies and Organizations. IEEE Trans. on Computer, C-34, n.3. p.234-241. 1985.
SRIVASTAVA, A.; EUSTACE. A. ATOM: A System for Building Customized Program Analysis Tools. In : ACM CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION, 1994. Proceedings... p.196-205. 1994.
SUGUMAR, R. A.; SANTOSH. G. A. Efficient Simulation of Caches under Optimal Replacement with Applications to Miss Characterization. In: ACM SIGMETRICS. 1993. Proceedings... p.24-35, 1993.
