Abstract
The gap between processors and main memory performance increases every year. In order to overcome this problem, cache memories are very useful, although there are some programs that dont take advantage of them. In order to improve the cache performance, compile-time program transformations are very useful. To apply most of these transformations, the compiler requires a precise knowledge of the locality of the different sections of the code, both before and after being transformed.

Cache Miss Equations (CMEs) allow us to obtain an analytical and precise description of the cache memory behavior for loop-oriented codes. Describing the cache behavior by means of diophantine equations allow to use mathematical techniques to obtain cache misses.

Unfortunately, a direct solution of the CMEs is computationally intractable due to its NP-hard nature. In this work, we propose a fast and accurate approach to estimate the solution of the CMEs, which is based on the use of sampling techniques. Statistical techniques allow us to approximate the absolute miss ratio of each reference by analyzing a small subset of the iteration space. The size of the subset, and therefore the analysis time, is determined by the accuracy selected by the user.

In order to reduce the complexity of the algorithm to solve CMEs, effective techniques have been developed to analyze the subset of the iteration space that is being considered. These techniques exploit some properties of the particular polyhedra represented by CMEs.

ASTEC seminar
November 21, 2000, 13:15

Place: Information technology, Uppsala University
Room: 1510
Time: 13.15

Help on how get here and MIC campus drawing.

There will be an extended period for discussions after the seminar.

Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 15.00.