Cache replacement write policies और multilevel AMAT
लक्ष्य और सीमाएँ
मौजूदा cache-foundations से आगे बढ़ें: LRU/FIFO trace करें, write-hit policy और write-miss allocation अलग करें, dirty writebacks गिनें, तथा local/global miss rates मिलाए बिना दो levels का AMAT निकालें। पूर्वज्ञान: block/set mapping और single-level AMAT। Address splitting फिर नहीं पढ़ाया गया है। Coherence, virtual indexing, prefetching और overlapping misses इस पाठ से बाहर हैं।
Trace में नाम blocks के हैं, byte addresses के नहीं। प्रत्येक request एक word को उसी block के भीतर access करती है। शुरुआत में सब invalid हैं। Read miss पर allocation है; full set में उसी set से replacement होगा। अगली request से पहले miss service पूरी है। समय निकालते हुए fills/writebacks serialized हैं जब तक अलग न कहा जाए।
1. Replacement इतिहास बदलता है, placement नहीं
LRU उस resident line को निकालता है जिसका आखिरी access सबसे पुराना है। Read/write hit दोनों recency बदलते हैं। FIFO सबसे पहले डाली गई resident line निकालता है; hit insertion order नहीं बदलता। पहले invalid line इस्तेमाल करें। Direct mapping में victim का चुनाव नहीं होता; policy तब महत्वपूर्ण है जब कई eligible lines हों।
उदाहरण: दो-line fully associative cache में reads A,B,A,C,B। LRU states oldest→newest: [A], [A,B], [B,A], [A,C], [C,B]। M,M,H,M,M: एक hit। FIFO में तीसरा access order [A,B] बनाए रखता है; C से A हटता और [B,C] बनता है; आखिरी B hit है। M,M,H,M,H: दो hits। LRU हर छोटे trace पर FIFO से बेहतर होना जरूरी नहीं।
2. Write के दो स्वतंत्र निर्णय
Write hit पर write-through cache बदलकर write अगले level को भेजता है। Write-back cache बदलकर dirty करता है; eviction या अन्य जरूरी writeback तक अगले level को update टालता है। Dirty का अर्थ अगला level पुराना हो सकता है; valid का अर्थ usable cached block है। दोनों अलग प्रश्नों के bits हैं।
Write miss पर write-allocate block लाकर फिर write करता है। No-write-allocate इस cache में block डाले बिना lower level को write भेजता है। Hit policy तथा miss policy स्वतंत्र हैं। Write-back/write-allocate और write-through/no-write-allocate सामान्य जोड़ हैं, अनिवार्य समानार्थी नहीं। वास्तविक full-block store optimization अलग हो सकती है; यहाँ हर allocating miss block fetch करता है।
Traffic उदाहरण: एक-line write-back, write-allocate cache पर W(A), W(A), R(B)। पहला W(A) A fetch करके dirty करता है; दूसरा hit है; R(B) dirty A का एक block writeback और B का fill करता है। कुल दो fills तथा एक writeback, हर store पर lower-level write नहीं। अंत में flush तब तक न जोड़ें जब तक माँगा न गया हो। Write-through/no-write-allocate में दोनों stores नीचे जाते हैं, A install नहीं होता और केवल R(B) block fill करता है। Word write और block transfer अलग units हैं।
3. Dirty victim का conditional खर्च
h=2 ns, m=0.10, fetch F=40 ns; 25% misses dirty victim निकालते हैं और serialized extra D=20 ns लेते हैं। औसत extra miss cost=40+0.25×20=45 ns। AMAT=2+0.10×45=6.5 ns। 25% misses का fraction है, सभी accesses का नहीं। Resident dirty line अभी writeback नहीं करती। दी हुई penalty में dirty writeback पहले से हो तो दोबारा न जोड़ें।
4. दो levels और conditional probability
L1 lookup h1; CPU access के सापेक्ष miss rate m1। L1 miss पर L2 lookup h2 अतिरिक्त है। L2 local miss rate m2, L2 requests में misses का fraction है। L2 miss पर lookup के बाद main-memory penalty P जुड़ती है। हर L1 miss L2 जाता है, lookups parallel नहीं हैं, writes absent या पहले counted हैं।
AMAT=h1+m1(h2+m2P)।
CPU accesses में memory तक जाने वाला fraction m1m2 है, इस model का global L2 miss rate। यह सामान्यतः m2 नहीं है। L2 hit हो तब भी L1 miss, L2 lookup का खर्च देता है।
उदाहरण: h1=1 ns, m1=0.10, h2=8 ns, m2=0.20, P=60 ns। AMAT=1+0.1(8+0.2×60)=3 ns। 1000 requests में 900 L1 hits 1 ns, 80 L2 hits 9 ns और 20 memory accesses 69 ns लेते हैं। Weighted average=(900+720+1380)/1000=3 ns। Global fraction 2% है, L2 local 20% है।
5. Memory stall और CPI
Instruction/data misses अलग हों तो संबंधित accesses प्रति useful instruction, miss rate और extra cycles गुणा करें। Base CPI=1, एक fetch/instruction में 1% misses, 0.3 data accesses/instruction में 5% misses, और दोनों की serialized extra penalty 40 cycles हो। Added CPI=1×0.01×40+0.3×0.05×40=1; total CPI=2। Base में ये misses शामिल नहीं, overlap नहीं और double counting नहीं मानी गई है। AMAT time/access और CPI cycles/instruction है।
सामान्य गलतियाँ
हर request के बाद state, recency तथा dirty status लिखें। Blocks, bytes, word writes और block writebacks अलग रखें। Probabilities का denominator बताएं। Extra तथा total penalty लगातार एक अर्थ में लें। Timing model के बिना अधिक associativity या write buffer से कुल execution तेज होने का दावा न करें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. खाली दो-line fully associative LRU cache में A,B,A,C,B reads हैं। Hits?
A. 1 B. 2 C. 3 D. 0
उत्तर: A
A: केवल तीसरा hit; C से B निकलता है।
B: यहाँ दो hits FIFO में हैं, LRU में नहीं।
C: केवल एक reuse eviction से बचता है।
D: तीसरे पर A resident है।
P02. खाली एक-line write-back/write-allocate cache: W(A),W(A),R(B)। Final flush नहीं है। Dirty writebacks कितने?
A. 0 B. 1 C. 2 D. 3
उत्तर: B
A: R(B), dirty A निकालता है।
B: B आने पर A एक बार writeback होता है।
C: दो stores उसी dirty residency में हैं।
D: हर access writeback नहीं करता।
P03. Write miss पर no-write-allocate क्या बताता है?
A. Write छोड़ दें B. Missed block install करें C. यहाँ block डाले बिना write नीचे भेजें D. सभी valid lines dirty करें
उत्तर: C
A: Store का प्रभाव होना जरूरी है।
B: यह write-allocate है।
C: Miss पर इस cache में allocation bypass होता है।
D: दूसरी lines इस store से असंबंधित हैं।
P04. L1 miss rate 10%, L2 local miss rate 30%; हर L1 miss L2 जाता है। दोनों में miss होने वाला CPU fraction?
A. 30% B. 40% C. 3% D. 10%
उत्तर: C
A: 30% का denominator L2 requests है।
B: Conditional rates जोड़ना गलत है।
C: 0.10×0.30=3%।
D: कुछ L1 misses L2 में hit हैं।
P05. h1=2 ns, m1=0.1, h2=6 ns, m2=0.25; memory L2 के बाद 80 ns जोड़ती है। Serial AMAT?
A. 4.6 ns B. 28 ns C. 2.6 ns D. 10 ns
उत्तर: A
A: 2+0.1(6+0.25×80)=4.6 ns।
B: यह हर CPU access पर L2 path लगाता है।
C: Memory miss cost छूटा है।
D: हर L1 miss को memory miss मानकर L2 lookup भी छोड़ा है।
P06. Lookup=1 ns; miss rate=0.2; fill=30 ns; आधे misses में extra serialized dirty writeback 10 ns है। AMAT?
A. 7 ns B. 8 ns C. 9 ns D. 12 ns
उत्तर: B
A: Dirty writebacks छूटे हैं।
B: 1+0.2(30+0.5×10)=8 ns।
C: यह हर miss पर writeback जोड़ता है।
D: 50% misses का fraction है, सभी accesses का नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे COA syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन