The Problem of Cache Pollution

In the context of prefetching, cache pollution is said to occur when prefetched data replaces more useful data (demand-paged or prefetched) from the cache. There have been attempts to reduce cache pollution by restricting the amount of cache the prefetched data can occupy [34], or via software hints [35]. The SARC algorithm [17] provides an adaptive and autonomous solution to limit this problem by allocating cache space so as to equalize the marginal utility of the demand paged and prefetched data. However, we are not aware of any prior online solution for minimizing cache pollution that occurs when new prefetched data replaces more useful prefetched data from the cache.