Expected I-cache miss rates via the gap model

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. In this paper, we remove 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, we determine the expected miss rate averaged over all possible address mappings.Our resulting gap model gives the expected miss rate for instruction caches of varying cache size, line size, and set associativity. Our model is simple but robust, and turns out to be the familiar LRU stack model with a statistical viewpoint. Our model allows a trace of arbitrary length to be compactly summarized in a few thousand bytes of information. Our model 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 our model typically has relative differences of less than 20% for a variety of cache parameters.