### 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 language | English (US) |
---|---|

Pages | 150-159 |

Number of pages | 10 |

State | Published - Dec 1 2003 |

Event | 2003 International Conference on Supercomputing - San Francisco, CA, United States Duration: Jun 23 2003 → Jun 26 2003 |

### Other

Other | 2003 International Conference on Supercomputing |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 6/23/03 → 6/26/03 |

### Fingerprint

### Keywords

- Cache modeling
- Compiler algorithms
- Stack algorithms

### ASJC Scopus subject areas

- Computer Science(all)

### Cite this

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

Research output: Contribution to conference › Paper

}

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 -