Instruction-level vs thread-level parallelism: Visual walkthrough

6.1.2 · D2 · Hardware › Parallelism & Multicore › Instruction-level vs thread-level parallelism

Parent note ne tumhe do formulas di thi jo almost identical lagti hain — lekin unhe likhne se pehle bhi, notice karo ki woh symbols se bhari hain: ek $f$ , ek $n$ , ek $p$ , ek $N$ . Yeh page un mein se ek bhi use karne se mana karta hai jab tak hum ne use draw nahi kar liya. Toh hum ek blank chalkboard aur chalk ki ek dandi ke saath shuru karte hain, aur har letter ko earn karte hain.

Akhir mein tum clearly dekhoge ki "ek core ko cycle mein zyada kaam karwao" (ILP) aur "zyada cores lagao" (TLP) dono same shape ki equation mein kyun collapse ho jaate hain.

Hum parent Instruction-level vs thread-level parallelism discussion ko extend kar rahe hain, aur dono formulas ki jadd Amdahl's Law hai.

Step 1 — "Work" kya hai? Instructions ki bar draw karo

WHAT. Kisi bhi cheez ko speed up karne se pehle, hume us cheez ki ek picture chahiye jo hum speed up kar rahe hain. Ek program ko ek bar mano jiska length total kaam ki matra hai. Kaam ke chhote pieces ki sankhya ko hum $I$ kahenge — socho " $I$ instructions", ek chalk ka ek daana har instruction ke liye.

WHY. Speedup hamesha do times ka ratio hota hai: kaam kitna time lega pehle vs. baad mein. Time measure karne ke liye pehle kaam ki matra measure karni hogi. Length $I$ wala ek bar "kitna karna hai" ka sabse simple aur honest picture hai.

PICTURE. Neeche ka bar ek program hai. Har tick kaam ki ek unit hai. Abhi kuch bhi parallel nahi hai — hum sirf raw material ko naam de rahe hain.

Figure — Instruction-level vs thread-level parallelism

Is stage par, agar hum sab kuch ek piece at a time karte, toh time bas

$T_{original} = I \cdot (time per piece)$

Hum time ko "ek piece" ki units mein measure karenge, toh hum simply likh sakte hain $T_{original} = I$ . Abhi tak har symbol earned hai: $I$ ek count hai jo tum literally bar length ke roop mein dekh sakte ho.

Step 2 — Bar ko split karo: jo part WAIT karna PADEGA, aur jo part SPREAD ho SAKTA HAI

WHAT. Bar ko do shades mein colour karo. Ek shade woh kaam hai jo stuck hai aur sequential rehna padega — piece 2 shuru nahi ho sakta jab tak piece 1 khatam na ho. Doosra shade woh kaam hai jiske pieces independent hain — unhe ek doosre ke answers ki zaroorat nahi.

WHY. Parallelism ke baare mein baat karne ka yahi ek honest tarika hai. Parallelism sirf independent pieces ko help karta hai aur stuck pieces ko bilkul bhi help nahi karta. Toh arithmetic karne se pehle hume unhe alag karna hoga. Yeh single split dono formulas ka beej hai.

PICTURE. Pink chunk stuck (serial) part hai. Blue chunk free (parallelizable) part hai.

Jo fraction free hai use hum ek single letter se naam dete hain. ILP world mein hum ise $f$ kehte hain; TLP world mein hum ise $p$ kehte hain. Dono ek hi tarah ki cheez mean karte hain — "kaunsa fraction spread out ho sakta hai" — lekin kisi piece ke stuck hone ki wajah alag hoti hai (hum Step 6 mein wapas aayenge).

Toh blue length hai $f \cdot I$ aur pink length hai $(1 - f) \cdot I$ . Picture check karo: blue + pink $= f \cdot I + (1 - f) \cdot I = I$ . Kuch bhi nahi gaya.

Step 3 — "Spreading" se time par actually kya hota hai? Width $n$ (ya $N$ ) introduce karo

WHAT. Ab hum blue (free) part ko kai pieces side by side run karne dete hain. Ek instant mein hum jitne pieces run kar sakte hain woh width hai. ILP mein woh width $n$ hai, yaani instructions finished per cycle (from superscalar issue). TLP mein woh width $N$ hai, yaani cores ki sankhya.

