6 Nov- COA - Cache Replacement Policies

Duration: 1 hr 28 min

This video lesson is available to enrolled students.

Enroll to watch — GATE Guidance by Sanchit Sir

AI Summary

An AI-generated summary of this video lecture.

This lecture covers Cache Replacement Policies, focusing on solving GATE exam problems related to cache memory addressing and replacement algorithms. The instructor begins by deriving the tag field length for a K-way associative cache, breaking down the physical address into Tag, Set, and Block Offset components. He then solves a specific problem involving a 4-way set-associative cache to find the tag value for a given hexadecimal address. The session transitions to theoretical concepts, defining Compulsory, Capacity, and Conflict misses. Finally, the instructor explains and demonstrates three major replacement policies: First In First Out (FIFO), Optimal, and Least Recently Used (LRU), using a common reference string to simulate cache behavior and calculate hit rates and misses.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video begins with an introductory slide titled 'Session-4 Cache Replacement Policies' by Ekagra Sir. The screen displays the name 'Sanchit Jain' briefly before transitioning to the main title slide. The instructor is visible in a small window in the top right corner, preparing to start the lecture on cache memory concepts.

  2. 2:00 – 5:00 02:00-05:00

    The instructor presents a GATE 2018 problem regarding a K-way associative cache. The problem states the physical address space is 2^P bytes, word length is 2^W, cache capacity is 2^N bytes, and block size is 2^M words. He draws a diagram showing the Main Memory address structure divided into Block Number and Block Offset, and the Cache structure divided into Tag, Set, and Block Offset. He begins calculating the bits required for the block offset based on the word length and block size.

  3. 5:00 – 10:00 05:00-10:00

    Continuing the GATE 2018 problem, the instructor calculates the number of sets in the cache. He derives the formula for the tag field length as P - N - M - W - log2K. He explains that the total address bits (P) minus the cache index bits (N) minus the block offset bits (M + W) minus the set index bits (log2K) gives the tag length. He reviews the multiple-choice options and identifies the correct formula corresponding to option (C).

  4. 10:00 – 15:00 10:00-15:00

    A new problem is introduced involving a 4-way set-associative cache. The parameters are: main memory word size 1 byte, block size 128 words, cache size 8 KB. The CPU accesses memory location 0C795H. The instructor calculates the number of bits for the block offset (7 bits for 128 words) and the number of sets. He writes down the address structure with Tag, Set, and Block Offset fields to visualize the bit allocation.

  5. 15:00 – 20:00 15:00-20:00

    The instructor solves the 4-way set-associative problem. He converts the hexadecimal address 0C795H to binary. He identifies the last 7 bits as the block offset. He calculates the number of sets as 64 (since cache size is 8KB and block size is 128 bytes, total blocks = 64, sets = 64/4 = 16). He determines the set index bits (4 bits) and the remaining bits for the tag (9 bits). He extracts the tag value from the binary address.

  6. 20:00 – 25:00 20:00-25:00

    The lecture moves to a GATE 1999 problem about set associative mapping. The main memory has 2cm blocks, and the cache has 2c blocks. The mapping scheme uses 2 blocks per set. The instructor explains that the number of sets is calculated by dividing total cache blocks by associativity. He derives the mapping formula for block k to a set, which is (k mod m) of the cache, where m is the number of sets.

  7. 25:00 – 30:00 25:00-30:00

    A GATE 2014 problem is presented regarding the implications of cache block size. The options discuss spatial locality, tag overhead, and miss penalty. The instructor analyzes option (A), stating that smaller block size implies worse spatial locality, not better. He then evaluates option (B), noting that smaller block size means more blocks for the same cache size, leading to more tags and higher overhead, making the statement false.

  8. 30:00 – 35:00 30:00-35:00

    Continuing the GATE 2014 analysis, the instructor evaluates option (D). He explains that a smaller block size incurs a lower cache miss penalty because less data needs to be fetched from main memory to the cache when a miss occurs. He concludes that option (D) is the correct statement. He writes down '16B -> 8S' to illustrate the relationship between block size and number of sets.

  9. 35:00 – 40:00 35:00-40:00

    The topic shifts to Cache Replacement Policies. The instructor explains that in a direct-mapped cache, each memory block maps to a single predetermined position, so no replacement policy is needed. However, in fully associative and set-associative caches, multiple blocks can map to the same set. When all positions in a set are occupied, a decision must be made on which block to replace.

  10. 40:00 – 45:00 40:00-45:00

    The First In, First Out (FIFO) policy is introduced. The instructor explains that the block that entered the cache first is replaced when the cache is full. He mentions Belady's Anomaly, where increasing cache lines can unexpectedly increase misses. He starts an example with a reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 and a 4-line cache.

  11. 45:00 – 50:00 45:00-50:00

    The instructor simulates the FIFO policy on the reference string. He fills the 4 cache lines with the first four blocks (7, 0, 1, 2). As new blocks arrive (0, 3, 0, 4...), he marks hits and misses. When the cache is full, he replaces the oldest block (7) with the new one (3). He continues this process, marking 'M' for miss and 'H' for hit above the sequence.

  12. 50:00 – 55:00 50:00-55:00

    The FIFO simulation concludes. The instructor counts the total hits and misses. He calculates the hit rate as the number of hits divided by the total accesses. For the given sequence and 4-line cache, he finds 10 hits out of 20 accesses, resulting in a 50% hit rate. He writes 'HR = #hits / #Access = 10/20 = 50%'.

  13. 55:00 – 60:00 55:00-60:00

    The Optimal Page Replacement Algorithm is introduced. It replaces the page that will not be used for the longest period in the future. The instructor notes this is a theoretical benchmark because it requires knowledge of future references. He begins the same example sequence (7, 0, 1, 2...) with a 4-line cache to demonstrate the algorithm.

  14. 60:00 – 65:00 60:00-65:00

    The Optimal algorithm simulation proceeds. When a replacement is needed, the instructor looks ahead in the reference string to see which block in the cache is used furthest in the future. For example, when replacing, he checks if 7, 0, 1, or 2 is needed next. He marks the replacements and hits, showing how this policy minimizes misses compared to FIFO.

  15. 65:00 – 70:00 65:00-70:00

    The Least Recently Used (LRU) policy is explained. It replaces the page that has not been accessed for the longest time in the past. The instructor mentions that while effective, it can be computationally expensive to track exact usage order. He starts the same example sequence to simulate LRU behavior, marking hits and misses.

  16. 70:00 – 75:00 70:00-75:00

    The LRU simulation continues. The instructor tracks the order of usage for the blocks in the cache. When a replacement is needed, he evicts the block that was accessed least recently. He updates the cache state for each access in the sequence, demonstrating how LRU adapts to the access pattern.

  17. 75:00 – 80:00 75:00-80:00

    The lecture covers Types of Misses. Compulsory Miss occurs when a block is accessed for the first time. Capacity Miss occurs when the cache is full and blocks are discarded because the working set is larger than the cache. Conflict Miss occurs in set-associative or direct-mapped caches when multiple blocks map to the same set.

  18. 80:00 – 85:00 80:00-85:00

    A GATE 2017 problem is solved. A 2-way set associative cache with 256 blocks uses LRU. The sequence of accesses is repeated 10 times. The instructor calculates the number of sets (128). He identifies that the first pass causes compulsory misses. Subsequent passes cause conflict misses because the blocks map to the same sets. He calculates the total conflict misses.

  19. 85:00 – 88:03 85:00-88:03

    The final problem is a GATE 2009 question. A 4-way set associative cache with 16 blocks is used. The sequence of memory blocks is 0, 255, 1, 4, 3, 8, 133, 159, 48, 32, 73, 92, 155. The instructor determines which block is NOT in the cache after the sequence using LRU. He simulates the cache state, calculating the set index for each block (block mod 4) and tracking replacements.

The lecture systematically builds understanding of cache memory from addressing to replacement strategies. It starts with practical problem-solving, deriving tag lengths and set indices for K-way associative caches using GATE exam questions. The instructor then transitions to theoretical concepts, defining the three types of cache misses: Compulsory, Capacity, and Conflict. The core of the session focuses on replacement policies, where FIFO, Optimal, and LRU are explained and demonstrated using a common reference string. The instructor highlights the trade-offs, such as Belady's Anomaly in FIFO and the computational cost of LRU. The session concludes with advanced problem-solving involving conflict misses and LRU simulation on specific memory access sequences.