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. 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