Cache miss equations: an analytical representation of cache misses

Research output: Chapter in Book/Report/Conference proceedingConference contribution

110 Scopus citations

Abstract

With the widening performance gap between processors and main memory, efficient memory accessing behavior is necessary for good program performance. Both hand-tuning and compiler optimization techniques are often used to transform codes to improve memory performance. Effective transformations require detailed knowledge about the frequency and causes of cache misses in the code. This paper describes methods for generating and solving Cache Miss equations that give a detailed representation of the cache misses in loop-oriented scientific code. Implemented within the SUIF compiler framework, our approach extends on traditional compiler reuse analysis to generate linear Diophantine equations that summarize each loop's memory behavior. Mathematical techniques for manipulating Diophantine equations allow us to compute the number of possible solutions, where each solution corresponds to a potential cache miss. These equations provide a general framework to guide code optimizations for improving cache performance. The paper gives examples of their use to determine array padding and offset amounts that minimize cache misses, and also to determine optimal blocking factors for tiled code. Overall, these equations represent an analysis framework that is more precise than traditional memory behavior heuristics, and is also potentially faster than simulation.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Supercomputing
PublisherACM
Pages317-324
Number of pages8
StatePublished - Jan 1 1997
EventProceedings of the 1997 International Conference on Supercomputing - Vienna, Austria
Duration: Jul 7 1997Jul 11 1997

Other

OtherProceedings of the 1997 International Conference on Supercomputing
CityVienna, Austria
Period7/7/977/11/97

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Cache miss equations: an analytical representation of cache misses'. Together they form a unique fingerprint.

  • Cite this

    Ghosh, S., Martonosi, M. R., & Malik, S. (1997). Cache miss equations: an analytical representation of cache misses. In Proceedings of the International Conference on Supercomputing (pp. 317-324). ACM.