Estimating Cache Misses and Locality Using Stack Distances

Calin Caşcaval, David A. Padua

Research output: Contribution to conferencePaperpeer-review


Cache behavior modeling is an important part of modern optimizing compilers. In this paper we present a method to estimate the number of cache misses, at compile time, using a machine independent model based on stack algorithms. Our algorithm computes the stack histograms symbolically, using data dependence distance vectors and is totally accurate when dependence distances are uniformly generated. The stack histogram models accurately fully associative caches with LRU replacement policy, and provides a very good approximation for set-associative caches and programs with non-constant dependence distances. The stack histogram is an accurate, machine-independent metric of locality. Compilers using this metric can evaluate optimizations with respect to memory behavior. We illustrate this use of the stack histogram by comparing three locality enhancing transformations: tiling, data shackling and the product-space transformation. Additionally, the stack histogram model can be used to compute optimal parameters for data locality transformations, such as the tile size for loop tiling.

Original languageEnglish (US)
Number of pages10
StatePublished - 2003
Event2003 International Conference on Supercomputing - San Francisco, CA, United States
Duration: Jun 23 2003Jun 26 2003


Other2003 International Conference on Supercomputing
Country/TerritoryUnited States
CitySan Francisco, CA


  • Cache modeling
  • Compiler algorithms
  • Stack algorithms

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Estimating Cache Misses and Locality Using Stack Distances'. Together they form a unique fingerprint.

Cite this