Week 8 Replacement Algorithm & Write Strategy.pdf

Week 8 : Replacement Algorithms and Write Strategy Ms. Ayyah Fadhl Objective ❑By the end of the lecture, you will know : ❑Replacement Algorithms. ❑Write Policy. Replacement Algorithm ❑Why do we need Replacement Algorithms? 1. Because there should be a mechanism to replace existin...

Week 8 : Replacement Algorithms and Write Strategy Ms. Ayyah Fadhl Objective ❑By the end of the lecture, you will know : ❑Replacement Algorithms. ❑Write Policy. Replacement Algorithm ❑Why do we need Replacement Algorithms? 1. Because there should be a mechanism to replace existing blocks when a new block is brought into a filled cache. ❑Case 1: For direct mapping, there is only one possible line for any particular block, and no choice is possible. ❑Case 2: For the associative and set associative techniques, a replacement algorithm is needed Replacement Algorithm ❑Different Replacement Algorithms are being used each has its own advantage and disadvantage. 1. Least Recently Used (LRU). 2. First in First out (FIFO). 3. Lease Frequently Used (LFU). 4. Random. Replacement Algorithm : least recently used (LRU): ❑Least Recently used (LRU): Replace that block in the set that has been in the cache longest with no reference to it. ❑Because we are assuming that more recently used memory locations are more likely to be referenced in the future. ❑Therefore, by implementing LRU Algorithm , the best hit ratio is implemented. Replacement Algorithm : least recently used (LRU): ❑For two-way set associative, this is easily implemented. ❑ Each line includes a USE bit. ❑When a line is referenced, its USE bit is set to 1 and the USE bit of the other line in that set is set to 0. ❑When a block is to be read into the set, the line whose USE bit is 0 is used. Replacement Algorithm : least recently used (LRU): ❑For Fully set associative, this is easily implemented. ❑The cache mechanism maintains a separate list of indexes to all the lines in the cache. ❑When a line is referenced, it moves to the front of the list. ❑For replacement, the line at the back of the list is used. Replacement Algorithm : First in First out (FIFO): ❑First-in-first-out (FIFO): Replace that block in the set that has been in the cache longest. ❑The implementation of FIFO in cache replacement involves maintain a queue or list of cache lines. ❑Where Cache Line at the front of the queue represents the oldest block in the cache and the cache line at the rear represents the most recently inserted block. Replacement Algorithm : Least frequently used (LFU): ❑least frequently used (LFU): Replace that block in the set that has experienced the fewest references. ❑LFU could be implemented by associating a counter with each line. Replacement Algorithm : Random ❑Random: pick a line at random from among the candidate lines and replace with it. 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. Write Policy ❑When a block that is resident in the cache is to be replaced, there are two cases to consider. ❑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 Policy: Write Through ❑When a block that is resident in the cache is to be replaced, there are two cases to consider. ❑Case 2: ❑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 Policy: Write Back ❑When a block that is resident in the cache is to be replaced, there are two cases to consider. ❑Case 2: ❑Write Back: write operations are written in the main memory before replacing if and only if the control bit(dirty bit) is set. Summary ❑Now, you should know : ❑Replacement Algorithms. 1. Least Recently Used (LRU). 2. First in First out (FIFO). 3. Lease Frequently Used (LFU). 4. Random. ❑Write Strategy: ❑Write Through. ❑Write back.