Prefetching strategies: Foundations — Hinglish deep dive

5.4.17 · D1 · Hardware › Memory Hierarchy & Caches › Prefetching strategies

Is page pe kuch bhi assume nahi kiya gaya. Parent note padhne se pehle, tumhe us page ke har letter, ratio, aur picture se fluent hona chahiye. Hum har ek cheez ko ground up se build karenge, ek aisi order mein jahan har symbol ko use kiye jaane se pehle samjha jaaye.

0. Har cheez jis stage pe tiki hai: ek cache

Neeche di gayi picture dekho: CPU directly slow memory se baat karna avoid karta hai jab tak ho sake — pehle fast cache mein dekhta hai.

YE TOPIC KO KYUN CHAHIYE: prefetching ka poora kaam hai misses ko hits mein badalna. Agar tumhare dimaag mein "block", "hit", "miss" ke pictures nahi hain, toh baad ke metrics bekar hain. Yahi ground floor hai — dekho Cache Basics — Blocks and Locality.

1. Cycles mein time measure karna, aur memory itni slow kyun hai

YE TOPIC KO KYUN CHAHIYE: prefetching ki poori motivation yahi hai ki ek stall bahut bada hota hai. Baad ke har formula mein yahi poocha ja raha hai "yeh $400$ -cycle ke kitne freezes hum avoid kar sakte hain?"

2. "Tum jald chahoge" ke do prakar — locality

YE TOPIC KO KYUN CHAHIYE: locality hi wajah hai ki ek guess bilkul safal ho sakta hai. Next-line prefetching spatial locality par jiiti hai; correlation prefetching misses ke repeated (temporal) patterns par jiiti hai. Koi locality nahi → koi predictable future nahi → prefetching pure luck hai. Poori detail Spatial vs Temporal Locality mein hai.

3. Address, block number, aur stride — "kahan" ka arithmetic

"Stride" ko ek picture ki tarah socho — ek ruler jis pe evenly spaced ticks hain:

YE TOPIC KO KYUN CHAHIYE: next-line prefetch ek special case hai stride $= 1$ block (ek box aage). Stride prefetch ek general case hai, usually bytes mein express kiya jaata hai. Parent ka formula $a dd r + s t r i d e \cdot k$ bas "yahan se shuru karo, $k$ barabar steps lo stride size ke" hai — jahan $a dd r$ aur $s t r i d e$ ek hi unit (bytes) mein ho.

4. Degree $D$ aur multiplier $k$ — kitna aage daudo

YE TOPIC KO KYUN CHAHIYE: parent $D$ aur $k$ dono next-line aur stride strategies mein use karta hai. Agar tum $a dd r + s t r i d e \cdot k$ padhte ho bina yeh jaane ki $k$ sirf $1.. D$ count karta hai, toh formula mysterious lagta hai. Hai nahi — bas " $D$ evenly spaced steps aage lo."

5. Fractions jo ek prefetcher ko grade karte hain — $m$ , $c$ , $a$

Everything jo parent measure karta hai woh ek fraction hai: $0$ aur $1$ ke beech ek number jiska matlab hai "poore ka yeh hissa."

Neeche ke do pie charts "different wholes" ki baat visually samjhaate hain. Dekho ki har pie ka ek slice kis cheez ka hai: baayaan pie original misses ke set se kati gayi hai — uska green wedge ( $c = 0.6$ ) un misses ka hissa hai jo humne khatam kiye. Daayaan pie ek bilkul alag set se kati gayi hai, wo prefetches jo humne issue kiye — uska green wedge ( $a = 0.35$ ) wo hissa hai jo use hua, aur laal "wasted / pollution" slice woh bandwidth hai jo bekaar gayi. Dono greens comparable numbers nahi hain: wo alag sawaalon ke jawab dete hain kyunki wo alag circles ke slices hain. Isliye tumhe accuracy ko kabhi coverage formula mein multiply nahi karna chahiye.

YE TOPIC KO KYUN CHAHIYE: parent ka central formula $m_{e f f} = m (1 - c)$ tabhi samajh aata hai jab tum dekhte ho ki $c$ pehle se hi "jo misses actually eliminate hue" hain. Related metrics Cache Pollution and Replacement Policies ko feed karte hain (buri accuracy → pollution) aur pure page ki vocabulary hain.

6. Parent se pehle $m_{e f f} = m (1 - c)$ padhna

