Expected I-cache miss rates via the gap model
Author:
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 372-383
Abstract
To evaluate the performance of a memory system, computer architects must determine the miss rate m of a cache C when running program P. Typically, the measured miss rate depends on the specific address mapping M of P set arbitrarily by the compiler and linker. The author removes the effect of the address-mapping on the miss rate by analyzing a symbolic trace T of basic blocks. By assuming each basic block has an equal probability of ending up anywhere in the address map, he determines the expected miss rate averaged over all possible address mappings. The resulting gap model gives the expected miss rate for instruction caches of varying cache size, line size, and set associativity. The model is simple but robust, and turns out to be the familiar LRU stack model with a statistical viewpoint. The model allows a trace of arbitrary length to he compactly summarized in a few thousand bytes of information. It also predicts how an intervening trace, such as an operating system call or a task switch, will affect the miss rate. Comparisons to measured miss rates from SPEC 92 instruction traces show that the model typically has relative differences of less than 20% for a variety of cache parameters.Keywords
This publication has 10 references indexed in Scilit:
- The feasibility of using compression to increase memory system performance2002
- A model of workloads and its use in miss-rate prediction for fully associative cachesIEEE Transactions on Computers, 1992
- Synthetic traces for trace-driven simulation of cache memoriesIEEE Transactions on Computers, 1992
- Procedure merging with instruction caches1991
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- An analytical cache modelACM Transactions on Computer Systems, 1989
- A study of a C function inlinerSoftware: Practice and Experience, 1988
- Aspects of Cache Memory and Instruction Buffer Performance1987
- Cache MemoriesACM Computing Surveys, 1982
- Use of the LRU stack depth distribution for simulation of paging behaviorCommunications of the ACM, 1977