Multi-level cache hierarchy (L1 - L2 - L3): Foundations

5.4.8 · D1 · Hardware › Memory Hierarchy & Caches › Multi-level cache hierarchy (L1 - L2 - L3)

Yeh page assume karta hai ki tum kuch nahi jaante. Isse pehle ki tum the parent note padh sako aur AMAT derivation ki har line follow kar sako (us acronym ko hum section 7 mein spell out karte hain), tumhe usme har symbol padh paana chahiye. Hum unhe ek ek karke, ek ke upar ek banate hain.

1. CPU aur memory — do characters

Figure — Multi-level cache hierarchy (L1 - L2 - L3)

Figure dekho. CPU baayein taraf hai, warehouse daayein taraf. Red arrow ek fact fetch karne ki ek trip hai. Woh trip lambi hai. Agar CPU ko har ek fact ke liye woh lambi trip karni padi, toh woh apna almost saara time wait karte hue bitaata aur almost kuch bhi kaam nahi karta. Yahi waiting woh problem hai jisko solve karne ke liye yeh topic exist karta hai.

2. Clock cycle — time ki hamari unit

Jab parent note kehta hai "L1 hits in 4 cycles" aur "DRAM costs 200 cycles", matlab: paas wali notebook se fetch karne ke muqable mein door wale warehouse se fetch karna 50 guna zyada ticks leta hai. Woh ratio hi dushman hai.

3. Cache — notebook

Cache internally kaise arranged hai (rows, ways, sets) yeh Cache Organization ka subject hai — yahan hume sirf black-box behaviour chahiye: tum use koi fact ke liye poochho, aur ya toh woh uske paas hai ya nahi hai.

4. Hit aur miss — do outcomes

Figure dekho. CPU se do paths nikalte hain. Short path (ek hit) fast notebook ke andar hi rehta hai. Red long path (ek miss) ko aage next level ki taraf jaane par majboor kiya jaata hai. Har access exactly inhi do paths mein se ek leta hai. Koi teesra option nahi hai — isliye hit aur miss rates hamesha 1 mein add hote hain (yeh hum aage dekhenge).

5. Hit rate $h$ aur miss rate $m$ — outcomes count karna

6. Hit time aur miss penalty — do costs

Definition Level-specific hit times, aur

$T_{mem}$ Rates ki tarah hi, generic hit time $T_{hit}$ ko subscript milta hai yeh batane ke liye ki kaun sa level:

$T_{L1}$ = L1 ka hit time (generic $T_{hit}$ jo L1 ke liye specialized hai) — jaise 4 cycles.
$T_{L2}$ = L2 ka hit time — jaise 12 cycles. $T_{L3}$ = L3 ka hit time — jaise 40 cycles.
$T_{mem}$ = main memory (DRAM) se fetch karne ka time jab har cache miss ho jaaye — jaise 100–200 cycles. Main memory ek cache nahi hai, toh uska khud ka hit/miss nahi hota; $T_{mem}$ simply "final, unavoidable warehouse trip ki cost" hai.

$T_{miss}$ vs. $T_{mem}$ resolve karna: $T_{miss}$ ek general idea hai "miss par extra cost." Single-level formula mein miss par jaane ke liye sirf ek jagah hai — DRAM — toh miss penalty equals $T_{mem}$ . Zyada levels ke saath, ek level ki miss penalty bajaaye next level ka average access time hoti hai, aur sirf last miss hi $T_{mem}$ pay karta hai.

7. Weighted average — woh tool jo sab ko ek saath jodta hai

Parent note ka single-level cache ke liye central formula hai: $AMAT = T_{L1} + m_{L1} \cdot T_{mem}$

Ise un symbols se padho jo humne abhi banaye: $T_{L1}$ L1 hit time hai (hamesha pay hota hai), $m_{L1}$ L1 miss rate hai, aur $T_{mem}$ DRAM fetch cost hai jo sirf miss par pay hoti hai.

