The Combinatorics of Cache Misses During Matrix Multiplication
Abstract
In this paper we construct an analytic model of cache misses during matrix multiplication. The analysis in this paper applies to square matrices of size 2m where the array layout function is given in terms of a function that interleaves the bits in the binary expansions of the row and column indices. We first analyze the number of cache misses for direct-mapped caches and then indicate how to extend this analysis to A-way associative caches. 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 array layout function.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 16, 2000
- Accession Number
- ADA448806
Entities
People
- Alivn R. Lebeck
- Daniel Genius
- Dean Chung
- Erin Parker
- Philip J. Hanlon
- Siddhartha Chatterjee
Organizations
- University of Michigan