Cache Showdown: The Good, Bad, and Ugly
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