Replacement Techniques

Replacement Techniques
We discuss three algorithms that are used to deal with miss case when the cache is full:-
-----------------------------------------------------------------------------------------
A) Random Selection
-----------------------------------------------------------------------------------------
It is done based on the output of the random number generator at the time of replacement. The generator produce a number between 0 and (N - 1) where N is no. of blocks in cache. This technique is simple and does not require much additional overhead. However, its main shortcoming is that it does not take locality into consideration. Random techniques have been found effective enough such that they have been first used by Intel in its iAPX microprocessor series.
-----------------------------------------------------------------------------------------
B) The FIFO technique
-----------------------------------------------------------------------------------------
It takes the time spent by a block in the cache as a measure for replacement. The block that has been in the cache the longest is selected for replacement regardless of the recent pattern of access to the block. This technique requires keeping track of the lifetime of a cache block. Therefore, it is not as simple as the random selection technique. The FIFO technique is reasonable to use for straightline programs where locality of reference is not of concern.
-----------------------------------------------------------------------------------------
C) LRU (least recently used) technique:
-----------------------------------------------------------------------------------------
In this method, the cache block that has been recently used the least is selected for replacement. Among the three replacement techniques, the LRU technique is the most effective. This is because the history of block usage (as the criterion for replacement) is taken into consideration.
The LRU algorithm requires the use of a cache controller circuit that keeps track of references to all blocks while residing in the cache. This can be achieved through a number of possible implementations. Among these implementations is the use of counters:
In this case each cache block is assigned a counter. Upon a cache hit, the counter of the corresponding block is set to 0, all other counters having a smaller value than the original value in the counter of the hit block are incremented by 1, and all counters having a larger value are kept unchanged. Upon a cache miss, the block whose counter is showing the maximum value is chosen for replacement, the counter is set to 0, and all other counters are incremented by 1.