WHY. Ek saath $n$ pieces run karne ka matlab hai blue part pehle wale time ka $1/ n$ mein khatam ho jaata hai. Yeh parallelism ka pura payoff hai, aur humhe "kitna wide ja sakte hain" ke liye ek symbol chahiye. Alag sawaal, alag letter — lekin same geometric move: blue bar ko horizontally width se squeeze karo.

PICTURE. Sirf blue part dekho: uski length $f \cdot I$ ko $n$ stacked lanes mein fold kiya jaata hai, toh uska time $\frac{f \cdot I}{n}$ tak shrink ho jaata hai. Pink part untouched hai — uske paas fold karne ke liye koi lanes nahi hain.

Step 4 — Nayi time add karo

WHAT. Nayi total time bas pink time + squashed-blue time hai.

WHY. Do coloured segments timeline par ek ke baad ek run hote hain: pehle pura pink (serial) segment, aur uske baad hi blue (parallel) segment. Toh unke durations simply add hote hain. Kahin bhi single "overlap" sirf blue segment ke andar hai — $n$ free pieces side by side run hote hain, exactly isne hi Step 3 mein uski length $\frac{f I}{n}$ tak shrink ki. Pink aur blue ek doosre se kabhi overlap nahi karte. Koi teesra piece nahi hai; Step 2 ne prove kiya tha ki blue + pink pura bar hai.

PICTURE. Do segments end to end: pura pink $(1 - f) I$ , phir shrunken blue $\frac{f I}{n}$ .

T_{I L P} = pink: serial work, full length (1 - f) \cdot I + blue: parallel work, squashed by width n \frac{f \cdot I}{n}

Har term ko wahan padhho jahan woh baitha hai:

$(1 - f) \cdot I$ — pink fraction $(1 - f)$ times total pieces $I$ : woh part jise help nahi kiya ja sakta tha.
$\frac{f \cdot I}{n}$ — blue fraction $f$ times $I$ (free pieces), width $n$ (lanes) se divided.

Yahi exact result hai jo parent note apne step 4 mein list karta hai. Hum ne ise ab ek coloured bar se build kar liya hai.

Step 5 — Speedup ratio banao (the punchline)

WHAT. Speedup old time ÷ new time hai. Step 1 ka $T_{original} = I$ ko Step 4 ke $T_{I L P}$ se divide karo.

WHY. "Kitne guna faster?" literally new duration ki units mein measured old duration hai. Woh ratio hi hai jo sabhi speedup ke roop mein quote karte hain.

PICTURE. Do bars stacked: lamba original bar chhote naye bar ke upar. Speedup kitne naye-bars ek purane-bar mein fit hote hain hai.

S_{I L P} = \frac{T _{original}}{T _{I L P}} = \frac{I}{( 1 - f ) I + \frac{f I}{n}}

Ab magic cancellation. Har term mein $I$ ka factor hai — kyunki humne ek ratio pucha, kaam ki absolute matra matter nahi karti. Top aur bottom dono ko $I$ se divide karo:

S_{I L P} = \frac{1}{( 1 - f ) + \frac{f}{n}}

Top par $1$ old time in $I$ -units hai.
$(1 - f)$ leftover pink time hai (kabhi shrink nahi hota).
$\frac{f}{n}$ $n$ -way squashing ke baad blue time hai.

Letters swap karo $f \to p$ , $n \to N$ aur tumhare paas twin hai

S_{T L P} = \frac{1}{( 1 - p ) + \frac{p}{N}}

bina kisi extra kaam ke — derivation ne kabhi care nahi ki koi piece free kyun tha. Isliye dono formulas twins hain. Dono Amdahl's Law hain.

Step 6 — Same skeleton, alag bones: $f$ aur $p$ same number kyun NAHI hain

WHAT. Formulas identical hain, lekin jo value tum plug in karte ho woh alag physics se aati hai. Hum dikhate hain ki har world mein ek piece ko "pink" kya banata hai.

