कैश मैपिंग लोकैलिटी और औसत एक्सेस समय
सीखने के लक्ष्य और दायरा
Hit और miss का अंतर समझें, byte address को tag/index/offset में बाँटें, छोटा cache trace करें और average memory access time (AMAT) निकालें। पूर्वज्ञान: दो की घातें, पूर्णांक भाग और शेष तथा पते और contents का अंतर। जैसे 2^4=16 होने से चार bits, सोलह byte positions में से एक चुन सकते हैं। यह cache organization का परिचय है; write policies, multilevel hierarchy, coherence, virtual indexing और replacement algorithms के लिए अलग पाठ चाहिए।
यहाँ memory byte-addressed है; cache और block sizes दो की घातें हैं; सामान्य low-bit indexing है; data capacity में metadata शामिल नहीं है। Traces में एक-byte read requests, शुरू में खाली cache और हर miss पर पूरा block लाना मानते हैं। लाया गया block अगले request के लिए उपलब्ध है। Prefetching, invalidation या बीच में अन्य accesses नहीं हैं। Tags और valid bits को data capacity में नहीं गिनते।
1. Cache क्यों उपयोगी हो सकती है
Cache memory blocks की copies रखती है, ताकि कई requests एक छोटे, सामान्यतः तेज storage से पूरी हों। Temporal locality का अर्थ हाल में इस्तेमाल locations को दोबारा इस्तेमाल करना है। Spatial locality का अर्थ पास-पास की locations इस्तेमाल करना है। एक ही counter को बार-बार पढ़ना temporal locality का उदाहरण है। Array के पड़ोसी elements पढ़ने पर, यदि कई elements एक block में हैं, तो spatial locality का लाभ मिल सकता है।
Hit का अर्थ माँगा गया block मौजूद और valid है। Miss में वह नहीं मिलता, इसलिए इस model में अगले memory level से लाया जाता है। खाली cache में किसी block का पहला access compulsory miss है। बाद का access आवश्यक रूप से hit नहीं: block evict हो चुका हो सकता है। हर संभव access sequence में cache लाभ देगी, ऐसा जरूरी नहीं।
2. Block line set और way
Memory block, cache में copy होने वाली इकाई है। Cache line, ऐसा एक block और metadata रखने का स्थान है। Data capacity C bytes और block size B bytes हो तो lines की संख्या L=C/B है।
Direct-mapped cache में हर memory block के लिए ठीक एक possible line है। E-way set-associative cache में उसके लिए एक possible set और उस set की E possible lines हैं। Sets की संख्या S=C/(B×E) है। Direct mapping में E=1 है। Fully associative cache में एक set होता है, इसलिए block किसी भी line में जा सकता है। Placement बताता है block कहाँ जा सकता है; replacement बताता है सभी योग्य lines भरी हों तो किसे हटाएँ।
Associativity, पहले से दी गई total capacity को गुणा नहीं करती। C=1024 bytes, B=16 bytes और E=4 पर कुल 64 lines और 16 sets हैं, 256 lines नहीं।
3. Address fields निकालना
Byte address a के लिए:
- Block number q=floor(a/B);
- byte offset o=a mod B;
- set index i=q mod S;
- tag t=floor(q/S)।
A-bit address में offset के b=log2(B) bits और index के s=log2(S) bits होते हैं। Tag के A−s−b bits बचते हैं। Direct mapping में यही नियम S=L के साथ लागू है। Fully associative cache में s=0 है, यानी index bits नहीं हैं। Lookup में चुने गए set की valid lines में matching tag खोजते हैं। Invalid line का tag समान हो तो भी hit नहीं।
ये सूत्र बताए गए power-of-two, low-bit-indexed organization के लिए हैं, हर वास्तविक implementation के लिए नहीं। Machine का word size, byte offset का स्थान नहीं लेता, जब तक प्रश्न स्पष्ट रूप से word-addressed memory न दे।
4. हल किया उदाहरण: fields और एक address
16-bit byte address, direct-mapped data capacity C=1024 bytes और B=16 bytes लें। L=S=64 है। इसलिए b=4, s=6 और tag width=16−6−4=6 bits। High से low bits का क्रम: tag 6, index 6, offset 4।
a=1170 पर q=floor(1170/16)=73 और o=2। Line index=73 mod 64=9 और tag=floor(73/64)=1। उलटी गणना से जाँचें: ((1×64)+9)×16+2=1170। Block में 1168 से 1183 तक के byte addresses हैं, दोनों सिरे शामिल हैं।
समान capacity और block size के साथ four-way associativity में S=16 होगा। Index width 4 और tag width 8 होंगे। Byte-offset width 4 ही रहेगा। इसी address का set index=73 mod 16=9 और tag=4 होगा। Tag organization पर निर्भर है; वह address का स्थायी label नहीं है।
5. हल किया उदाहरण: conflicts का trace
दो lines और चार-byte blocks वाली direct-mapped cache लें। Byte addresses 0, 1, 8, 0, 4, 8 क्रम से पढ़ें। Block numbers 0, 0, 2, 0, 1, 2 हैं; line index=block number mod 2 है।
| Address | Block | Line | परिणाम | कारण |
|---|---|---|---|---|
| 0 | 0 | 0 | Miss | शुरू में खाली; block 0 लाएँ |
| 1 | 0 | 0 | Hit | मौजूद block 0 का दूसरा byte |
| 8 | 2 | 0 | Miss | Block 2, block 0 को हटाता है |
| 0 | 0 | 0 | Miss | Block 0 हट चुका था; अब block 2 हटेगा |
| 4 | 1 | 1 | Miss | Block 1 का पहला access |
| 8 | 2 | 0 | Miss | Block 2 फिर हट चुका था |
छह requests में एक hit है, इसलिए hit rate=1/6 और miss rate=5/6। चौथी request conflict दिखाती है: blocks 0 और 2 एक ही line चाहते हैं, जबकि दूसरी line अभी खाली है। Blocks 0, 2 और 1 के पहले accesses compulsory misses हैं। बाद के हर miss को conflict न कहें; उपयुक्त fully associative reference से तुलना जरूरी है, क्योंकि सीमित capacity भी miss करा सकती है।
6. AMAT और miss penalty का अर्थ
h hit time, m miss rate और P, cache lookup के बाद miss पर लगने वाला अतिरिक्त समय हो। Hit में h और miss में h+P समय लगता है। इसलिए
AMAT=(1−m)h+m(h+P)=h+mP.
हल किया उदाहरण: h=2 ns, miss rate=0.10 और अतिरिक्त miss penalty P=40 ns। AMAT=2+0.10×40=6 ns। समान रूप से 90% accesses 2 ns और 10% accesses 42 ns लेते हैं: 0.9×2+0.1×42=6 ns।
यदि प्रश्न lookup सहित कुल miss-access time 40 ns बताता है, तो 0.9×2+0.1×40=5.8 ns होगा। इस स्थिति में अतिरिक्त penalty 38 ns है। अंतर शब्दों की परिभाषा का है, गणित का नहीं। Units और lookup के पहले से शामिल होने की जाँच करें। AMAT प्रति memory access समय है; वह अपने आप पूरे program की CPI या execution time नहीं है।
मुख्य बातें और सामान्य गलतियाँ
- Index निकालने से पहले byte address को block number में बदलें।
- C/B से lines और C/(B×E) से sets गिनें। Metadata अतिरिक्त है, जब तक प्रश्न में शामिल न हो।
- Offset block के भीतर स्थान, index set चुनता है; valid matching tag से hit तय होता है।
- Trace में शुरुआती स्थिति, request size और replacement assumptions जरूरी हैं।
- Miss rate fraction है: 10%=0.10, न कि 10।
- h+mP में P अतिरिक्त miss time है। Lookup को दो बार न गिनें और न छोड़ें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
K01. Direct-mapped cache की data capacity 4 KiB, blocks 32-byte और byte addresses 32-bit हैं। क्रमशः tag, index और offset की widths क्या हैं?
A. 20, 7, 5 B. 20, 5, 7 C. 15, 12, 5 D. 25, 2, 5
उत्तर: A
A: 4 KiB=4096 bytes; 4096/32=128 lines, इसलिए index=7, offset=5 और tag=32−7−5=20।
B: इसमें index और offset widths उलट गई हैं।
C: बारह bits cache bytes चुनते हैं, 128 lines नहीं; offset दो बार गिना जाएगा।
D: 128 lines हैं, चार नहीं; दो-bit index पर्याप्त नहीं।
K02. Direct-mapped cache में 256 bytes data और 16-byte blocks हैं। Byte address 1100 का block number, line index और byte offset क्या है?
A. 68, 12, 4 B. 1100, 12, 0 C. 69, 5, 12 D. 68, 4, 12
उत्तर: D
A: इसमें index और byte offset बदल गए हैं।
B: इसमें byte address को block number मान लिया और offset खो गया।
C: पूर्णांक भाग में floor लें: 1100/16 का भाग 68, शेष 12 है, block 69 नहीं।
D: 16 lines हैं; block=floor(1100/16)=68, index=68 mod 16=4 और offset=12।
K03. 8 KiB data cache में 64-byte blocks और four-way set associativity है। कितने sets हैं?
A. 128 B. 32 C. 512 D. 2048
उत्तर: B
A: 128 कुल lines हैं; हर set में चार lines हैं।
B: Sets=8192/(64×4)=32।
C: इसमें line count को associativity से भाग देने के बजाय गुणा किया है।
D: 8192/4 में 64-byte block size नहीं लिया, इसलिए sets नहीं गिने।
K04. शुरू में खाली direct-mapped cache में चार lines और चार-byte blocks हैं। वह 0, 4, 0, 16, 0 addresses पर एक-एक byte क्रम से पढ़ती है; miss पर block लाती है और अन्य accesses नहीं हैं। कितने hits होंगे?
A. 0 B. 2 C. 1 D. 3
उत्तर: C
A: तीसरा address 0 access, block 4 आने से पहले hit है।
B: अंतिम 0 access miss है, क्योंकि address 16 ने line 0 में उसका block हटा दिया।
C: Blocks 0,1,0,4,0 हैं; परिणाम miss, miss, hit, miss, miss हैं: ठीक एक hit।
D: बीच में block हटे तो दोबारा आए address पर hit की गारंटी नहीं।
K05. Hit time 1 ns, miss rate 8% और miss पर lookup के बाद 50 ns अतिरिक्त लगते हैं। AMAT क्या है?
A. 4 ns B. 4.92 ns C. 51 ns D. 5 ns
उत्तर: D
A: चार केवल औसत miss-penalty contribution है; हर access में 1 ns lookup भी है।
B: इसमें 50 ns को कुल miss time मान लिया, जबकि वह lookup के बाद अतिरिक्त है।
C: इक्यावन miss का समय है, hits और misses का औसत नहीं।
D: AMAT=1+0.08×50=5 ns; समान रूप से 0.92×1+0.08×51=5।
K06. Direct-mapped cache की चुनी line का tag, address tag के बराबर है, लेकिन valid bit 0 है। परिणाम क्या होगा?
A. Miss B. Hit C. केवल offset शून्य हो तो hit D. Tag width बदलनी होगी
उत्तर: A
A: Hit के लिए matching tag और valid line दोनों चाहिए; यहाँ validity नहीं है।
B: केवल tag समान होने से invalid data उपयोग योग्य नहीं हो जाता।
C: Offset valid block में byte चुनता है; invalid line को valid नहीं बनाता।
D: Tag width cache organization से तय होती है; lookup का परिणाम उसे नहीं बदलता।
स्रोत और दायरा
यह Computer Organization का आधारभूत पाठ है, पूरे विषय या पूरे पाठ्यक्रम की समाप्ति नहीं। आधिकारिक syllabus विषय का संबंध बताता है; technical references मूल परिभाषाओं की जाँच के लिए हैं। शिक्षण models, हल किए उदाहरण और अभ्यास मौलिक हैं। जाँच: 14 अक्टूबर 2026।
प्रगति सहेजने के लिए साइन इन करें। साइन इन