Estimating Cache Misses and Locality Using Stack Distances

Calin Caşcaval, David A. Padua

Research output: Contribution to conferencePaper

Abstract

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)
Pages150-159
Number of pages10
StatePublished - Dec 1 2003
Event2003 International Conference on Supercomputing - San Francisco, CA, United States
Duration: Jun 23 2003Jun 26 2003

Other

Other2003 International Conference on Supercomputing
CountryUnited States
CitySan Francisco, CA
Period6/23/036/26/03

Fingerprint

Tile
Data storage equipment

Keywords

  • Cache modeling
  • Compiler algorithms
  • Stack algorithms

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Caşcaval, C., & Padua, D. A. (2003). Estimating Cache Misses and Locality Using Stack Distances. 150-159. Paper presented at 2003 International Conference on Supercomputing, San Francisco, CA, United States.

Estimating Cache Misses and Locality Using Stack Distances. / Caşcaval, Calin; Padua, David A.

2003. 150-159 Paper presented at 2003 International Conference on Supercomputing, San Francisco, CA, United States.

Research output: Contribution to conferencePaper

Caşcaval, C & Padua, DA 2003, 'Estimating Cache Misses and Locality Using Stack Distances', Paper presented at 2003 International Conference on Supercomputing, San Francisco, CA, United States, 6/23/03 - 6/26/03 pp. 150-159.
Caşcaval C, Padua DA. Estimating Cache Misses and Locality Using Stack Distances. 2003. Paper presented at 2003 International Conference on Supercomputing, San Francisco, CA, United States.
Caşcaval, Calin ; Padua, David A. / Estimating Cache Misses and Locality Using Stack Distances. Paper presented at 2003 International Conference on Supercomputing, San Francisco, CA, United States.10 p.
@conference{9d203e512cdc4222a23e1c988a306289,
title = "Estimating Cache Misses and Locality Using Stack Distances",
abstract = "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.",
keywords = "Cache modeling, Compiler algorithms, Stack algorithms",
author = "Calin Caşcaval and Padua, {David A.}",
year = "2003",
month = "12",
day = "1",
language = "English (US)",
pages = "150--159",
note = "2003 International Conference on Supercomputing ; Conference date: 23-06-2003 Through 26-06-2003",

}

TY - CONF

T1 - Estimating Cache Misses and Locality Using Stack Distances

AU - Caşcaval, Calin

AU - Padua, David A.

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

KW - Cache modeling

KW - Compiler algorithms

KW - Stack algorithms

UR - http://www.scopus.com/inward/record.url?scp=1142268809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1142268809&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:1142268809

SP - 150

EP - 159

ER -