Controlling Cache Pollution in Prefetching With Software-assisted Cache Replacement

Abstract

Aggressive prefetch methods can suffer from cache pollution when prefetched data replaces useful data in the cache, causing performance degradation. In this paper, we present a methodology that ensures that cache pollution does not degrade overall performance when software or hardware prefetching methods are used. Software instructions can allow a program to kill a particular cache element, i.e., effectively make the element the least recently used element. We provide conditions under which kill instructions can be inserted into program code, such that the resulting performance is guaranteed to be as good as or better than the original program run using the standard LRU policy. Using these results, it is possible to analyze code and determine when to perform software-assisted replacement, i.e., when to insert a kill instruction. The result of this analysis is a modified cache replacement method that may be used independently to improve cache performance, or may be used to control cache pollution caused by arbitrary prefetching methods. A prefetching method can be combined with this modified cache replacement method in different ways, by distinguishing normal data from prefetched data. Different ways of combining prefetching with replacement have different associated performance guarantees. We consider aggressive, sequential prefetching methods which prefetch multiple cache blocks on a cache miss. These methods are easy to implement in hardware, but may cause significant cache pollution, and/or require increased bandwidth into the cache, which may result in worse performance than not prefetching at all. We show that both bandwidth and pollution can be controlled effectively using our software-assisted replacement algorithm. Empirical evidence is provided that shows that cache performance can be significantly improved, and minimumperformance guarantees provided, using a combination of simple, aggressive hardware prefetching and softwarecontrolled replacement.