|
|
|
|
|
|
|
Figure 5.20
Replacement policies. |
|
|
|
|
|
|
|
|
The replacement policy determines which line to replace when cache is full polices: |
|
|
|
|  |
|
|
|
|
LRU (Least Recently Used) |
|
|
|
| |
|
|
|
|
FIFO (First In-First Out) |
|
|
|
| |
|
|
|
|
RAND (Random Replacement) |
|
|
|
| |
|
|
|
|
LRU is generally regarded as the best and most expensive to implent. |
|
|
|
| |
|
|
|
|
RAND is least expensive, but amplifies the miss rate by 12% (average). |
|
|
|
| |
|
|
|
|
For various S/370 traces, the FIFO to LRU ratio varies from 0.96 to 1.38. |
|
|
|
| |
|
|
|
|
RAND appears to perform about the same as FIFO (with respect to LRU). |
|
|
|
|
|
|
|
|
|
2. The number of misses that can be bypassed (or controlled by the cache) while the processor executes. Current implementations do not exceed one bypassed miss. |
|
|
|
|
|
|
|
|
The replacement policy determines which line to replace when a miss occurs and the cache is full (Figure 5.20). There are three replacement policies that have been widely discussed and used; these include: |
|
|
|
|
|
|
|
|
1. Least Recently Used (LRU) Under this policy, the line that was least recently accessed (by a read or write) would be the candidate for replacement. |
|
|
|
|
|
|
|
|
2. First In-First Out (FIFO) Under this policy, the line that had been in the cache the longest is designated the line to be replaced. |
|
|
|
|
|
|
|
|
3. Random Replacement (RAND) Under this policy, replacement is determined randomly. |
|
|
|
|
|
|
|
|
The LRU policy is generally regarded as an ideal policy, since it most closely corresponds to the concept of temporal locality. It is also the most complex to implement, as a counter must be associated with each line and modified on a read (or write) activity. It is possible to create reasonable approximations to the true LRU with small counters. |
|
|
|
|
|
|
|
|
Generally, for most cache sizes, LRU performs better than either FIFO or RAND. For various traces, RAND appears to perform about the same as FIFO and with a range of between 0.96 and 1.38 relative performance with respect to LRU. An overall average of traces studied indicates that RAND or |
|
|
|
|
|
