A Fast and Accurate Approach to Analyze Cache Memory Behavior
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.
Place: Information technology, Uppsala University
Room 1510 is in Building 1, Floor 5, room 10
(in the southern part of the building).
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.
Updated 10-Nov-2000 08:59 by Roland Grönroos
e-mail: info -at- astec.uu.se