Cache replacement policies

In computing, cache replacement policies (also known as cache replacement algorithms or cache algorithms) are optimizing instructions or algorithms which a computer program or hardware-maintained structure can utilize to manage a cache of information. Caching improves performance by keeping recent or often-used data items in memory locations which are faster, or computationally cheaper to access, than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for new data.

Overview

The average memory reference time is

T

=

m

×

T

m

+

T

h

+

E

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

where

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

A cache has two primary figures of merit: latency and hit ratio. A number of secondary factors also affect cache performance.

The hit ratio of a cache describes how often a searched-for item is found. More efficient replacement strategies 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 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.