A Stall-Oriented Approach to Cache Replacement

Abstract

Memory accesses have increasingly become the bottleneck of processor performance in recent years, and cache replacement algorithms are an essential part of reducing this strain. While there exists extensive literature on cache replacement algorithms that seek to minimize the total number of cache misses as a way to improve overall processor performance, there is considerably less research that seeks to improve processor performance in an alternative way that may result in an increase of total misses. The latter method is known as cost-aware, and is made possible by exploiting the fact that not all cache misses hurt the processor’s performance equally in modern out-of-order architectures. This paper presents a cost-aware cache replacement algorithm that emphasizes simplicity, and shows significant performance gains without the use of significant additional hardware, complex computation or prefetcher coordination. Furthermore, this technique, while relegated to the L1 instruction and data caches for this paper, can be generalized to other caches, as will be discussed in the future work section.