TLB (translation lookaside buffer): Exercises — Hinglish deep dive

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

Poore document mein yahi reference numbers use hote hain (jab tak koi problem override na kare):

Koi bhi problem shuru karne se pehle, us formula ka matlab samjho. Neeche ki tasveer EMAT ko teen stacked blocks mein todti hai: halka lavender block $t_{TLB}$ jo aap har access par dete ho (TLB search karte waqt), butter block $t_{m}$ jo aap har access par bhi dete ho (final data read), aur patla coral block $(1 - h) W t_{m}$ — miss penalty — jo sirf miss fraction ke liye present hai. Dhyan do ki coral block $h \to 1$ hone par zero ki taraf sirakta hai: woh visual shrinking hi poori wajah hai ki TLB kyon help karta hai.

Figure — TLB (translation lookaside buffer)

Har access ko yeh bhi decide karna padta hai ki hit hai ya miss, aur miss khatam nahi hoti — yeh clean fill mein khatam ho sakti hai, ya page fault mein agar page bilkul memory mein nahi hai. Woh branching ek flowchart mein sabse asaan follow hoti hai:

Is flowchart ko yaad rakho: valid-bit branch (E) woh case hai jise zyaadatar students bhool jaate hain, aur yahi Exercise 3.4 ka subject hai.

Level 1 — Recognition

Exercise 1.1 — Splitting an address

Ek system $P = 4 KiB$ pages aur 32-bit virtual addresses use karta hai. Virtual address 0x00012ABC ke liye batao (a) kitne offset bits hain, (b) offset ki value kya hai, (c) VPN kya hai.

Neeche ki bit-field tasveer exactly dikhati hai ki cut kahan padti hai: upar ke 20 bits VPN hain (lavender), neeche ke 12 bits offset hain (mint), aur vertical dashed line bit 11/12 par boundary hai.

Recall Solution 1.1

(a) $4 KiB = 2^{12}$ bytes, isliye offset ko page ke andar har byte name karne ke liye 12 bits chahiye. (b) Offset low 12 bits hai. 0x00012ABC ke bottom 3 hex digits ABC hain — lekin 3 hex digits = 12 bits exactly, isliye offset = 0xABC. (c) VPN bit 11 ke upar ki sab cheez hai → high 20 bits = 0x00012. Aisa kyun split karte hain? Paging kisi byte ko uske page ke andar kabhi move nahi karta, isliye low $lo g_{2} P$ bits bina translate hue pass hote hain; sirf page number ko lookup kiya jaata hai.

Exercise 1.2 — What lives in a TLB entry?

Inme se kaunse ek single TLB entry ke andar belong karte hain? (VPN, PFN, page offset, valid bit, permission bits, ASID tag, pure page ka data.)

Recall Solution 1.2

Ek TLB entry mein store hota hai: VPN (tag/key), PFN (answer), ek valid bit, permission bits (read/write/execute, user/kernel), aur — un designs par jo flush avoid karte hain — ek ASID (Address-Space Identifier) tag jo batata hai ki mapping kis process ki hai. Isme nahi hota page offset (woh address se hi aata hai, untranslated) aur isme nahi hota page ka data (woh cache/DRAM mein hota hai, TLB mein nahi). ASID field kyun matter karta hai: iske bina, process A ke liye VPN 0x5 aur process B ke liye VPN 0x5 ek dusre se alag nahi ho paate, jo har Context Switch par full flush forced karta hai. Yeh tag dono entries ko saath-saath rehne deta hai (Exercise 4.2 mein use hota hai).

Level 2 — Application

Exercise 2.1 — Build the physical address

TLB mein VPN 0x00012 → PFN 0x0037 diya hai, $P = 4 KiB$ hai, VA = 0x00012ABC ko physical address mein translate karo.

Recall Solution 2.1