Ab hamare paas har piece hai. Formula ko plain words mein padho:

Agar $c = 0$ (prefetcher kuch nahi karta), $m_{e f f} = m$ . Agar $c = 1$ (har miss khatam karta hai), $m_{e f f} = 0$ . Beech ki har value ek seedhi line hai — koi hidden accuracy factor nahi, kyunki $c$ sirf unhe hi count karta hai jo kaam aaye. Dekho Average Memory Access Time (AMAT) jahan $m_{e f f}$ fit hota hai.

7. Symbols jo baad mein milenge (taaki naye na lagein jab milein)

Recall

$t_{hi t}$ aur $t_{mi ss}$ $t_{hi t}$ = cache hit ka time (chhota, ~1 cycle). $t_{mi ss}$ = miss ka extra penalty (~100 cycles). AMAT $= t_{hi t} + m_{e f f} \cdot t_{mi ss}$ : hit-probe hamesha pay karte ho, aur sirf survivors penalty pay karte hain.

Recall

$Δ m$ (pollution) Extra misses jo create hote hain jab ek bekaari prefetch ek still-needed block ko evict kar deti hai. Likha jaata hai $m_{e f f} = m (1 - c) + Δ m$ . Isliye ek inaccurate prefetcher cheezein badtar bana sakta hai.

Recall PC aur Reference Prediction Table

PC = program counter = us instruction ka address jo load kar raha hai. Table ko PC se index kiya jaata hai taaki alag loads (A[i] vs B[j]) apni alag stride histories rakkhein aur ek doosre ko corrupt na karein.

Recall MLP aur Out-of-Order

Memory-Level Parallelism (Memory-Level Parallelism (MLP)) = ek saath kaafi memory fetches in-flight hona. Out-of-Order Execution CPU ko stall ke baad bhi kaam karte rehne deta hai — woh useful computation jiske saath prefetch overlap karta hai. Compiler Optimizations — Loop Blocking software cousin hai jo access patterns ko prefetch-friendly banaata hai.

Prerequisite map

Equipment checklist

Test karo khud ko — sirf apna jawab bolne ke baad reveal karo.

Cache block (line) kya hai?

Ek fixed-size chunk (jaise 64 bytes) jise cache ek unit ke roop mein move karta hai — kabhi single byte nahi.

Hit vs miss?

Hit = data fast cache mein already hai. Miss = slow memory tak jaana padta hai aur stall karna padta hai.

Ek typical DRAM miss mein kitne CPU cycles lagte hain?

Lagbhag

400

cycles (~

100

ns at

4

GHz).

Spatial aur temporal locality mein kya fark hai?

Spatial = tum jald nearby addresses ko touch karoge; temporal = tum usi address ko dobara jald touch karoge.

Do addresses se stride kaise compute karte hain?

Baad wala address minus pehla address (number line pe gap).

Stride do units mein count ho sakta hai — kaun se?

Bytes (jaise

32

B) ya blocks (poore boxes aage); "stride = 1 block" matlab ek box, yaani ek byte-stride jo block size ke barabar ho.

Prefetch degree

D

kya count karta hai, aur

s t r i d e \cdot D

kya measure karta hai?

D

= fetch hone wali lines ki sankhya (ek count);

s t r i d e \cdot D

= bytes mein kitna aage tak sabse dur wala prefetch pahunchta hai (ek length).

a dd r + s t r i d e \cdot k

mein

k

ke liye kaun si values hain?

k = 1, 2, \dots, D

— yeh bas

D

prefetched lines mein se har ek ko naam deta hai.

Coverage

c

— numerator aur denominator?

(Jo misses hits mein badal gaye) ÷ (original misses).

Accuracy

a

— numerator aur denominator?

(Jo prefetches actually use hue) ÷ (prefetches issued).

Accuracy ko

m_{e f f} = m (1 - c)

mein multiply kyun nahi kar sakte?

Kyunki

c

pehle se sirf wahi misses count karta hai jo truly eliminate hue — accuracy ek alag bandwidth metric hai ek alag denominator ke upar.

(1 - c)

ko words mein padho.

Original misses ka wo fraction jo survive karta hai (abhi bhi miss hai).

Δ m

kya hai?

Extra misses jo pollution se create hote hain jab ek bekaari prefetch ek still-needed block ko evict kar deti hai.