TLB (translation lookaside buffer): Visual walkthrough

5.4.12 · D2 · Hardware › Memory Hierarchy & Caches › TLB (translation lookaside buffer)

Hum sirf yeh assume karte hain ki tum jaante ho ki memory touch karne se pehle address translate hona chahiye — yeh Virtual Memory ka idea hai. Baaki sab kuch neeche earn kiya gaya hai.

Step 1 — Woh do clocks Name Karo Jinse Hum Race Kar Rahe Hain

KYA. Koi bhi time add karne se pehle, humein ek single memory access mein lagaayi jaane waali har duration ko name karna hoga. Time sirf do jagah consume hota hai: ek chhote, fast box ko search karna, aur slow memory ko touch karna.

YEH DO HI KYUN, ZYADA NAHI? Kyunki poori machine mein sirf do speeds humare liye matter karti hain. Ek hai chhoti hardware lookup table (TLB) jo ek fraction of a nanosecond mein jawab deti hai. Doosri hai DRAM, jo roughly sau guna slower hai. Hum jo bhi cost compute karenge woh sirf inhi do bricks se bani hogi — isliye hum inhe pehle name karte hain, koi symbol use karne se pehle.

PICTURE. Do bars dekho: chhota blue bar TLB search hai, lamba red bar ek memory access hai. Baad mein sab kuch inhi bars ka stack hoga.

Figure — TLB (translation lookaside buffer)

Step 2 — Har Access Ek Hi Tarah Shuru Hoti Hai: TLB Search Karo

KYA. Aage chahe kuch bhi ho, hardware kisi bhi memory reference par sabse pehle TLB search karta hai. Toh har access $t_{TLB}$ pay karti hai — koi exception nahi, abhi koi branch nahi.

YAHAN SE KYUN SHURU KAREIN? Kyunki TLB critical path par baitha hai: CPU physical frame tab tak nahi jaanta jab tak woh yeh na pooche "kya yeh translation cached hai?" Woh sawaal TLB search hai, aur ise poochna unconditionally $t_{TLB}$ cost karta hai. Ise cost ke shared "floor" banana ek key trick hai jo baad mein formula ko collapse karne deti hai.

PICTURE. Timeline ke saamne ek blue bar, road fork hone se pehle.

$cost so far = always paid: the search t_{TLB}$

Step 3 — Road Fork Hoti Hai: Hit vs Miss

KYA. Search ke baad, exactly do mein se ek cheez sach hoti hai. Ya toh translation TLB mein thi (ek hit), ya nahi thi (ek miss). Sirf yahi do outcomes hain, aur yeh mutually exclusive hain — isliye locality (Locality of Reference) matter karti hai: yeh decide karti hai ki hum kitni baar sasta branch lete hain.

FORMULA SE PEHLE FORK KYUN? Kyunki do branches alag amounts cost karti hain, hum ek single number tab tak nahi likh sakte jab tak dono branches ko apne aap price na kar lein. Toh hum fork draw karte hain, har side ko price karte hain, phir probability se weight karte hue re-merge karte hain.

PICTURE. Timeline do mein split hoti hai — ek green upper path (hit) aur ek red lower path (miss). Green path chhoti hai; red path ke beech mein ek bada walk block hai.

Step 4 — HIT Road (Green) Ko Price Karo

KYA. Hit par, TLB turant physical frame number (PFN) de deta hai. Page Table se kuch nahi padha jaata. Toh hum sirf ek real data access memory mein karte hain. Total green cost: search plus ek memory touch.

SIRF EK $t_{m}$ KYUN? Kyunki TLB ka maqsad hi page-table walk ko completely skip karna hai. Translation already known hai, toh ek maatra unavoidable memory work jo bacha hai woh hai actual data byte ko fetch karna jo tumne maanga tha — woh ek $t_{m}$ hai, lamba red bar.

PICTURE. Green road = ek chhota blue bar (search) + ek lamba bar (data). Koi walk block nahi.

$cost_{hit} = the search t_{TLB} + fetch the data t_{m}$

Step 5 — MISS Road (Red) Ko Price Karo: The Walk

KYA. Miss par, translation cached nahi hai, toh hardware ko PFN dhundhne ke liye page table walk karni padti hai. Parent note ne bataya tha ki ek walk $W$ memory accesses cost karti hai ( $W = 1$ single-level table ke liye, $W = L$ $L$ -level table ke liye). Walk ke baad PFN milne par, hum ek final data access karte hain. Toh miss road pay karti hai: search + walk + data.

EXTRA $W t_{m}$ KYUN? Page table ka har level DRAM mein rehta hai. Ek level padhna = ek $t_{m}$ . Ek $L$ -level table isliye $L$ memory reads cost karti hai data fetch karne se pehle. Yahi reason hai ki TLB exist karta hai — har access par $W t_{m}$ pay karne se bachne ke liye. (Note: miss ek Page Fault nahi hai — page memory mein hai, hum sirf map re-lookup kar rahe hain.)

PICTURE. Red road = chhota blue bar (search) + $W$ stacked memory bars (walk) + ek final lamba bar (data).

$cost_{miss} = the search t_{TLB} + walk: W page-table reads W t_{m} + fetch the data t_{m}$

Step 6 — Roads Ko Unki Probabilities Se Merge Karo