Split: offset = 0xABC, VPN = 0x00012 (Exercise 1.1 se).
Lookup: VPN 0x00012 present hai → hit, PFN = 0x0037.
PA banao: $PA = (PFN ≪ 12) ∣ offset$ . 0x0037 ko left 12 bits shift karne par = 0x00037000 (teen hex zeros append = 12 bits). 0xABC ke saath OR karo → PA = 0x00037ABC. 12 se shift kyun? PFN poori 4KiB frame name karta hai; uska base byte address $PFN \times P = PFN \times 2^{12}$ hai, jo exactly 12 se left shift hai.

Exercise 2.2 — EMAT plug-in

$t_{TLB} = 1$ ns, $t_{m} = 100$ ns, single-level walk ( $W = 1$ ), hit rate $h = 0.95$ . EMAT nikalo.

Recall Solution 2.2

Extra miss cost $= (1 - h) W t_{m} = (0.05) (1) (100) = 5$ ns. $EMAT = t_{TLB} + t_{m} + extra = 1 + 100 + 5 = 106 ns$ . Yeh shape kyun hai? Aap hamesha TLB search karte ho ( $t_{TLB}$ ) aur hamesha ek final data read karte ho ( $t_{m}$ ); walk ek maatra extra cost hai aur yeh sirf us $5%$ accesses par hoti hai jo miss karte hain. Yeh exactly page ke top se woh teen-block picture hai jisme $h = 0.95$ hai.

Level 3 — Analysis

Exercise 3.1 — Multi-level walk zyada hurt karta hai

Same system jaise 2.2 ( $t_{TLB} = 1$ , $t_{m} = 100$ ) lekin 4-level page table ( $W = 4$ ) aur $h = 0.98$ . Usi hit rate par single-level case se EMAT compare karo.

Recall Solution 3.1

Single-level ( $W = 1$ ): extra $= (0.02) (1) (100) = 2$ → EMAT $= 1 + 100 + 2 = 103$ ns. Four-level ( $W = 4$ ): extra $= (0.02) (4) (100) = 8$ → EMAT $= 1 + 100 + 8 = 109 ns$ . Analysis: miss fraction identical hai (2%), lekin ab har miss 4× ka walk work cost karta hai. Isliye deeper page tables penalty per miss multiply karte hain, aur yahi wajah hai ki x86-64 par high $h$ zyada matter karta hai.

Exercise 3.2 — Required hit rate ke liye solve karo

Tum chahte ho ki $EMAT \leq 105$ ns ho jisme $t_{TLB} = 1$ , $t_{m} = 100$ , $W = 1$ . Tumhe minimum hit rate $h$ kitni chahiye?

Recall Solution 3.2

Set up: $1 + 100 + (1 - h) (1) (100) \leq 105$ . $\Rightarrow 101 + 100 (1 - h) \leq 105$ $\Rightarrow 100 (1 - h) \leq 4$ $\Rightarrow 1 - h \leq 0.04 \Rightarrow h \geq 0.96$ . Minimum hit rate = 96%. Formula ko invert kyun kiya? EMAT badhta hai jab $h$ girta hai; constraint miss fraction $(1 - h)$ par ek inequality hai, isliye hum use isolate karte hain aur boundary read karte hain.

Exercise 3.3 — No TLB ke muqable mein Speedup

$h = 0.98$ , $t_{m} = 100$ , $t_{TLB} = 1$ , single-level walk ke saath, ek aisi machine se compare karo jisme TLB nahi hai (har access ek page-table read + ek data read $= 2 t_{m}$ deta hai). Speedup kya hai?

Recall Solution 3.3

No TLB: har access $= 2 t_{m} = 200$ ns. TLB ke saath: $EMAT = 1 + 100 + (0.02) (100) = 103$ ns. Speedup $= 200/103 \approx 1.94 \times$ . Iska matlab: locality accesses ko kuch pages par concentrate karti hai → high $h$ → TLB yahan access time almost aadha kar deta hai.

Exercise 3.4 — Miss jo sirf walk nahi hoti (valid-bit edge case)

