Mapping function and replacement algorithm

Mapping function

The mapping function decides in which cache line a block of main memory is placed, because the cache has far fewer lines than main memory has blocks. The three functions are direct, associative and set associative mapping.

Why a replacement algorithm is used

In associative and set associative mapping a block may be placed in more than one line (any line of the cache or of the set). When a miss occurs and all candidate lines are already filled, the hardware must pick one line to be overwritten. A replacement algorithm makes that choice. In direct mapping there is only one possible line, so no choice (and no algorithm) is needed.

Common algorithms

• LRU: removes the block unused for the longest time (best hit ratio).
• FIFO: removes the block that has been in the cache longest.
• LFU: removes the block with fewest references.
• Random: removes any line; cheap and fairly good.

Example

A 2-way set has blocks A and B (A used earlier). Block C maps to this set and misses. The set is full, so one of A or B must go. FIFO or LRU removes A (assuming A was the oldest and the least recently used), then the set holds B and C. If a later request is for A, it is a miss and a block is replaced again.

Using the 4-line cache LRU sequence 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 gives 6 hits and 6 misses; block 3 is evicted at the reference to 4 because it is the least recently used.