SIP: Speculative Insertion Policy for High Performance Caching

Abstract

High performance cache mechanisms have a great impact on overall performance of computer systems by reducing memory-access latency. Least-Recently Used (LRU) mecha- nism can achieve good performance in small workload; how- ever, it suffers from thrashing caused by memory-intensive application. To address this challenge, dynamic insertion policy-DIP, which dynamically switches between LRU and an alternative policy, has recently been proposed. The algo- rithm, however, applies either one of the two policies to the entire cache based on the total number of misses. Therefore, such algorithm is not flexible enough to adjust to the differ- ent memory access pattern of each set. In this paper, we propose a novel approach, called SIP (Speculative Insertion Policy), to achieve high-performance caching via workload speculation mechanism. By utilizing memory-access direction and cache misses/hits , SIP esti- mates the size of per-set workload and dynamically selects an optimized policy for each set, leading to significant im- provement in cache performance with only 13Kbits addi- tional storage requirement over LRU for 1MB cache.