Editing Cache replacement policies (section)

=== {{anchor|Cache replacement policies approximating Bélády's algorithm}}Policies approximating Bélády's algorithm ===
Bélády's algorithm is the optimal cache replacement policy, but it requires knowledge of the future to evict lines that will be reused farthest in the future. A number of replacement policies have been proposed which attempt to predict future reuse distances from past access patterns,<ref>{{Cite book |last1=Keramidas |first1=Georgios |last2=Petoumenos |first2=Pavlos |last3=Kaxiras |first3=Stefanos |title=2007 25th International Conference on Computer Design |chapter=Cache replacement based on reuse-distance prediction |date=2007 |pages=245–250 |doi=10.1109/ICCD.2007.4601909 |isbn=978-1-4244-1257-0 |s2cid=14260179 |chapter-url=https://doi.org/10.1109/ICCD.2007.4601909}}</ref> allowing them to approximate the optimal replacement policy. Some of the best-performing cache replacement policies attempt to imitate Bélády's algorithm.

==== Hawkeye ====
Hawkeye<ref name=":1" /> attempts to emulate Bélády's algorithm by using past accesses by a PC to predict whether the accesses it produces generate cache-friendly (used later) or cache-averse accesses (not used later). It samples a number of non-aligned cache sets, uses a history of length <math>8 \times \text{the cache size}</math> and emulates Bélády's algorithm on these accesses. This allows the policy to determine which lines should have been cached and which should not, predicting whether an instruction is cache-friendly or cache-averse. This data is then fed into an RRIP; accesses from cache-friendly instructions have a lower RRPV value (likely to be evicted later), and accesses from cache-averse instructions have a higher RRPV value (likely to be evicted sooner). The RRIP backend makes the eviction decisions. The sampled cache and [[Page replacement algorithm#The theoretically optimal page replacement algorithm|OPT]] generator set the initial RRPV value of the inserted cache lines. Hawkeye won the CRC2 cache championship in 2017,<ref>{{Cite web |title=THE 2ND CACHE REPLACEMENT CHAMPIONSHIP – Co-located with ISCA June 2017 |url=https://crc2.ece.tamu.edu/ |access-date=2022-03-24 |website=crc2.ece.tamu.edu}}</ref> and Harmony<ref>{{Cite book |last1=Jain |first1=Akanksha |last2=Lin |first2=Calvin |title=2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA) |chapter=Rethinking Belady's Algorithm to Accommodate Prefetching |date=June 2018 |chapter-url=https://ieeexplore.ieee.org/document/8416822 |pages=110–123 |doi=10.1109/ISCA.2018.00020|isbn=978-1-5386-5984-7 |s2cid=5079813 }}</ref> is an extension of Hawkeye which improves prefetching performance.
[[File:Mockingjay Description.svg|thumb|alt=See caption|Block diagram of the Mockingjay cache replacement policy]]

==== Mockingjay ====
Mockingjay<ref>{{Cite journal |last1=Shah |first1=Ishan |last2=Jain |first2=Akanksha |last3=Lin |first3=Calvin |date=April 2022 |title=Effective Mimicry of Belady's MIN Policy |journal=HPCA}}</ref> tries to improve on Hawkeye in several ways. It drops the binary prediction, allowing it to make more fine-grained decisions about which cache lines to evict, and leaves the decision about which cache line to evict for when more information is available.

Mockingjay keeps a sampled cache of unique accesses, the PCs that produced them, and their timestamps. When a line in the sampled cache is accessed again, the time difference will be sent to the reuse distance predictor. The RDP uses temporal difference learning,<ref>{{Cite journal |last=Sutton |first=Richard S. |date=1988-08-01 |title=Learning to predict by the methods of temporal differences |journal=Machine Learning |language=en |volume=3 |issue=1 |pages=9–44 |doi=10.1007/BF00115009 |s2cid=207771194 |issn=1573-0565|doi-access=free }}</ref> where the new RDP value will be increased or decreased by a small number to compensate for outliers; the number is calculated as <math>w = \min\left(1, \frac{\text{timestamp difference}}{16}\right)</math>. If the value has not been initialized, the observed reuse distance is inserted directly. If the sampled cache is full and a line needs to be discarded, the RDP is instructed that the PC that last accessed it produces streaming accesses.

On an access or insertion, the estimated time of reuse (ETR) for this line is updated to reflect the predicted reuse distance. On a cache miss, the line with the highest ETR value is evicted. Mockingjay has results which are close to the optimal Bélády's algorithm.