23 May - COA - Problem Solving Session - 18
Duration: 1 hr 29 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This academic lecture video, titled 'COA Doubt Session-5', focuses on Cache Replacement Policies, Multi-Level Caching, and Updating Techniques. The instructor systematically solves a series of problems ranging from basic set-associative cache simulations to complex multi-level hierarchy calculations and GATE exam questions. Key topics covered include FIFO and LRU replacement policies, effective access time calculations for 2 and 3-level caches, and the distinction between compulsory, conflict, and capacity misses. The session also addresses write-back versus write-through policies and analyzes array access patterns in direct-mapped caches.
Chapters
0:00 – 2:00 00:00-02:00
The video begins with an introduction to 'COA Doubt Session-5' by Ekagra Sir. The slide title clearly states the topic: '5. Cache Replacement Policies, Multi-Level Caching & Updating Techniques'. The instructor is seen preparing to start the lecture, setting the stage for a detailed discussion on computer organization concepts related to cache memory.
2:00 – 5:00 02:00-05:00
The first problem is introduced on the screen: 'Consider a 4-block cache memory initially empty with the following main memory references: 4, 5, 7, 12, 4, 5, 13, 4, 5, 7'. The task is to identify the hit ratio using a 2-way Set Associative Cache with FIFO and LRU policies. The instructor draws a 2x2 grid to represent the cache sets for the simulation.
5:00 – 10:00 05:00-10:00
The instructor traces the memory references through the 2-way set associative cache using the FIFO replacement policy. He marks each access as a Hit (H) or Miss (M), updating the cache state accordingly. He calculates the final hit ratio for FIFO as 3 hits out of 10 accesses, resulting in a 30% hit ratio.
10:00 – 15:00 10:00-15:00
Continuing with the same sequence, the instructor applies the LRU (Least Recently Used) replacement policy. He tracks the usage order of blocks in each set, marking hits and misses. He determines the hit ratio for LRU is 4/10, demonstrating the difference in performance between FIFO and LRU policies for the given access pattern.
15:00 – 20:00 15:00-20:00
A theoretical question from GATE 2014 is presented on the slide. It asks for the miss ratio of an access sequence of length N with n unique addresses, where the number of unique addresses between consecutive accesses to the same block is bounded by k, using a cache of associativity A >= k with LRU replacement.
20:00 – 25:00 20:00-25:00
The instructor solves the GATE 2014 problem by creating a concrete example: N=10, n=4, k=3, with sequence A, B, C, D, A, B, C, D, A, B. Using a 3-way associative cache, he shows that the first n accesses are misses and subsequent ones are hits, proving the miss ratio is n/N.
25:00 – 30:00 25:00-30:00
The lecture shifts to a multi-level cache hierarchy problem. Parameters are given: L1 (0.2 ns, 94%), L2 (0.5 ns, 97.7%), Main Memory (25 ns, 100%). The goal is to calculate the effective access time for this 2-level hierarchy, requiring the application of weighted average formulas.
30:00 – 35:00 30:00-35:00
The instructor writes the formula for effective access time: T_avg = H1*T1 + (1-H1)*H2*(T1+T2) + (1-H1)*(1-H2)*Hm*(T1+T2+Tm). He substitutes the given values and calculates the result as 0.2645 ns for the 2-level hierarchy, showing the step-by-step arithmetic.
35:00 – 40:00 35:00-40:00
An L3 cache is added to the hierarchy with a hit time of 1.2 ns and hit rate of 99.92%. The instructor updates the formula to include the L3 terms and calculates the new effective access time, which comes out to be 0.232 ns, showing the improvement in performance with the additional cache level.
40:00 – 45:00 40:00-45:00
A new problem involves a 2-way set associative cache with 4 sets and 8 blocks. The sequence is 0, 5, 9, 13, 7, 0, 15, 25. The task is to find the total number of conflict cache misses, assuming LRU replacement and an initially empty cache, requiring careful mapping of blocks to sets.
45:00 – 50:00 45:00-50:00
The instructor maps the block addresses to cache sets using modulo 4. He traces the sequence and observes that while there are misses, they are all compulsory misses because the cache capacity is sufficient to hold the unique blocks mapping to each set without evicting needed blocks. Thus, conflict misses are 0.
50:00 – 55:00 50:00-55:00
The next problem is a direct mapped cache with 8 words total size and 2 words block size. The sequence is 0, 11, 4, 14, 9, 1, 8, 0. The instructor asks to calculate the number of misses, compulsory misses, conflict misses, and capacity misses, requiring a detailed trace of the cache state.
55:00 – 60:00 55:00-60:00
He traces the direct mapped cache, mapping addresses to blocks (Address/2) and blocks to lines (Block%4). He marks the accesses, identifying the first access to each block as a compulsory miss and subsequent accesses as hits or conflicts, carefully tracking the cache contents.
60:00 – 65:00 60:00-65:00
He classifies the misses found in the trace. He counts the total misses, identifies compulsory misses (first access to 0, 5, 2, 7, 4, 1, 8), and identifies conflict misses where a block is evicted and needed again. He concludes with the specific counts for each type of miss.
65:00 – 70:00 65:00-70:00
To clarify concepts, the instructor displays a StackExchange page defining Capacity and Conflict misses. He reads the definitions: Capacity misses occur when data exceeds cache capacity, while Conflict misses occur when multiple lines map to the same set, forcing eviction.
70:00 – 75:00 70:00-75:00
He shows another source, GateOverflow, which defines a Capacity Miss as occurring when a block is replaced due to lack of space and is accessed again in the future. This reinforces the distinction between capacity and conflict misses, emphasizing the role of cache size.
75:00 – 80:00 75:00-80:00
A GATE 2025 problem is introduced comparing Write Back (WBC) and Write Through (WTC) policies in set-associative caches with LRU replacement. The question asks to identify true statements among four options regarding read/write misses and dirty bits, testing understanding of write policies.
80:00 – 85:00 80:00-85:00
The instructor analyzes the options. He explains that a read miss in WBC can evict a dirty block (False), a read miss in WTC never triggers write back (True), a write hit in WBC modifies the dirty bit (True), and a write miss in WTC does not write the victim (False).
85:00 – 89:05 85:00-89:05
The final problem is from GATE 2007. It involves a direct mapped cache with 32 lines of 64 bytes, accessing a 50x50 array starting at 1100H twice. The instructor begins analyzing the cache structure (Tag, Line, Word) to determine the total data misses, setting up the calculation for the next session.
The lecture provides a comprehensive review of cache memory concepts through a progression of solved problems. It begins with basic replacement policies (FIFO, LRU) in set-associative caches, then moves to theoretical questions about miss ratios in GATE exams. The instructor then tackles multi-level cache hierarchy calculations, demonstrating how to compute effective access time with varying numbers of cache levels. The session further distinguishes between different types of cache misses (compulsory, conflict, capacity) using direct-mapped and set-associative examples, supported by definitions from online resources. Finally, it addresses write policies (write-back vs. write-through) and complex array access patterns in direct-mapped caches, providing a thorough preparation for COA exams.