Abstract of Phil Hanlon paper

In this paper we construct an analytic model of cache misses during matrix multiply. The analysis in this paper applies to matrices of size $2^m$ where the memory mapping function is given in terms of a function $\Theta$ which interleaves the bits in the binary expansions of the row and column indices. We first analyze the number of cache misses for direct mapped cache and then indicate how to extend this analysis to $L$-way associate cache. The work in this paper accomplishes two things. First, we construct fast algorithms to estimate the number of cache misses. Second, we develop theoretical understanding of cache misses that will allow us, in subsequent work, to approach the problem of minimizing cache misses by appropriately choosing the bit interleaving function that goes into the memory mapping function.