Cache replacement policies

<h2 id="overview">Overview</h2>
<p>The average memory reference time is<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>

T
        =
        m
        ×
        
          T
          
            m
          
        
        +
        
          T
          
            h
          
        
        +
        E
      
    
    {\displaystyle T=m\times T_{m}+T_{h}+E}

<p>where
</p>

m
      
    
    {\displaystyle m}
  
 = miss ratio = 1 - (hit ratio)

T
          
            m
          
        
      
    
    {\displaystyle T_{m}}
  
 = time to make main-memory access when there is a miss (or, with a multi-level cache, average memory reference time for the next-lower cache)

T
          
            h
          
        
      
    
    {\displaystyle T_{h}}
  
= latency: time to reference the cache (should be the same for hits and misses)

E
      
    
    {\displaystyle E}
  
 = secondary effects, such as queuing effects in multiprocessor systems
<p>A cache has two primary figures of merit: latency and hit ratio. A number of secondary factors also affect cache performance.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p><p>The hit ratio of a cache describes how often a searched-for item is found. More efficient replacement policies track more usage information to improve the hit rate for a given cache size.
The latency of a cache describes how long after requesting a desired item the cache can return that item when there is a hit. Faster replacement strategies typically track of less usage information—or, with a direct-mapped cache, no information—to reduce the time required to update the information. Each replacement strategy is a compromise between hit rate and latency.
</p><p>Hit-rate measurements are typically performed on <a href="/facts/Benchmark_(computing)/XSS42cRe">benchmark</a> applications, and the hit ratio varies by application. Video and audio streaming applications often have a hit ratio near zero, because each bit of data in the stream is read once (a compulsory miss), used, and then never read or written again. Many cache algorithms (particularly <a href="/facts/Page_replacement_algorithm/ApuSJLaq">LRU</a>) allow streaming data to fill the cache, pushing out information which will soon be used again (<a href="/facts/Cache_pollution/35RlcQAT">cache pollution</a>).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Other factors may be size, length of time to obtain, and expiration. Depending on cache size, no further caching algorithm to discard items may be needed. Algorithms also maintain <a href="/facts/Cache_coherence/MhUD576q">cache coherence</a> when several caches are used for the same data, such as multiple database servers updating a shared data file.
</p>
<h2 id="policies">Policies</h2>
<h3>Bélády's algorithm</h3>
<p>The most efficient caching algorithm would be to discard information which would not be needed for the longest time; this is known as <a href="/facts/L%25C3%25A1szl%25C3%25B3_B%25C3%25A9l%25C3%25A1dy/HMM9REqx">Bélády</a>'s optimal algorithm, optimal replacement policy, or <a href="/facts/Page_replacement_algorithm/ApuSJLaq">the clairvoyant algorithm</a>. Since it is generally impossible to predict how far in the future information will be needed, this is unfeasible in practice. The practical minimum can be calculated after experimentation, and the effectiveness of a chosen cache algorithm can be compared.
</p>

