For its on-chip cache, the Intel 80486 uses a replacement algorithm referred to as pseudo least recently used. Associated with each of the 128 sets of four lines (labeled L0, L1, L2, L3) are three bits B0, B1, and B2. The replacement algorithm works as follows: When a line must be replaced, the cache will first determine whether the most recent use was from L0 and L1 or L2 and L3.Then the cache will determine which of the pair of blocks was least recently used and mark it for replacement. Figure 4.20 illustrates the logic.
a. Specify how the bits B0, B1, and B2 are set and then describe in words how they are used in the replacement algorithm depicted in Figure 4.20.
b. Show that the 80486 algorithm approximates a true LRU algorithm.
c. Demonstrate that a true LRU algorithm would require 6 bits per set.

Transcribed Image Text:

All four lines|n- the set valid? Replace nonvalid line 0 Yes Yes, LO or L1 least recently used No, L2 or L3 least recently used B1 = 0? B2 = 0? Yes No Yes No Replace L2 Replace Replace LI Replace L3 1.0 Figure 4.20 Intel 80486 On-Chip Cache Replacement Strategy