Editing Cache replacement policies (section)

=== RRIP-style policies ===
RRIP-style policies are the basis for other cache replacement policies, including Hawkeye.<ref name=":1">{{Cite book |last1=Jain |first1=Akanksha |last2=Lin |first2=Calvin |title=2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA) |chapter=Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement |date=June 2016 |chapter-url=https://ieeexplore.ieee.org/document/7551384 |pages=78–89 |doi=10.1109/ISCA.2016.17|isbn=978-1-4673-8947-1 }}</ref> 

==== Re-Reference Interval Prediction (RRIP) ====
RRIP<ref name=":0">{{Cite book |last1=Jaleel |first1=Aamer |last2=Theobald |first2=Kevin B. |last3=Steely |first3=Simon C. |last4=Emer |first4=Joel |title=Proceedings of the 37th annual international symposium on Computer architecture |chapter=High performance cache replacement using re-reference interval prediction (RRIP) |date=2010-06-19 |chapter-url=https://doi.org/10.1145/1815961.1815971 |series=ISCA '10 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=60–71 |doi=10.1145/1815961.1815971 |isbn=978-1-4503-0053-7|s2cid=856628 }}</ref> is a flexible policy, proposed by [[Intel]], which attempts to provide good scan resistance while allowing older cache lines that have not been reused to be evicted. All cache lines have a prediction value, the RRPV (re-reference prediction value), that should correlate with when the line is expected to be reused. The RRPV is usually high on insertion; if a line is not reused soon, it will be evicted to prevent scans (large amounts of data used only once) from filling the cache. When a cache line is reused the RRPV is set to zero, indicating that the line has been reused once and is likely to be reused again.

On a cache miss, the line with an RRPV equal to the maximum possible RRPV is evicted; with 3-bit values, a line with an RRPV of 2<sup>3</sup> - 1 = 7 is evicted. If no lines have this value, all RRPVs in the set are increased by 1 until one reaches it. A tie-breaker is needed, and usually, it is the first line on the left. The increase is needed to ensure that older lines are aged properly and will be evicted if they are not reused.

===== Static RRIP (SRRIP) =====
SRRIP inserts lines with an RRPV value of maxRRPV; a line which has just been inserted will be the most likely to be evicted on a cache miss.

===== Bimodal RRIP (BRRIP) =====
SRRIP performs well normally, but suffers when the working set is much larger than the cache size and causes [[cache thrashing]]. This is remedied by inserting lines with an RRPV value of maxRRPV most of the time, and inserting lines with an RRPV value of maxRRPV - 1 randomly with a low probability. This causes some lines to "stick" in the cache, and helps prevent thrashing. BRRIP degrades performance, however, on non-thrashing accesses. SRRIP performs best when the working set is smaller than the cache, and BRRIP performs best when the working set is larger than the cache.

===== Dynamic RRIP (DRRIP) =====

DRRIP<ref name=":0" /> uses set dueling<ref>{{Cite journal |last1=Qureshi |first1=Moinuddin K. |last2=Jaleel |first2=Aamer |last3=Patt |first3=Yale N. |last4=Steely |first4=Simon C. |last5=Emer |first5=Joel |date=2007-06-09 |title=Adaptive insertion policies for high performance caching |url=https://doi.org/10.1145/1273440.1250709 |journal=ACM SIGARCH Computer Architecture News |volume=35 |issue=2 |pages=381–391 |doi=10.1145/1273440.1250709 |issn=0163-5964}}</ref> to select whether to use SRRIP or BRRIP. It dedicates a few sets (typically 32) to use SRRIP and another few to use BRRIP, and uses a policy counter which monitors set performance to determine which policy will be used by the rest of the cache.