Skip to main content

Systems with predictable caching

It is difficult to predict cache performance because programs (except for trivial ones) are typically composed of various interwoven activities. Each of these activities leaves its footprint in the cache, thereby destroying data that was potentially needed by other parts of the program.

What makes prediction even more difficult is that various `gadgets' have been introduced that reduce interference between activities. Early on, set-associative caches were defined, followed by victim caches, skewed-associative caches (using different hash functions for different cache banks allowing a greater flexibility to place data), and column associative caches (sequentially applying different hash functions in the same bank). Interference is reduced at the cost of decreasing predictability.

Various compiler techniques have been developed to reduce interference. These techniques all use a conventional language as a starting point, and can improve certain patterns in the code. They do not structurally solve the problem. More promising approaches are Software Based Partitioning, and the application of compiler directed mappings.

None of these techniques comes to the heart of the matter. The traditional approach to ``system design'' is flawed, because it allows a programmer to make a monolithic block of statements. We propose taking a different approach to system design, in which the components must be identified and specified with composability as a target. That is, when compiled, components of the system have performance characteristics that can be combined using straightforward composition laws.

The approach that we propose is based on the CSP/Occam style of programming. When specified as a set of independent activities, a compiler will generate code and build a performance model of its caching activity. In addition to conventional techniques such as software based partitioning, we will use hardware based partitioning, in order to allow complete independence of activities, and simple composability. http://www.cs.bris.ac.uk/Research/LanguagesArchitecture/Predictable/

Staff and Students

James Irwin, Henk Muller, David May, Roger Shepherd (ST), Jeremy Gunawardena (HP)
Dan Page.

Publications

Support

Supported by EPSRC Grant GR/L78970.

Collaborators

SGS-Thomson Microelectronics, Hewlett-Packard Laboratories Europe.