Flowchart ki branch E follow karo. Ek memory access TLB mein miss karti hai, isliye hardware page table walk karta hai — aur PTE ka valid bit = 0 pata hai, matlab page physical memory mein resident nahi hai. Times: $t_{TLB} = 1$ ns, single walk $t_{m} = 100$ ns ( $W = 1$ ), aur ek Page Fault ko disk se service karne mein $t_{fault} = 5, 000, 000$ ns (5 ms) lagta hai. OS ke page load karne ke baad woh dobara walk karta hai (aur $100$ ns) aur data read karta hai ( $100$ ns). Is ek access ka total time kya hai, aur yeh ek ordinary TLB hit ( $t_{TLB} + t_{m} = 101$ ns) se kitne times bada hai?

Recall Solution 3.4

Flowchart branch by branch neeche chalo:

TLB search: $t_{TLB} = 1$ ns.
Pehla walk valid bit = 0 pata hai: $W t_{m} = 100$ ns.
Page fault disk par (branch E → G → H): $t_{fault} = 5, 000, 000$ ns.
Page resident hone ke baad re-walk: $100$ ns.
Data read: $t_{m} = 100$ ns.

Total $= 1 + 100 + 5, 000, 000 + 100 + 100 = 5, 000, 301 ns$ . Hit se ratio $= 5, 000, 301/101 \approx 49, 508 \times$ . Baat yeh hai: TLB miss aur page fault alag quadrants hain. Zyaadatar misses step 2 par ruk jaati hain (valid bit = 1 → clean fill, ~100ns). Valid-bit-zero branch woh rare, catastrophic wali hai — paanch million nanoseconds — kyunki woh disk hit karti hai. EMAT formula sirf common (resident) miss model karta hai; page faults ek alag, bahut rarer term hain.

Level 4 — Synthesis

Exercise 4.1 — Two-level TLB EMAT

Ek design mein L1 TLB (search $t_{1} = 1$ ns) aur L2 TLB (search $t_{2} = 4$ ns) hai. L1 hit rate $h_{1} = 0.90$ hai. L1 misses mein se, L2 $h_{2} = 0.80$ catch karta hai. L2 miss ek full walk $W t_{m}$ trigger karta hai jisme $W = 4$ , $t_{m} = 100$ hai. Kisi bhi access par aap ek final data read $t_{m}$ bhi dete ho. L1 hit hone par $t_{2}$ ignore karo (parallel/short-circuit). EMAT compute karo.

Recall Solution 4.1

Cases ke hisaab se cost banao, phir hamesha final data read $t_{m} = 100$ jodo:

L1 hit (prob $0.90$ ): translation cost $= t_{1} = 1$ .
L1 miss, L2 hit (prob $0.10 \times 0.80 = 0.08$ ): cost $= t_{1} + t_{2} = 1 + 4 = 5$ .
L1 miss, L2 miss (prob $0.10 \times 0.20 = 0.02$ ): cost $= t_{1} + t_{2} + W t_{m} = 1 + 4 + 400 = 405$ .

Expected translation cost: $0.90 (1) + 0.08 (5) + 0.02 (405) = 0.90 + 0.40 + 8.10 = 9.40 ns .$ Data read jodo: $EMAT = 9.40 + 100 = 109.4 ns$ . Do levels kyun? Ek chhota fast L1 common case sasta rakhta hai; ek bada L2 zyaadatar L1 misses ko 400ns walk diye bina rescue karta hai — wahi layering idea jaise data caches mein hai.

Exercise 4.2 — Context switch ke baad Flush vs. ASID cost

