Computer Organization: Replacement Algorithms

Replacement Algorithms

• Replacement algorithms are needed because there must be a mechanism to replace existing blocks when a new block is brought into a filled cache.
• In direct mapping, there is only one possible line for any particular block, and no choice is possible.
• In associative and set associative techniques, a replacement algorithm is needed.

Least Recently Used (LRU)

• LRU replaces the block in the set that has been in the cache longest with no reference to it.
• This is because recently used memory locations are more likely to be referenced in the future.
• In two-way set associative, LRU is implemented using a USE bit, which is set to 1 when a line is referenced and 0 when the other line in the set is referenced.
• In fully set associative, LRU is implemented using a separate list of indexes to all the lines in the cache, where the line at the back of the list is used for replacement.

First In First Out (FIFO)

• FIFO replaces the block in the set that has been in the cache longest.
• FIFO implementation involves maintaining a queue or list of cache lines, where the cache line at the front of the queue represents the oldest block in the cache.

Least Frequently Used (LFU)

• LFU replaces the block in the set that has experienced the fewest references.
• LFU can be implemented by associating a counter with each line.

Random

• Random replaces a line at random from among the candidate lines.

Write Policy

• When a block that is resident in the cache is to be replaced, there are two cases to consider:
  • Case 1: If the old block in the cache has not been altered, then it may be overwritten with a new block without first writing out the old block.
  • Case 2: If at least one write operation has been performed on a word in that line of the cache, then main memory must be updated by writing the line of cache out to the block of memory before bringing in the new block.

Write Through

• Write through: all write operations are made to main memory as well as cache immediately.
• Disadvantage: The processor always slows down to main memory speed.

Write Back

• Write Back: write operations are written in the main memory before replacing if and only if the control bit (dirty bit) is set.

Learn about replacement algorithms and write strategy in computer organization. Understand why these algorithms are needed and how they work in different caching scenarios.