3. An optimal cache replacement policy makes its replacement decisions using per

Question

3. An optimal cache replacement policy makes its replacement decisions using perfect knowledge of the re-reference (or reuse) pattern of each cache block and replaces the block that will be re-referenced furthest in the future. A commonly used replacement policy is the Least Recently Used (LRU) algorithm. The LRU algorithm maintains a chain of cache blocks with the most recently used (MRU) at the head of the chain and the LRU position at the tail. The cache controller hardware maintains the LRU chain by adding some LRU metadata bits to each cache block and representing the recency of access by e.g. an integer encoding. Hence, the MRU position can be represented by 0, next most-recent by 1, and so on until the LRU position is represented by the integer (n-1) for an n-associative (n ways per set) cache. Answer the following questions for a 2-way cache:

(a) How many bits are needed per set in order to maintain the LRU metadata?

(b) How is the LRU metadata updated when a new block is brought into a set? Note that the LRU block is evicted.

(c) How is the LRU metadata updated when a block is accessed that is already in the set?

Answer the following questions for a 4-way cache: (d) How many bits are needed per set in order to maintain the LRU metadata?

(e) How is the LRU metadata updated when a new block is brought into a set? Note that the LRU block is evicted.

(f) How is the LRU metadata updated when a block is accessed that is already in the set?

Explanation / Answer

Solution:

a)

One bit is needed per set to maintain the metadata.

b)

The data at which LRU is pointing will be replaced with the new data in that block and MRU will start to pint at that location.

c)

If the block which is getting accessed is already in the set then MRU will start pointing at that address or data.

d)

for 4-way set total 2 bits are required to represent.

e)

Just like in the above case here also LRU meta data will be updated.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.