Ek Context Switch par, design A TLB flush karta hai; design B ASIDs use karta hai — Exercise 1.2 ka Address-Space Identifier field jo har entry ko uske owning process se tag karta hai, isliye koi flush zaroorat nahi. Switch ke baad, returning process $N = 1000$ accesses karta hai. ASIDs ke saath uska warm hit rate $h = 0.98$ hai. Flush ke baad TLB cold hai: in $1000$ accesses ke liye average hit rate $h^{'} = 0.85$ tak gir jaati hai (refill hote waqt miss storm). $t_{TLB} = 1$ , $t_{m} = 100$ , $W = 1$ use karte hue, in 1000 accesses mein ASID flush ke muqable mein kitna total time bachata hai?

Recall Solution 4.2

Per-access EMAT:

ASID: $1 + 100 + (0.02) (100) = 103$ ns.
Flush: $1 + 100 + (0.15) (100) = 116$ ns. Over $N = 1000$ accesses:
ASID total $= 1000 \times 103 = 103, 000$ ns.
Flush total $= 1000 \times 116 = 116, 000$ ns. Savings $= 116, 000 - 103, 000 = 13, 000$ ns $= 13 μ s$ per switch window. Synthesis point: flush ka nuksan cold-start miss storm hai — cost flush instruction khud nahi hai balki uske baad aane wale kaafi saare walks hain. ASID tag entries ko switch survive karne deta hai, refill avoid karta hai.

Level 5 — Mastery

Exercise 5.1 — When is a bigger TLB actually worse?

Ek chhote TLB ka $t_{TLB} = 1$ ns aur hit rate $h_{S} = 0.95$ hai. Ek bada TLB hit rate $h_{B} = 0.99$ tak badhata hai lekin, har access ke critical path par hone ki wajah se, uska search time $t_{TLB} = 2$ ns ho jaata hai. $t_{m} = 100$ , $W = 1$ ke saath, EMAT par kaun jeetta hai?

Recall Solution 5.1

Small: $EMAT_{S} = 1 + 100 + (0.05) (100) = 106$ ns. Big: $EMAT_{B} = 2 + 100 + (0.01) (100) = 103$ ns. Big TLB yahan jeetta hai (103 < 106). Lekin tension notice karo: bade TLB ne walk term mein $4$ ns bachaye par $t_{TLB}$ mein $1$ ns har single access par add kiya. Agar uska search time, maano, $6$ ns ho jaata, toh woh haar jaata: $6 + 100 + 1 = 107 > 106$ . Mastery point: $t_{TLB}$ mein add kiya gaya har nanosecond unconditionally pay hota hai; walk savings sirf miss fraction par pay hoti hain. Bada tabhi jeetta hai jab $Δ t_{TLB} < (h_{B} - h_{S}) W t_{m}$ .

Exercise 5.2 — Break-even search-time penalty derive karo

5.1 ko generalise karo. Ek bada TLB hit rate $h_{S}$ se $h_{B}$ tak improve karta hai lekin search time mein $Δ$ ns add karta hai. Woh sabse bada $Δ$ derive karo jis par bada TLB abhi bhi help karta hai, $h_{S}, h_{B}, W, t_{m}$ ke terms mein. $h_{S} = 0.95, h_{B} = 0.99, W = 4, t_{m} = 100$ ke liye evaluate karo.

Recall Solution 5.2

Break-even wahan hai jahan dono EMATs equal hain: $(t_{TLB} + Δ) + t_{m} + (1 - h_{B}) W t_{m} = t_{TLB} + t_{m} + (1 - h_{S}) W t_{m} .$ Common $t_{TLB} + t_{m}$ cancel karo: $Δ + (1 - h_{B}) W t_{m} = (1 - h_{S}) W t_{m}$ $Δ_{m a x} = (h_{B} - h_{S}) W t_{m}$ Evaluate: $Δ_{m a x} = (0.99 - 0.95) (4) (100) = (0.04) (400) = 16 ns$ . Interpretation: deep 4-level walk ke saath, walk penalty badi hai, isliye tum bade TLB ke fayde khatam hone se pehle $16$ ns tak extra search time afford kar sakte ho. Deeper page tables → bade TLBs ke liye zyada headroom. Yahi exact reason hai ki real CPUs deep page tables ke saath multi-level TLBs pair karte hain.

Exercises 5.1 aur 5.2 mein trade-off ek graph ke roop mein sabse asaan dikhta hai. Neeche ki figure small-TLB EMAT (ek flat line — yeh kabhi change nahi hoti) ko big-TLB EMAT (jo uske extra search time $Δ$ badhne par rise karti hai) ke against plot karti hai. Exactly wahan read karo jahan rising line flat line cross karti hai: woh crossing $Δ_{m a x}$ hai, aur uske left ki shaded region wahan hai jahan bada TLB jeetta hai.