The combinatorics of cache misses during matrix multiplication

Journal Article (Journal Article)

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

Full Text

Duke Authors

Cited Authors

  • Hanlon, PJ; Chung, D; Chatterjee, S; Genius, D; Lebeck, AR; Parker, E

Published Date

  • January 1, 2001

Published In

Volume / Issue

  • 63 / 1

Start / End Page

  • 80 - 126

International Standard Serial Number (ISSN)

  • 0022-0000

Digital Object Identifier (DOI)

  • 10.1006/jcss.2001.1756

Citation Source

  • Scopus