WHY. Agar tum yeh bhool gaye toh sahi formula ke saath bhi galat speedup predict karoge. Parent ka linked-list example (ILP $\approx 1.08 \times$ , TLP $\approx 3.33 \times$ same list ke liye) exactly yahi gap hai.

PICTURE. Left board: ILP pinkness instruction dependencies se aati hai — ek load-to-use chain, ek branch, ek pipeline hazard. Right board: TLP pinkness algorithm structure se aati hai — initialization, final reduction, thread spawn/join.

Step 7 — Degenerate cases: corners ko pin down karo

WHAT. Formula ko uski extremes par test karo taaki koi reader kabhi surprise na paye.

WHY. Jis law par tum trust karte ho use edges par sane answers dene chahiye. Contract rule: har case cover karo.

PICTURE. Speedup curve $S$ vs width, "free" ki kuch values ke liye drawn, dikhate hue ki woh kahan flat ho jaata hai.

free $= 0$ (sab pink): $S = \frac{1}{1 + 0} = 1$ . Koi speedup nahi, chahe width kuch bhi ho. Intuition se match karta hai: ek fully serial chain ko help nahi kiya ja sakta.
free $= 1$ (sab blue): $S = \frac{1}{0 + 1/ width} = width$ . Perfect linear scaling — parent note mein embarrassingly parallel image strips.
width $\to \infty$ : $S \to \frac{1}{1 - free}$ . Famous ceiling: infinite cores bhi yeh beat nahi kar sakte. $p = 0.99$ ke saath ceiling $1/0.01 = 100 \times$ hai, bas.
width $= 1$ : $S = \frac{1}{( 1 - free ) + free} = 1$ . Ek lane ka matlab hai koi lane nahi — sanity check pass.

The one-picture summary

Upar sab kuch, compressed: ek work bar, pink/blue split kiya, blue ko width se squash kiya, ratio liya, $I$ cancel hua, ceiling reveal hua.

Recall Feynman retelling — aise batao jaise kisi dost ko batate

Ek kaam ko kagaz ki ek strip ki tarah socho. Use colour karo: pink bit woh kaam hai jo order mein karna padta hai (har step pichle wale ka intezaar karta hai), blue bit woh kaam hai jiske pieces ko ek doosre ki koi parwah nahi. Ab helpers ko blue pieces pakadne do — $n$ helpers ke saath blue strip $n$ guna faster khatam hoti hai, lekin pink strip kabhi speed up nahi hoti, kyunki tum step 1 se pehle step 2 nahi kar sakte. Shortened strip ko end to end rakho: pink (full) phir blue-over- $n$ — do colours ek ke baad ek run hote hain, aur side-by-side action sirf blue part ke andar hoti hai. Pucho "kitne guna faster?" — woh old length over new length hai. Jab tum divide karte ho, kaam ki total matra cancel ho jaati hai (ek ratio ko job ki size se koi fark nahi padta), bas $S = 1/ ((1 - free) + free / width)$ bachta hai. ILP aur TLP is same box mein plug in hote hain — ILP ka "free" woh instructions hain jinhe core independent paata hai, TLP ka "free" woh chunks hain jinhe programmer ne split kiya. Aur chahe tum kitne bhi helpers throw karo, tum kabhi $1/ (1 - free)$ ko beat nahi kar sakte, kyunki pink part abhi bhi wahan baitha hai.

Recall Quick self-test

Jab sab kuch parallel ho aur 8 lanes hon, toh speedup kya hai? ::: $S = 1/ (0 + 1/8) = 8 \times$ (perfect linear). 90% parallel aur infinite lanes ke saath, ceiling kya hai? ::: $1/ (1 - 0.9) = 10 \times$ . Total instruction count $I$ final formula se kyun gaayab ho jaata hai? ::: Kyunki speedup do times ka ratio hai; $I$ dono mein factor out ho jaata hai aur cancel ho jaata hai. Same list, TLP speedup ILP se yahan bada kyun hai? ::: "Free" fraction alag tarah se measure hota hai — instruction dependencies $f$ ko cripple kar deti hain jabki algorithm abhi bhi kuch thread-level split allow karta hai, toh $p > f$ .