Cache Showdown: The Good, Bad, and Ugly

Bhavesh Mehta, Dana Vantrease, Luke Yen

Abstract: Prefetching algorithms have been mainly studied in the context of the Coverage and Accuracy metrics.  While this is an appropriate metric for prefetching into separate stream buffers, it is a poor assessment of prefetching into a shared cache structure where cache pollution can become a serious factor.  Traditionally, prefetches have been categorized as "good" or "bad" if they are accessed or are evicted without being accessed, respectively.  We propose a new categorization of "good", "bad", and "ugly" that takes into account prefetches that cause harmful cache pollution. This paper proposes a novel structure called the Evict Table (ET) that gauges the amount of cache pollution caused by prefetching into a shared data structure, such as a cache.  We show the value of the ET in the context of a chip-multiprocessors, where prefetching among several processing nodes may further increase the contention for cache real-estate. Specifically, we use the ET as an aid in evaluating the effects of Unistride and Czone prefetching algorithms on a chip-multiprocessor's shared L2 cache across a varying number of cache sizes.

Available as: Postscript or PDF