Program execution speed critically depends on reducing cache misses, as cache misses are orders of magnitude slower than hits. To reduce cache misses, we focus on the problem of cache replacement: choosing which cache line to evict upon inserting a new line. This is challenging because it requires planning far ahead and currently there is no known practical solution. As a result, current replacement policies typically resort to heuristics designed for specific common access patterns, which fail…