KYA. Ab hum dono prices ko ek expected number mein glue karte hain. Har road apni probability ke saath li jaati hai: green road $h$ fraction of time, red road $1 - h$ fraction of time. Expected (average) cost hai har price times kitni baar tum use pay karte ho.

MULTIPLY AUR ADD KYUN? Yeh sirf ek weighted average hai — ek honest tarika "ek typical access par, main kya pay karta hoon?" ka jawab dene ka. Agar $98%$ trips sasti hain aur $2%$ mehgi hain, toh tumhari average trip $0.98 \times (sasta) + 0.02 \times (mehnga)$ hai.

PICTURE. Do bars, ek $h$ se scale ki gayi (moti, green), ek $1 - h$ se scale ki gayi (patli, red), milaakar ek average bar banti hain.

$EMAT = hit fraction h green price (t_{TLB} + t_{m}) + miss fraction (1 - h) red price (t_{TLB} + W t_{m} + t_{m})$

KYA. Dono prices dekho: dono mein $t_{TLB}$ hai (Step 2 ne kaha tha ki search hamesha paid hoti hai) aur dono mein ek final $t_{m}$ hai (dono roads ek data fetch par khatam hoti hain). Yeh shared hain. Sirf yahi farq hai walk $W t_{m}$ , jo sirf red road par hai.

YEH SIMPLIFICATION KYUN? Kyunki common floor ko nikalna answer ko readable banata hai: yeh kehta hai "tum hamesha search + ek data access pay karte ho, aur phir walk penalty sirf miss fraction par." Algebraically:

$h (t_{TLB} + t_{m}) + (1 - h) (t_{TLB} + t_{m}) = (h + 1 - h) (t_{TLB} + t_{m}) = t_{TLB} + t_{m} .$

Weights $h$ aur $1 - h$ milaakar $1$ hote hain, toh shared part poora ek baar pay hota hai. Red road se sirf uska extra piece bachta hai, $1 - h$ se weighted:

$EMAT = always search t_{TLB} + always one data fetch t_{m} + walk, only on the miss fraction (1 - h) W t_{m}$

PICTURE. Ek tall stack: ek fixed floor ( $t_{TLB} + t_{m}$ ) jo kabhi nahi badlta, plus ek chhota red cap $(1 - h) W t_{m}$ jo $h \to 1$ hone par shrink hota hai.

Step 8 — Edge Cases (Limits Check Karo)

KYA. Ek formula jo tum trust karte ho use apni extremes pe survive karna chahiye. $h$ ko dono ends par aur $W$ ko upar push karo.

KYUN. Agar formula $h = 1$ ya $h = 0$ par nonsense deta toh hum jaante ki humne ise galat build kiya. Limits check karna hi woh tarika hai jisse tum khud ko prove karte ho ki picture sahi hai.

Perfect TLB, $h = 1$ : red cap gayab ho jaata hai, $(1 - 1) W t_{m} = 0$ , toh $EMAT = t_{TLB} + t_{m}$ . Har access green road jaisi sasti hai. Yeh dream scenario hai.
Useless TLB, $h = 0$ : cap poori hai, $(1 - 0) W t_{m} = W t_{m}$ , toh $EMAT = t_{TLB} + t_{m} + W t_{m}$ . Har access walk karti hai — exactly woh "no help" world jiske baare mein parent ne warn kiya tha.
Deeper page table, bada $W$ : red cap $W$ ke saath linearly badhta hai. x86-64 par, $W = 4$ , toh ek miss chaar guna zyada stings karta hai — aur yahi reason hai ki zyada $h$ itna worth hai.

PICTURE. Red cap $h$ ke against plot hua: ek straight line jo $W t_{m}$ (at $h = 0$ ) se gir kar $0$ (at $h = 1$ ) tak jaati hai, $W$ ki har value ke liye ek line.

Ek-Picture Summary

Upar sab kuch ek single diagram mein compress hota hai: search floor, fork, sirf red road par walk, aur merge jo ek fixed floor ke upar ek shrinking red cap chhodta hai.

Recall Feynman: plain words mein poora walkthrough

Jab bhi CPU ko memory chahiye, woh pehle apni pocket sticky-note (TLB) mein jhankta hai — woh peek hamesha thodi si time cost karti hai ( $t_{TLB}$ ). Phir road fork hoti hai. Agar note mein jawab hai (ek hit, jo zyaatar hota hai, fraction $h$ ), toh hum seedha data grab karne jaate hain — ek memory trip ( $t_{m}$ ). Agar note blank hai (ek miss, fraction $1 - h$ ), toh hum pehle office mein bade map tak sab rasta walk karte hain — woh $W$ memory trips hain — phir data grab karte hain. Kyunki dono roads mein hamesha pocket-peek hoti hai aur hamesha ek data grab par khatam hoti hain, woh do costs ek fixed floor hain jo tum hamesha pay karte ho. Sirf yeh badlta hai ki kya tumne expensive office walk li, aur yeh sirf miss fraction par hota hai. Toh average cost hai: floor ( $t_{TLB} + t_{m}$ ) plus walk penalty $W t_{m}$ jo scale down hai is se ki tum kitni rarely miss karte ho $(1 - h)$ . Note ko accha banao ( $h \to 1$ ) aur penalty zero ho jaati hai.

Related: Cache (memory hierarchy) mein same hit/miss-weighted-average idea use hota hai; ek Context Switch TLB ko cool karke $h$ ko achanak drop kar sakta hai.