Replacement Algorithms
● When the cache is full or based on the
mapping function any one of cache line is
replaced with new block .
● Which cache line is it?
● The answer is given by replacement
algorithms. There are 3 replacement
algorithms:
1) Random (Random Replacement (RR) )
2) FIFO (First-In-First-Out)
3) LRU (Least Recently Used) 1
● In the random policy, any one of the cache line can be
replaced by new block.
● In FIFO algo., the cache line with longest time duration
block is replaced with the new block.
● In the LRU policy the cache line with “less number of
references ” and ‘longest duration’ block is replaced with
new block.
2
● Q. Consider a 4 block cache with the
following main memory references:
4, 5, 7, 12, 4, 5, 13, 4, 5, 7
Calculate the Hit ratios using:
a) FIFO
b) LRU
c) Direct mapping
d) 2-way set associative with LRU
3
● Q. Consider a 4 block cache with the
following main memory references:
4, 5, 7, 12, 4, 5, 13, 4, 5, 7
4
● Q. Consider a 4 block cache with the
following main memory references:
4, 5, 7, 12, 4, 5, 13, 4, 5, 7
5
● Q. Consider a 4 block cache with the
following main memory references:
4, 5, 7, 12, 4, 5, 13, 4, 5, 7
6
Q. The main memory of a computer is organized as 64 blocks
with a block size of eight words. The cache has eight block
frames.
● A) Identify the tag field, the block number and the word
number in case of direct mapping.
● B) Show the fully associative mapping and the address bits
that identify the tag field and the word number.
● C) Show the two-way set associativity mapping and the
address bits that identify the tag field, the set number.
