The last-level cache (LLC) is the last chance for memory accesses from the processor to avoid the costly latency of accessing the main memory.In recent years, an increasing number of instruction heavy workloads have put pressure on the last-level cache.We find that, for instruction heavy workloads, a simple replacement policy with minimal overhead provides at least the same benefit as a stateof-the-art, high-overhead replacement policy in the presence of aggressive prefetching.Our proposal is based on specifying insertion and promotion vectors (IPVs) as a generalization of re-reference interval prediction (RRIP) in such a way that the space of feasible policies may be searched exhaustively to find the best policy for the training set of workloads.The policies are formulated to deliver the best performance taking into account demand and prefetch accesses.We show that our technique, Prefetch Aware Coarse-grained Insertion and Promotion Vectors (PACIPV), improves performance over a state-of-the-art LLC replacement policy (Mockingjay) for instruction heavy workloads, and remains competitive for data heavy workloads with significantly less hardware overhead.We show that RRIP-based IPVs are very easy to implement but outperform far more complex replacement policies.PACIPV achieves a speedup of 3.3% over the baseline of LRU, outperforming SRRIP by 1.1% and the much more hardware intensive Mockingjay by 0.1%.

Hardware prefetching is an effective technique for hiding cache miss latencies in modern processor designs. Prefetcher performance can be characterized by two main metrics that are generally at odds with one another: coverage, the fraction of baseline cache misses which the prefetcher brings into the cache; and accuracy, the fraction of prefetches which are ultimately used. An overly aggressive prefetcher may improve coverage at the cost of reduced accuracy. Thus, performance may be harmed by this over-aggressiveness because many resources are wasted, including cache capacity and bandwidth. An ideal prefetcher would have both high coverage and accuracy.

Applications continue to increase their capacity requirements. Die-stacked DRAM caches have been proposed as a solution to filter as many accesses as possible to main memory. DRAM caches have been predominantly studied in the scenario where the next level of memory is off-chip DRAM. With similar access times for both of these levels of the memory hierarchy, the focus has been optimizing access latency, rather than increasing the hit rate. Emerging non-volatile memory (NVM) technologies are proposed as an affordable solution to replace DRAM. These technologies come with a significantly higher access latency than an already slow DRAM. Thus, architects must reconsider design choices for DRAM caches. It is no longer reasonable to compromise on hit rate, and it is still necessary to mitigate access latency. In this work, we revisit the idea of associativity for DRAM caches. We propose Flexible Associativity (FlexA), a low-cost technique that allows the DRAM cache to behave as a low-access latency direct-mapped design for most accesses, but provides associativity when needed to optimize hit rate. We evaluate (FlexA) on a wide variety of workloads as well as in the presence of different main memory latencies. FlexA achieves an average speedup of 13% compare to the state-of-the-art work.

Data prefetching and cache replacement algorithms have been intensively studied in the design of high performance microprocessors. Typically, the data prefetcher operates in the private caches and does not interact with the replacement policy in the shared Last-Level Cache (LLC). Similarly, most replacement policies do not consider demand and prefetch requests as different types of requests. In particular, program counter (PC)-based replacement policies cannot learn from prefetch requests since the data prefetcher does not generate a PC value. PC-based policies can also be negatively affected by compiler optimizations. In this paper, we propose a holistic cache management technique called Kill-the-PC (KPC) that overcomes the weaknesses of traditional prefetching and replacement policy algorithms. KPC cache management has three novel contributions. First, a prefetcher which approximates the future use distance of prefetch requests based on its prediction confidence. Second, a simple replacement policy provides similar or better performance than current state-of-the-art PC-based prediction using global hysteresis. Third, KPC integrates prefetching and replacement policy into a whole system which is greater than the sum of its parts. Information from the prefetcher is used to improve the performance of the replacement policy and vice-versa. Finally, KPC removes the need to propagate the PC through entire on-chip cache hierarchy while providing a holistic cache management approach with better performance than state-of-the-art PC-, and non-PC-based schemes. Our evaluation shows that KPC provides 8% better performance than the best combination of existing prefetcher and replacement policy for multi-core workloads.

The disparity between last-level cache and memory latencies motivates the search for efficient cache management policies. Recent work in predicting reuse of cache blocks enables optimizations that significantly improve cache performance and efficiency. However, the accuracy of the prediction mechanisms limits the scope of optimization.

Cache replacement policies often order blocks into distinct positions. A block is placed into a set in some initial position. A re-referenced block is promoted into a higher position while other blocks may move into lower positions. A block in the lowest position is a candidate for replacement. Tree-based PseudoLRU is a well-known space-efficient replacement policy based on representing block positions as distinct paths in a binary tree. We find that a placement or promotion for one block often needlessly disturbs the non-promoted blocks. Guided by the principle of minimal disturbance, i.e. that a policy should seek to disturb the order of non-promoted blocks to the smallest extent possible, we develop a simple modification to PseudoLRU resulting in a policy that improves performance over previous techniques while retaining the low cost of PseudoLRU. The result is a minimal disturbance placement and promotion (MDPP) policy. We first give a static formulation of MDPP and show that it provides superior performance to LRU, PseudoLRU and matches performance for SRRIP for both single-threaded and multi-core workloads. We then give a dynamic formulation that uses dead block prediction for placement and bypass and show that it meets or exceeds state-of-the-art performance with lower overhead. For single-threaded workloads, dynamic MDPP matches the 5.9% speedup over LRU of the state-of-the-art policy SHiP. For multi-core workloads, dynamic MDPP gives a normalized weighted speedup of 14.3% over LRU, compared with SHiP that yields a speedup of 12.3% over LRU and requires double the storage overhead per set. We show that minimal disturbance policies can reduce the frequency of a costly read-modify-write cycle for replacement state, making them potentially suitable for future work in DRAM caches.

The disparity between last-level cache and memory latencies motivates the search for efficient cache management policies. Recent work in predicting reuse of cache blocks enables optimizations that significantly improve cache performance and efficiency. However, the accuracy of the prediction mechanisms limits the scope of optimization. This paper proposes perceptron learning for reuse prediction. The proposed predictor greatly improves accuracy over previous work. For multi-programmed workloads, the average false positive rate of the proposed predictor is 3.2%, while sampling dead block prediction (SDBP) and signature-based hit prediction (SHiP) yield false positive rates above 7%. The improvement in accuracy translates directly into performance. For single-thread workloads and a 4MB last-level cache, reuse prediction with perceptron learning enables a replacement and bypass optimization to achieve a geometric mean speedup of 6.1%, compared with 3.8% for SHiP and 3.5% for SDBP on the SPEC CPU 2006 benchmarks. On a memory-intensive subset of SPEC, perceptron learning yields 18.3% speedup, versus 10.5% for SHiP and 7.7% for SDBP. For multi-programmed workloads and a 16MB cache, the proposed technique doubles the efficiency of the cache over LRU and yields a geometric mean normalized weighted speedup of 7.4%, compared with 4.4% for SHiP and 4.2% for SDBP.