Figure mein bar dekho. Har access black base ( $T_{L1}$ ) pay karta hai. Sirf miss fraction upar red extra stack karta hai, aur kyunki yeh ek fraction hai, red block $m$ se shrink ho jaata hai. Poori bar ki height AMAT hai. $m$ ko chhota karna (ek achha cache) red block ko zero ki taraf dabaata hai.

Recall Hum sirf

$T_{L1} + T_{mem}$ kyun nahi add kar sakte? Kyunki iska matlab yeh hoga ki har access DRAM jaata hai, jo galat hai ::: sirf miss fraction $m$ jaata hai, toh hum DRAM cost ko $m$ se weight karte hain.

Multiplication aur nesting

Formula do operations use karta hai jo tum pehle se jaante ho:

Multiply ( $\cdot$ ): "kitni baar" × "kitna" = us penalty ki average cost.
Nest (parentheses ke andar parentheses): ek level ki miss penalty khud next level ka ek AMAT hoti hai. Pehle innermost parentheses compute karo, phir baahri taraf kaam karo. Isliye parent 3-level example ko inside-out solve karta hai: L3+mem 60 deta hai, phir L2 ise 24 mein wrap karta hai, phir L1 ise 5.2 mein wrap karta hai.

8. Size vs. speed — kayi notebooks kyun hoti hain

Yeh size/speed tradeoff isliye hierarchy exist karti hai, aur yahi woh hai jo parent note ka poora "Why Each Level Is Designed Differently" section explain karta hai.

9. Prerequisite map

Is page par sab kuch parent topic mein neeche flow karta hai. Related paths jo tum baad mein miloge: write par kya hota hai (Write Policies), cache kaise decide karta hai kya throw out karna hai (Cache Replacement Policies), shared caches ko consistent rakhna (Cache Coherence), aur address translation (TLB and Virtual Memory). Caches instruction flow ke andar kaise baithte hain yeh CPU Pipeline hai.

Equipment checklist

Khud ko test karo — tum parent note ke liye tab ready ho jab tum bina jhankhe har ek answer de sako.

AMAT acronym ka matlab kya hai?

Average Memory Access Time — ek memory access ka typical cycles, saare accesses par average kiya hua.

Cycle kya hai aur hum seconds ki jagah cycles mein kyun count karte hain?

CPU clock ki ek tick; cycles clock speed se independent hoti hain toh designs fairly compare hote hain.

Hit aur miss mein kya difference hai?

Hit ka matlab data is cache mein hai (fast); miss ka matlab nahi hai, toh hum next slower level par jaate hain.

Agar hit rate

h = 0.90

hai, toh miss rate

m

kya hai?

m = 1 - h = 0.10

T_{L1}

aur

T_{mem}

symbols ka kya matlab hai, aur yeh

T_{hit}

aur

T_{miss}

se kaise relate karte hain?

T_{L1}

generic hit time

T_{hit}

hai jo L1 ke liye specialized hai;

T_{mem}

DRAM fetch cost hai, jo single-level cache mein miss penalty

T_{miss}

ke equal hoti hai.

AMAT formula mein miss penalty ko miss rate se multiply kyun kiya jaata hai?

Kyunki hum penalty sirf un accesses ke fraction par pay karte hain jo miss karte hain; yeh extra cost per access ka weighted average hai.

Kya miss penalty mein next level ka access time include hota hai?

Haan — yeh data wapas fetch karne ka poora time hai, jisme next level ka apna (sambhavit roop se nested) access time shamil hai.

Ek single cache huge aur blazing-fast dono kyun nahi ho sakta?

SRAM per bit expensive hai (cost) aur bade caches mein andar ki wires lambi hoti hain (physics), toh size aur speed trade off karte hain.

Nested AMAT formula mein tum pehle kaun sa parenthesis evaluate karte ho?

Innermost — inside-out kaam karo (pehle L3+mem, phir L2, phir L1).