Multi-Lateral Cache Scheduling

Graduate

The limiting factor today in processor performance is the gap between processor speed and memory access speed; this is the memory latency problem. A common approach for coping with memory latency is to use a set-associative cache, a small, high speed memory located between main memory and the processor. However, the gap between processor performance and memory performance is expected to continue growing at an exponential rate and better designed caches with improved performance are needed to ensure that increases in processor speed result in corresponding increases in processor performance. A promising class of cache designs is the multi-lateral cache. A multi-lateral cache consists of two or more caches structures which are accessed in parallel. A given item might be in any of those structures. This class includes skew caches and victim caches. Cache performance is highly dependent on how memory items are placed in the cache. The cache scheduling algorithm determines which items to keep in the cache and where to place items in the cache. For traditional caches, cache scheduling is an easy and well studied problem. Multi-lateral cache scheduling is a much more difficult problem. We have shown that the offline version of this problem is NP-complete even for the simplest multi-lateral cache. The problem is also APX-complete, which means it belongs to a class of "hard" to approximate problems. We have also shown that for the online version, the commonly used Least Recently Used scheduling algorithm is not competitive for multi-lateral caches.

Return to Workshop Listing