<p>When a <a href="/facts/Page_fault/0pzn9ByX">page fault</a> occurs, a set of pages is in memory. In the example, the sequence of 5, 0, 1 is accessed by Frame 1, Frame 2, and Frame 3 respectively. When 2 is accessed, it replaces value 5 (which is in frame 1, predicting that value 5 will not be accessed in the near future. Because a general-purpose operating system cannot predict when 5 will be accessed, Bélády's algorithm cannot be implemented there.
</p>
<h3>Random replacement (RR)</h3>
<p>Random replacement selects an item and discards it to make space when necessary. This algorithm does not require keeping any access history. It has been used in <a href="/facts/ARM_architecture_family/SALsYA79">ARM processors</a> due to its simplicity,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> and it allows efficient <a href="/facts/Stochastic/uMbgL94r">stochastic</a> simulation.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h3>Simple queue-based policies</h3>
<h4>First in first out (FIFO)</h4>
<p>With this algorithm, the cache behaves like a <a href="/facts/FIFO_(computing_and_electronics)/RctvBNgE">FIFO queue</a>; it evicts blocks in the order in which they were added, regardless of how often or how many times they were accessed before.
</p>
<h4>Last in first out (LIFO) or First in last out (FILO)</h4>
<p>The cache behaves like a <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack</a>, and unlike a FIFO queue. The cache evicts the block added most recently first, regardless of how often or how many times it was accessed before.
</p>
<h4>SIEVE</h4>
<p>SIEVE is a simple eviction algorithm designed specifically for web caches, such as key-value caches and Content Delivery Networks. 
It uses the idea of lazy promotion and quick demotion.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> Therefore, SIEVE does not update the global data structure at cache hits and delays the update till eviction time; meanwhile, it quickly evicts newly inserted objects because cache workloads tend to show high one-hit-wonder ratios, and most of the new objects are not worthwhile to be kept in the cache. SIEVE uses a single FIFO queue and uses a moving hand to select objects to evict. Objects in the cache have one bit of metadata indicating whether the object has been requested after being admitted into the cache. The eviction hand points to the tail of the queue at the beginning and moves toward the head over time. Compared with the CLOCK eviction algorithm, retained objects in SIEVE stay in the old position. Therefore, new objects are always at the head, and the old objects are always at the tail. As the hand moves toward the head, new objects are quickly evicted (quick demotion), which is the key to the high efficiency in the SIEVE eviction algorithm. SIEVE is simpler than LRU, but achieves lower miss ratios than LRU on par with state-of-the-art eviction algorithms. Moreover, on stationary skewed workloads, SIEVE is better than existing known algorithms including LFU.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>
<h3>Simple recency-based policies</h3>
<h4>Least Recently Used (LRU)</h4>
<p>Discards least recently used items first. This algorithm requires keeping track of what was used and when, which is cumbersome. It requires "age bits" for <a href="/facts/CPU_cache/x8BYFcdv">cache lines</a>, and tracks the least recently used cache line based on these age bits. When a cache line is used, the age of the other cache lines changes. LRU is <a href="/facts/Page_replacement_algorithm/ApuSJLaq">a family of caching algorithms</a>, that includes 2Q by Theodore Johnson and Dennis Shasha<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and LRU/K by Pat O'Neil, Betty O'Neil and Gerhard Weikum.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> The access sequence for the example is A B C D E D F:
</p>

<p>When A B C D is installed in the blocks with sequence numbers (increment 1 for each new access) and E is accessed, it is a <a href="/facts/CPU_cache/x8BYFcdv">miss</a> and must be installed in a block. With the LRU algorithm, E will replace A because A has the lowest rank (A(0)). In the next-to-last step, D is accessed and the sequence number is updated. F is then accessed, replacing B – which had the lowest rank, (B(1)).
</p>
<h4>Time-aware, least-recently used</h4>
<p>Time-aware, least-recently-used (TLRU)<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> is a variant of LRU designed for when the contents of a cache have a valid lifetime. The algorithm is suitable for network cache applications such as <a href="/facts/Information-centric_networking/wPwwCDU9">information-centric networking</a> (ICN), <a href="/facts/Content_delivery_network/SVuID7jd">content delivery networks</a> (CDNs) and distributed networks in general. TLRU introduces a term: TTU (time to use), a timestamp of content (or a page) which stipulates the usability time for the content based on its locality and the content publisher. TTU provides more control to a local administrator in regulating network storage.
</p><p>When content subject to TLRU arrives, a cache <a href="/facts/Node_(computer_science)/eYlvVE0z">node</a> calculates the local TTU based on the TTU assigned by the content publisher. The local TTU value is calculated with a locally-defined function. When the local TTU value is calculated, content replacement is performed on a subset of the total content of the cache node. TLRU ensures that less-popular and short-lived content is replaced with incoming content.
</p>
<h4>Most-recently-used (MRU)</h4>
<p>Unlike LRU, MRU discards the most-recently-used items first. At the 11th <a href="/facts/VLDB_conference/kI6n1DQA">VLDB conference</a>, Chou and DeWitt said: "When a file is being repeatedly scanned in a [looping sequential] reference pattern, MRU is the best <a href="/facts/Page_replacement_algorithm/ApuSJLaq">replacement algorithm</a>."<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> Researchers presenting at the 22nd VLDB conference noted that for random access patterns and repeated scans over large <a href="/facts/Data_set/eDvegUTK">datasets</a> (also known as cyclic access patterns), MRU cache algorithms have more hits than LRU due to their tendency to retain older data.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> MRU algorithms are most useful in situations where the older an item is, the more likely it is to be accessed. The access sequence for the example is A B C D E C D B:
</p>

<p>A B C D are placed in the cache, since there is space available. At the fifth access (E), the block which held D is replaced with E since this block was used most recently. At the next access (to D), C is replaced since it was the block accessed just before D.
</p>
<h4>Segmented LRU (SLRU)</h4>
<p>An SLRU cache is divided into two segments: probationary and protected. Lines in each segment are ordered from most- to least-recently-accessed. Data from misses is added to the cache at the most-recently-accessed end of the probationary segment. Hits are removed from where they reside and added to the most-recently-accessed end of the protected segment; lines in the protected segment have been accessed at least twice. The protected segment is finite; migration of a line from the probationary segment to the protected segment may force the migration of the LRU line in the protected segment to the most-recently-used end of the probationary segment, giving this line another chance to be accessed before being replaced. The size limit of the protected segment is an SLRU parameter which varies according to <a href="/facts/Input%2foutput/WQTE8Jas">I/O</a> workload patterns. When data must be discarded from the cache, lines are obtained from the LRU end of the probationary segment.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a>
</p>
<h4>LRU approximations</h4>
<p>LRU may be expensive in caches with higher <a href="/facts/Associative_property/EQX8lV6r">associativity</a>. Practical hardware usually employs an approximation to achieve similar performance at a lower hardware cost.
</p>
<h5>Pseudo-LRU (PLRU)</h5>
<p class="note">Further information: <a href="/facts/Pseudo-LRU/Kp7acgbR">Pseudo-LRU</a></p>
<p>For <a href="/facts/CPU_caches/x8BYFcdv">CPU caches</a> with large <a href="/facts/CPU_cache/x8BYFcdv">associativity</a> (generally > four ways), the implementation cost of LRU becomes prohibitive. In many CPU caches, an algorithm that almost always discards one of the least recently used items is sufficient; many CPU designers choose a PLRU algorithm, which only needs one bit per cache item to work. PLRU typically has a slightly-worse miss ratio, slightly-better <a href="/facts/CAS_latency/4slUyjdX">latency</a>, uses slightly less power than LRU, and has a lower <a href="/facts/Overhead_(computing)/e2jgPrHr">overhead</a> than LRU.
</p><p>Bits work as a binary tree of one-bit pointers which point to a less-recently-used sub-tree. Following the pointer chain to the leaf node identifies the replacement candidate. With an access, all pointers in the chain from the accessed way's leaf node to the root node are set to point to a sub-tree which does not contain the accessed path. The access sequence in the example is A B C D E:
</p>

<p>When there is access to a value (such as A) and it is not in the cache, it is loaded from memory and placed in the block where the arrows are pointing in the example. After that block is placed, the arrows are flipped to point the opposite way. A, B, C and D are placed; E replaces A as the cache fills because that was where the arrows were pointing, and the arrows which led to A flip to point in the opposite direction (to B, the block which will be replaced on the next cache miss).
</p>
<h5>Clock-Pro</h5>
<p>The LRU algorithm cannot be implemented in the critical path of computer systems, such as <a href="/facts/Operating_system/8XTuvMh2">operating systems</a>, due to its high overhead; <a href="/facts/Page_replacement_algorithm/ApuSJLaq">Clock</a>, an approximation of LRU, is commonly used instead. Clock-Pro is an approximation of <a href="/facts/LIRS_caching_algorithm/zr3UVLKP">LIRS</a> for low-cost implementation in systems.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> Clock-Pro has the basic Clock framework, with three advantages. It has three "clock hands" (unlike Clock's single "hand"), and can approximately measure the reuse distance of data accesses. Like LIRS, it can quickly evict one-time-access or low-<a href="/facts/Locality_of_reference/fYFKDv5q">locality</a> data items. Clock-Pro is as complex as Clock, and is easy to implement at low cost. The buffer-cache replacement implementation in the 2017 version of <a href="/facts/Linux/9FvCKSTq">Linux</a> combines LRU and Clock-Pro.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a><a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a>
</p>
<h3>Simple frequency-based policies</h3>
<h4>Least frequently used (LFU)</h4>
<p class="note">Further information: <a href="/facts/Least_frequently_used/MrnTKYeL">Least frequently used</a></p>
<p>The LFU algorithm counts how often an item is needed; those used less often are discarded first. This is similar to LRU, except that how many times a block was accessed is stored instead of how recently. While running an access sequence, the block which was used the fewest times will be removed from the cache.
</p>
<h4>Least frequent recently used (LFRU)</h4>
<p>The least frequent recently used (LFRU)<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> algorithm combines the benefits of LFU and LRU. LFRU is suitable for network cache applications such as <a href="/facts/Information-centric_networking/wPwwCDU9">ICN</a>, <a href="/facts/Content_delivery_network/SVuID7jd">CDNs</a>, and distributed networks in general. In LFRU, the cache is divided into two partitions: privileged and unprivileged. The privileged partition is protected and, if content is popular, it is pushed into the privileged partition. In replacing the privileged partition, LFRU evicts content from the unprivileged partition; pushes content from the privileged to the unprivileged partition, and inserts new content into the privileged partition. LRU is used for the privileged partition and an approximated LFU (ALFU) algorithm for the unprivileged partition.
</p>
<h4>LFU with dynamic aging (LFUDA)</h4>
<p>A variant, LFU with dynamic aging (LFUDA), uses dynamic aging to accommodate shifts in a set of popular objects; it adds a cache-age factor to the reference count when a new object is added to the cache or an existing object is re-referenced. LFUDA increments cache age when evicting blocks by setting it to the evicted object's key value, and the cache age is always less than or equal to the minimum key value in the cache.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> If an object was frequently accessed in the past and becomes unpopular, it will remain in the cache for a long time (preventing newly- or less-popular objects from replacing it). Dynamic aging reduces the number of such objects, making them eligible for replacement,  and LFUDA reduces <a href="/facts/Cache_pollution/35RlcQAT">cache pollution</a> caused by LFU when a cache is small.
</p>
<h3>RRIP-style policies</h3>
<p>RRIP-style policies are the basis for other cache replacement policies, including Hawkeye.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> 
</p>
<h4>Re-Reference Interval Prediction (RRIP)</h4>
<p>RRIP<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> is a flexible policy, proposed by <a href="/facts/Intel/SMF0gJJX">Intel</a>, 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.
</p><p>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 23 - 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.
</p>
<h5>Static RRIP (SRRIP)</h5>
<p>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.
</p>
<h5>Bimodal RRIP (BRRIP)</h5>
<p>SRRIP performs well normally, but suffers when the working set is much larger than the cache size and causes <a href="/facts/Cache_thrashing/7Xvz6xEa">cache thrashing</a>. 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.
</p>
<h5>Dynamic RRIP (DRRIP)</h5>
<p>DRRIP<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> uses set dueling<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> 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.
</p>
<h3>Policies approximating Bélády's algorithm</h3>
<p>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,<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> allowing them to approximate the optimal replacement policy. Some of the best-performing cache replacement policies attempt to imitate Bélády's algorithm.
</p>
<h4>Hawkeye</h4>
<p>Hawkeye<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> 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 
  
    
      
        8
        ×
        
          the cache size
        
      
    
    {\displaystyle 8\times {\text{the cache size}}}
  
 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 <a href="/facts/Page_replacement_algorithm/ApuSJLaq">OPT</a> generator set the initial RRPV value of the inserted cache lines. Hawkeye won the CRC2 cache championship in 2017,<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a> and Harmony<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> is an extension of Hawkeye which improves prefetching performance.
</p>

<h4>Mockingjay</h4>
<p>Mockingjay<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> 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.
</p><p>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,<a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a> where the new RDP value will be increased or decreased by a small number to compensate for outliers; the number is calculated as 
  
    
      
        w
        =
        min
        
          (
          
            1
            ,
            
              
                timestamp difference
                16
              
            
          
          )
        
      
    
    {\displaystyle w=\min \left(1,{\frac {\text{timestamp difference}}{16}}\right)}
  
. 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.
</p><p>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.
</p>
<h3>Machine-learning policies</h3>
<p>A number of policies have attempted to use <a href="/facts/Perceptron/ArxdkAC1">perceptrons</a>, <a href="/facts/Markov_chain/5oP5hntk">markov chains</a> or other types of <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> to predict which line to evict.<a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a><a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a> Learning augmented algorithms also exist for cache replacement.
<a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a><a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a>
</p>
<h3>Other policies</h3>
<h4>Low inter-reference recency set (LIRS)</h4>
<p class="note">Further information: <a href="/facts/LIRS_caching_algorithm/zr3UVLKP">LIRS caching algorithm</a></p>
<p>LIRS is a page replacement algorithm with better performance than LRU and other, newer replacement algorithms. Reuse distance is a metric for dynamically ranking accessed pages to make a replacement decision.<a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a> LIRS addresses the limits of LRU by using recency to evaluate inter-reference recency (IRR) to make a replacement decision.
</p>

<p>In the diagram, X indicates that a block is accessed at a particular time. If block A1 is accessed at time 1, its recency will be 0; this is the first-accessed block and the IRR will be 1, since it predicts that A1 will be accessed again in time 3. In time 2, since A4 is accessed, the recency will become 0 for A4 and 1 for A1; A4 is the most recently accessed object, and the IRR will become 4. At time 10, the LIRS algorithm will have two sets: an LIR set = {A1, A2} and an HIR set = {A3, A4, A5}. At time 10, if there is access to A4 a miss occurs; LIRS will  evict A5 instead of A2 because of its greater recency.
</p>
<h4>Adaptive replacement cache</h4>
<p><a href="/facts/Adaptive_replacement_cache/KqUfMduG">Adaptive replacement cache</a> (ARC) constantly balances between LRU and LFU to improve the combined result.<a class="footnote-ref" id="fnref:34" href="#fn:34"><sup>34</sup></a> It improves SLRU by using information about recently-evicted cache items to adjust the size of the protected and probationary segments to make the best use of available cache space.<a class="footnote-ref" id="fnref:35" href="#fn:35"><sup>35</sup></a>
</p>
<h4>Clock with adaptive replacement</h4>
<p><a href="/facts/Page_replacement_algorithm/ApuSJLaq">Clock with adaptive replacement</a> (CAR) combines the advantages of ARC and <a href="/facts/Page_replacement_algorithm/ApuSJLaq">Clock</a>. CAR performs comparably to ARC, and outperforms LRU and Clock. Like ARC, CAR is self-tuning and requires no user-specified parameters.
</p>
<h4>Multi-queue</h4>
<p>The multi-queue replacement (MQ) algorithm was developed to improve the performance of a second-level buffer cache, such as a server buffer cache, and was introduced in a paper by Zhou, Philbin, and Li.<a class="footnote-ref" id="fnref:36" href="#fn:36"><sup>36</sup></a> The MQ cache contains an <i>m</i> number of LRU queues: Q0, Q1, ..., Q<i>m</i>-1. The value of <i>m</i> represents a hierarchy based on the lifetime of all blocks in that queue.<a class="footnote-ref" id="fnref:37" href="#fn:37"><sup>37</sup></a>
</p>

<h4>Pannier</h4>
<p>Pannier<a class="footnote-ref" id="fnref:38" href="#fn:38"><sup>38</sup></a> is a container-based flash caching mechanism which identifies containers whose blocks have variable access patterns. Pannier has a priority-queue-based survival-queue structure to rank containers based on their survival time, which is proportional to live data in the container.
</p>
<h2 id="static-analysis">Static analysis</h2>
<p><a href="/facts/Static_analysis/YkJEVPxs">Static analysis</a> determines which accesses are cache hits or misses to indicate the <a href="/facts/Worst-case_execution_time/PQfFMtGx">worst-case execution time</a> of a program.<a class="footnote-ref" id="fnref:39" href="#fn:39"><sup>39</sup></a> An approach to analyzing properties of LRU caches is to give each block in the cache an "age" (0 for the most recently used) and compute intervals for possible ages.<a class="footnote-ref" id="fnref:40" href="#fn:40"><sup>40</sup></a> This analysis can be refined to distinguish cases where the same program point is accessible by paths that result in misses or hits.<a class="footnote-ref" id="fnref:41" href="#fn:41"><sup>41</sup></a> An efficient analysis may be obtained by abstracting sets of cache states by <a href="/facts/Antichain/rPuqkKJt">antichains</a> which are represented by compact <a href="/facts/Binary_decision_diagram/977o5E7L">binary decision diagrams</a>.<a class="footnote-ref" id="fnref:42" href="#fn:42"><sup>42</sup></a>
</p><p>LRU static analysis does not extend to pseudo-LRU policies. According to <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, static-analysis problems posed by pseudo-LRU and FIFO are in higher <a href="/facts/Complexity_class/IIKrcTbP">complexity classes</a> than those for LRU.<a class="footnote-ref" id="fnref:43" href="#fn:43"><sup>43</sup></a><a class="footnote-ref" id="fnref:44" href="#fn:44"><sup>44</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Cache-oblivious_algorithm/8pueWrAn">Cache-oblivious algorithm</a></li>
<li><a href="/facts/Distributed_cache/ry6do0bs">Distributed cache</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.usenix.org/events/usenix01/full_papers/zhou/zhou_html/node3.html">Definitions of various cache algorithms</a></li>
<li><a href="http://dl.acm.org/citation.cfm?id=2814734">Caching algorithm for flash/SSDs</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Alan Jay Smith.
"Design of CPU Cache Memories".
Proc. IEEE TENCON, 1987.
[1] <a href="http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-357.pdf" target="_blank">http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-357.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Alan Jay Smith.
"Design of CPU Cache Memories".
Proc. IEEE TENCON, 1987.
[1] <a href="http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-357.pdf" target="_blank">http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-357.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Paul V. Bolotoff.
"Functional Principles of Cache Memory" Archived 14 March 2012 at the Wayback Machine. 2007. <a href="http://alasir.com/articles/cache_principles/" target="_blank">http://alasir.com/articles/cache_principles/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>ARM Cortex-R Series Programmer's Guide <a href="https://developer.arm.com/documentation/den0042/a/Caches/Cache-policies/Replacement-policy" target="_blank">https://developer.arm.com/documentation/den0042/a/Caches/Cache-policies/Replacement-policy</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>An Efficient Simulation Algorithm for Cache of Random Replacement Policy [2] <a href="https://doi.org/10.1007%2F978-3-642-15672-4_13" target="_blank">https://doi.org/10.1007%2F978-3-642-15672-4_13</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Yang, Juncheng; Qiu, Ziyue; Zhang, Yazhuo; Yue, Yao; Rashmi, K. V. (22 June 2023). "FIFO can be Better than LRU: The Power of Lazy Promotion and Quick Demotion". Proceedings of the 19th Workshop on Hot Topics in Operating Systems. HOTOS '23. New York, NY, USA: Association for Computing Machinery. pp. 70–79. doi:10.1145/3593856.3595887. ISBN 979-8-4007-0195-5. <a href="979-8-4007-0195-5" target="_blank">979-8-4007-0195-5</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Zhang, Yazhuo; Yang, Juncheng; Yue, Yao; Vigfusson, Ymir; Rashmi, K. V. (2024). {SIEVE} is Simpler than {LRU}: an Efficient {Turn-Key} Eviction Algorithm for Web Caches. pp. 1229–1246. ISBN 978-1-939133-39-7. <a href="978-1-939133-39-7" target="_blank">978-1-939133-39-7</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Johnson, Theodore; Shasha, Dennis (12 September 1994). "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm" (PDF). Proceedings of the 20th International Conference on Very Large Data Bases. VLDB '94. San Francisco, CA: Morgan Kaufmann Publishers Inc.: 439–450. ISBN 978-1-55860-153-6. S2CID 6259428. <a href="978-1-55860-153-6" target="_blank">978-1-55860-153-6</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>O'Neil, Elizabeth J.; O'Neil, Patrick E.; Weikum, Gerhard (1993). "The LRU-K page replacement algorithm for database disk buffering". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. New York, NY, USA: ACM. pp. 297–306. CiteSeerX 10.1.1.102.8240. doi:10.1145/170035.170081. ISBN 978-0-89791-592-2. S2CID 207177617. <a href="978-0-89791-592-2" target="_blank">978-0-89791-592-2</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Bilal, Muhammad; et al. (2014). "Time Aware Least Recent Used (TLRU) cache management policy in ICN". 16th International Conference on Advanced Communication Technology. pp. 528–532. arXiv:1801.00390. Bibcode:2018arXiv180100390B. doi:10.1109/ICACT.2014.6779016. ISBN 978-89-968650-3-2. S2CID 830503. <a href="978-89-968650-3-2" target="_blank">978-89-968650-3-2</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Hong-Tai Chou and David J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB, 1985. <a href="http://www.vldb.org/conf/1985/P127.PDF" target="_blank">http://www.vldb.org/conf/1985/P127.PDF</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, and Michael Tan. Semantic Data Caching and Replacement. VLDB, 1996. <a href="http://www.vldb.org/conf/1996/P330.PDF" target="_blank">http://www.vldb.org/conf/1996/P330.PDF</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In Computer, 1994. <a href="/wiki/Computer_(magazine)" target="_blank">/wiki/Computer_(magazine)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
<li id="fn:14"><p>Jiang, Song; Chen, Feng; Zhang, Xiaodong (2005). "CLOCK-Pro: An Effective Improvement of the CLOCK Replacement" (PDF). Proceedings of the Annual Conference on USENIX Annual Technical Conference. USENIX Association: 323–336. <a href="http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf" target="_blank">http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li>
<li id="fn:15"><p>"Linux Memory Management: Page Replacement Design". 30 December 2017. Retrieved 30 June 2020. <a href="https://linux-mm.org/PageReplacementDesign" target="_blank">https://linux-mm.org/PageReplacementDesign</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li>
<li id="fn:16"><p>"A CLOCK-Pro page replacement implementation". LWN.net. 16 August 2005. Retrieved 30 June 2020. <a href="https://lwn.net/Articles/147879/" target="_blank">https://lwn.net/Articles/147879/</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li>
<li id="fn:17"><p>Bilal, Muhammad; et al. (2017). "A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks". IEEE Access. 5: 1692–1701. arXiv:1702.04078. Bibcode:2017arXiv170204078B. doi:10.1109/ACCESS.2017.2669344. S2CID 14517299. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li>
<li id="fn:18"><p>Jayarekha, P.; Nair, T (2010). "An Adaptive Dynamic Replacement Approach for a Multicast-based Popularity Aware Prefix Cache Memory System". arXiv:1001.4135 [cs.MM]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li>
<li id="fn:19"><p>Jain, Akanksha; Lin, Calvin (June 2016). "Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement". 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA). pp. 78–89. doi:10.1109/ISCA.2016.17. ISBN 978-1-4673-8947-1. <a href="978-1-4673-8947-1" target="_blank">978-1-4673-8947-1</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li>
<li id="fn:20"><p>Jaleel, Aamer; Theobald, Kevin B.; Steely, Simon C.; Emer, Joel (19 June 2010). "High performance cache replacement using re-reference interval prediction (RRIP)". Proceedings of the 37th annual international symposium on Computer architecture. ISCA '10. New York, NY, USA: Association for Computing Machinery. pp. 60–71. doi:10.1145/1815961.1815971. ISBN 978-1-4503-0053-7. S2CID 856628. <a href="978-1-4503-0053-7" target="_blank">978-1-4503-0053-7</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li>
<li id="fn:21"><p>Jaleel, Aamer; Theobald, Kevin B.; Steely, Simon C.; Emer, Joel (19 June 2010). "High performance cache replacement using re-reference interval prediction (RRIP)". Proceedings of the 37th annual international symposium on Computer architecture. ISCA '10. New York, NY, USA: Association for Computing Machinery. pp. 60–71. doi:10.1145/1815961.1815971. ISBN 978-1-4503-0053-7. S2CID 856628. <a href="978-1-4503-0053-7" target="_blank">978-1-4503-0053-7</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li>
<li id="fn:22"><p>Qureshi, Moinuddin K.; Jaleel, Aamer; Patt, Yale N.; Steely, Simon C.; Emer, Joel (9 June 2007). "Adaptive insertion policies for high performance caching". ACM SIGARCH Computer Architecture News. 35 (2): 381–391. doi:10.1145/1273440.1250709. ISSN 0163-5964. <a href="https://doi.org/10.1145/1273440.1250709" target="_blank">https://doi.org/10.1145/1273440.1250709</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li>
<li id="fn:23"><p>Keramidas, Georgios; Petoumenos, Pavlos; Kaxiras, Stefanos (2007). "Cache replacement based on reuse-distance prediction". 2007 25th International Conference on Computer Design. pp. 245–250. doi:10.1109/ICCD.2007.4601909. ISBN 978-1-4244-1257-0. S2CID 14260179. <a href="978-1-4244-1257-0" target="_blank">978-1-4244-1257-0</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li>
<li id="fn:24"><p>Jain, Akanksha; Lin, Calvin (June 2016). "Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement". 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA). pp. 78–89. doi:10.1109/ISCA.2016.17. ISBN 978-1-4673-8947-1. <a href="978-1-4673-8947-1" target="_blank">978-1-4673-8947-1</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li>
<li id="fn:25"><p>"THE 2ND CACHE REPLACEMENT CHAMPIONSHIP – Co-located with ISCA June 2017". crc2.ece.tamu.edu. Retrieved 24 March 2022. <a href="https://crc2.ece.tamu.edu/" target="_blank">https://crc2.ece.tamu.edu/</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li>
<li id="fn:26"><p>Jain, Akanksha; Lin, Calvin (June 2018). "Rethinking Belady's Algorithm to Accommodate Prefetching". 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). pp. 110–123. doi:10.1109/ISCA.2018.00020. ISBN 978-1-5386-5984-7. S2CID 5079813. <a href="978-1-5386-5984-7" target="_blank">978-1-5386-5984-7</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li>
<li id="fn:27"><p>Shah, Ishan; Jain, Akanksha; Lin, Calvin (April 2022). "Effective Mimicry of Belady's MIN Policy". HPCA. <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li>
<li id="fn:28"><p>Sutton, Richard S. (1 August 1988). "Learning to predict by the methods of temporal differences". Machine Learning. 3 (1): 9–44. doi:10.1007/BF00115009. ISSN 1573-0565. S2CID 207771194. <a href="https://doi.org/10.1007%2FBF00115009" target="_blank">https://doi.org/10.1007%2FBF00115009</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li>
<li id="fn:29"><p>Liu, Evan; Hashemi, Milad; Swersky, Kevin; Ranganathan, Parthasarathy; Ahn, Junwhan (21 November 2020). "An Imitation Learning Approach for Cache Replacement". International Conference on Machine Learning. PMLR: 6237–6247. arXiv:2006.16239. <a href="https://proceedings.mlr.press/v119/liu20f.html" target="_blank">https://proceedings.mlr.press/v119/liu20f.html</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li>
<li id="fn:30"><p>Jiménez, Daniel A.; Teran, Elvira (14 October 2017). "Multiperspective reuse prediction". Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture. New York, NY, USA: ACM. pp. 436–448. doi:10.1145/3123939.3123942. ISBN 9781450349529. S2CID 1811177. <a href="9781450349529" target="_blank">9781450349529</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li>
<li id="fn:31"><p>Lykouris, Thodoris; Vassilvitskii, Sergei (7 July 2021). "Competitive Caching with Machine Learned Advice". Journal of the ACM. 68 (4): 1–25. arXiv:1802.05399. doi:10.1145/3447579. eISSN 1557-735X. ISSN 0004-5411. S2CID 3625405. <a href="https://doi.org/10.1145%2F3447579" target="_blank">https://doi.org/10.1145%2F3447579</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li>
<li id="fn:32"><p>Mitzenmacher, Michael; Vassilvitskii, Sergei (31 December 2020). "Algorithms with Predictions". Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. pp. 646–662. arXiv:2006.09123. doi:10.1017/9781108637435.037. ISBN 9781108637435. <a href="9781108637435" target="_blank">9781108637435</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li>
<li id="fn:33"><p>Jiang, Song; Zhang, Xiaodong (June 2002). "LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance" (PDF). ACM SIGMETRICS Performance Evaluation Review. 30 (1). Association for Computing Machinery: 31–42. doi:10.1145/511399.511340. ISSN 0163-5999. <a href="http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf" target="_blank">http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li>
<li id="fn:34"><p>Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST, 2003. <a href="/wiki/Nimrod_Megiddo" target="_blank">/wiki/Nimrod_Megiddo</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></p></li>
<li id="fn:35"><p>"Some insight into the read cache of ZFS - or: The ARC - c0t0d0s0.org". Archived from the original on 24 February 2009. <a href="https://web.archive.org/web/20090224074209/http://www.c0t0d0s0.org/archives/5329-Some-insight-into-the-read-cache-of-ZFS-or-The-ARC.html" target="_blank">https://web.archive.org/web/20090224074209/http://www.c0t0d0s0.org/archives/5329-Some-insight-into-the-read-cache-of-ZFS-or-The-ARC.html</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></p></li>
<li id="fn:36"><p>Yuanyuan Zhou, James Philbin, and Kai Li. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX, 2002. <a href="/wiki/Yuanyuan_Zhou" target="_blank">/wiki/Yuanyuan_Zhou</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></p></li>
<li id="fn:37"><p>Eduardo Pinheiro, Ricardo Bianchini, Energy conservation techniques for disk array-based servers, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France <a href="#fnref:37" class="footnote-back-ref">↩</a></p></li>
<li id="fn:38"><p>Cheng Li, Philip Shilane, Fred Douglis and Grant Wallace. Pannier: A Container-based Flash Cache for Compound Objects. ACM/IFIP/USENIX Middleware, 2015. <a href="http://dl.acm.org/citation.cfm?id=2814734" target="_blank">http://dl.acm.org/citation.cfm?id=2814734</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></p></li>
<li id="fn:39"><p>Christian Ferdinand; Reinhard Wilhelm (1999). "Efficient and precise cache behavior prediction for real-time systems". Real-Time Syst. 17 (2–3): 131–181. Bibcode:1999RTSys..17..131F. doi:10.1023/A:1008186323068. S2CID 28282721. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></p></li>
<li id="fn:40"><p>Christian Ferdinand; Florian Martin; Reinhard Wilhelm; Martin Alt (November 1999). "Cache Behavior Prediction by Abstract Interpretation". Science of Computer Programming. 35 (2–3). Springer: 163–189. doi:10.1016/S0167-6423(99)00010-6. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></p></li>
<li id="fn:41"><p>Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2017). "Ascertaining Uncertainty for Efficient Exact Cache Analysis". Computer-aided verification (2). arXiv:1709.10008. doi:10.1007/978-3-319-63390-9_2. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></p></li>
<li id="fn:42"><p>Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2019). "Fast and exact analysis for LRU caches". Proc. {ACM} Program. Lang. 3 (POPL): 54:1–54:29. arXiv:1811.01670. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></p></li>
<li id="fn:43"><p>David Monniaux; Valentin Touzeau (11 November 2019). "On the complexity of cache analysis for different replacement policies". Journal of the ACM. 66 (6). Association for Computing Machinery: 1–22. doi:10.1145/3366018. S2CID 53219937. <a href="https://hal.archives-ouvertes.fr/hal-01910216v3/" target="_blank">https://hal.archives-ouvertes.fr/hal-01910216v3/</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></p></li>
<li id="fn:44"><p>David Monniaux (13 May 2022). "The complexity gap in the static analysis of cache accesses grows if procedure calls are added". Formal Methods in System Design. 59 (1–3). Springer Verlag: 1–20. arXiv:2201.13056. doi:10.1007/s10703-022-00392-w. S2CID 246430884. <a href="https://hal.archives-ouvertes.fr/hal-03545774/" target="_blank">https://hal.archives-ouvertes.fr/hal-03545774/</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></p></li>
</ol>

Cache replacement policies open-in-new

Cache replacement policies