Warp divergence penalties: Visual walkthrough — Hinglish deep dive

6.2.11 · D2 · Hardware › GPU Architecture › Warp divergence penalties

Yeh page Warp divergence penalties ka central result bilkul zero se build karta hai. End tak tumhe dikhega ki ek warp jo alag-alag paths mein split hota hai woh un paths ka sum kyun bharta hai, max kyun nahi — aur raaste mein har symbol tumne khud earn kiya hoga.

Hum sirf teen ideas pe depend karte hain: SIMT execution model (ek instruction, bahut saare threads), warp scheduling (warps kaise baari-baari lete hain), aur baad mein CPU-style branch prediction ka ek zikr — yeh dikhane ke liye ki GPUs kya nahi karte.

Step 1 — Warp actually kya hota hai: ek string pe 32 puppets

KYA HAI. Ek warp 32 threads ka ek bundle hai jo ek hi single instruction pointer share karta hai. Ek instruction decoder hota hai; jo bhi woh padhe, sab 32 threads ko same instruction same clock tick pe milti hai.

YEH KYUN PEHLE. Baad ki har penalty ek fact se aati hai: 32 threads ek hi time pe alag-alag instructions nahi padh sakte. Agar yeh feel nahi hua, toh baad ka kuch bhi samajh nahi aayega. Toh pehle hum ise picture karte hain.

PICTURE. Figure dekho: ek decoder (puppeteer) ek string kheenchta hai, aur saare 32 puppets ek hi haath uthate hain. Puppet 5 ke liye possible hi nahi ki woh is tick pe alag haath utha sake — string shared hai.

Step 2 — Time measure hota hai instruction cycles mein

KYA HAI. Hum cost instruction cycles mein measure karte hain: ek cycle = decoder ka ek instruction warp ko issue karna. Agar ek code path $n$ instructions ki seedhi list hai bina branches ke, toh poore warp ko $n$ cycles lagenge — saare 32 lanes saath khatam karte hain.

YEH UNIT KYUN. Hamare paas costs add karne ke liye ek currency chahiye. Cycles perfect hain kyunki SIMT mein ek issued instruction saare 32 lanes ko ek saath serve karti hai, isliye "cost" is baat pe depend nahi karti ki kitne lanes active hain — sirf is baat pe ki kitni instructions issue hoti hain.

PICTURE. $n$ boxes ka ek seedha blue pipe; 32 parallel lanes iske through side by side flow karti hain, saath enter aur saath nikle. Cost pipe ki length hai, lanes ki ginti nahi.

Step 3 — Fork: jab lanes agree nahi karte tab kya hota hai

KYA HAI. Ek branch (if, while, for) har lane se ek yes/no sawaal karta hai. Jab kuch lanes true bolte hain aur kuch false, toh hame warp divergence milta hai. Lanes do alag instruction streams run karna chahte hain — lekin Step 1 ne ek tick pe yeh forbid kiya hua hai.

YEH CRISIS KYUN HAI. Yahi woh exact moment hai jab shared string parallelism ka illusion tod deti hai. Ab hame decide karna hai ki hardware kaise cope karta hai, kyunki physically dono streams ek saath nahi ho sakte.

PICTURE. Ek incoming warp ek diamond (branch) se takrata hai. Active mask split hoti hai: kuch lanes green ho jaate hain (condition true), baki grey. Diamond se do pipes nikalte hain — lekin decoder ek waqt mein sirf ek ko feed kar sakta hai.

Step 4 — Path A run karna: aadha warp kaam karta hai, aadha idle jalता hai

KYA HAI. Hardware path A choose karta hai. Woh active mask set karta hai taaki sirf true lanes results rakhe; false lanes mask off hain. Woh path A ki saari instructions issue karta hai. Masked lanes phir bhi har instruction receive karti hain — bas output discard kar deti hain.

YEH IDLE LANES KO ISSUE KYUN KARNA PADTA HAI. Ek decoder hai (Step 1). Path A ki true-lanes ko feed karne ke liye, decoder path A ki instructions poore warp ko issue karta hai; false-lanes ke paas zero mask ke saath inhe jhhelne ke siva koi option nahi. "Sirf kuch lanes ke liye" decode nahi ho sakta.

PICTURE. Path A ka pipe (length $T_{A}$ ) jisme green lanes flow kar rahi hain aur grey lanes beside park hain, time waste kar rahi hain. Side mein clock $T_{A}$ cycles tick karta hai.

Step 5 — Path B run karna, phir add karna: sum appear hota hai

KYA HAI. Stack pop hota hai. Ab mask flip hoti hai: false lanes (path B) light up ho jaate hain, true lanes grey ho jaate hain. Decoder path B ki saari instructions issue karta hai, $T_{B}$ cycles lagti hain. Dono khatam hone ke baad hi reconverge hota hai.

YEH DO COSTS ADD KYUN HOTE HAIN. Path A aur path B same decoder pe alag-alag times pe chale. Ek bhi tick aisa nahi tha jab A ki aur B ki instructions dono issue ki gayi hon. Isliye wall-clock time A ke cycles aur uske baad B ke cycles hai — addition, max nahi.

PICTURE. A-pipe aur B-pipe ek single timeline pe end-to-end draw kiye hain. Total length clearly $T_{A} + T_{B}$ hai, jahan full green mask return hoti hai wahan reconverge marker hai.

Step 6 — Ye asliyat mein kya hona chahiye tha: max, aur efficiency ratio

KYA HAI. Socho koi divergence nahi — saare 32 lanes ne same path liya. Toh sirf ek pipe issue hoti hai, aur uski cost sirf us pipe ki length hai. Best-case cost jab kai paths ho sakte hain woh sabse lamba ek hai, $max (T_{1}, \dots, T_{k})$ , kyunki ideal parallel machine mein paths time mein overlap hote.

MAX SE COMPARE KYUN. Penalty measure karne ke liye ek yardstick chahiye: "yeh kitni fast ho sakti thi agar lanes perfectly overlap karti?" Woh ideal saare pipes overlap karta hai, isliye finish time sabse slow se set hoti hai — max. Divide karne se clean efficiency fraction milta hai.

PICTURE. Left: ideal — saare pipes parallel stacked, $max$ pe khatam. Right: reality — wahi pipes end-to-end rakhe, sum pe khatam. Do bar lengths ka ratio efficiency hai.

Step 7 — Edge case: worst case hai 32 distinct paths ( $k = 32$ )

KYA HAI. Branch ko uski cruelest limit tak push karo: 32 lanes mein se har ek alag path leta hai, har path $n$ instructions lamba. Tab $k = 32$ aur har $T_{i} = n$ .

YEH KYUN COVER KARO. Reader ko kabhi koi unexplained scenario nahi milna chahiye. Famous "GPUs up to $32 \times$ lose kar sakte hain" number exactly yahan rehta hai — aur seedha hamare sum formula se nikalata hai.

PICTURE. Battees identical pipes, har ek length $n$ , end-to-end $32 n$ length ki ek lambi chain mein stacked. Uske paas, ideal single pipe length $n$ ki.

Step 8 — Degenerate cases: koi divergence nahi, aur lopsided divergence

KYA HAI. Do boundary scenarios jo logon ko surprise karte hain.

(a) Koi divergence nahi ( $k = 1$ ). Saare 32 lanes agree karte hain. Ek pipe, poore time full mask. $T_{diverged} = T_{1} = max$ , efficiency $= 100%$ . Yahi parent note mein har mitigation ka goal hai (branches ko warp boundaries pe align karo).

(b) Lopsided divergence — "sirf 1 lane alag hai". Ek akela lane 100-instruction path leta hai; baki 31 ne 50-instruction path liya. Intuition chillata hai "31/32 agree karte hain, toh basically free hai!" — lekin hamare formula mein lane counts bilkul nahi hain.

YEH KYUN MATTER KARTA HAI. Parent note mein yeh #1 mistake hai. Sum formula mein koi term nahi hai ki kitni lanes ne ek path liya — sirf yeh ki kitne distinct paths hain aur har ek kitna lamba hai. Ek dissenting lane phir bhi apna poora pipe issue karwata hai.

PICTURE. Left panel: full-green single pipe, 100% efficient. Right panel: ek mota 31-lane pipe (50 lamba) aur ek patla 1-lane pipe (100 lamba), phir bhi end-to-end $150$ cycles ke liye rakhe — patla pipe utna hi clock time leta hai jaise saare 32 lanes ise use kar rahe hon.

Ek picture mein summary

Sab kuch ek image mein collapse ho jaata hai: ek warp enter karta hai, mask $k$ pipes mein split hoti hai, pipes ek ke baad ek issue hote hain (sum), aur hum us end-to-end length ko ideal overlapped length (max) se compare karte hain.

Recall

Feynman retelling — ek 12-saal ke bacche ko batao Battees dost ek saath zanjeer mein bandhe hain aur ek waqt mein sirf ek step le sakte hain, sab same step, kyunki ek leader moves bolata hai. Woh ek fork pe pahunchte hain. Kuch left jaana chahte hain, kuch right — lekin zanjeer sirf ek raaste pe chali ja sakti hai ek waqt mein. Toh leader poori zanjeer ko left path pe march karta hai jabki right-wale ghisatey chale jaate hain kuch nahi karte, phir sabko right path pe march karta hai jabki left-wale ghisatey hain kuch nahi karte. Total time hai left walk plus right walk — add hote hain, overlap nahi. Agar instead sabne same direction chahia hoti, toh woh ek baar walk karte: yahi ideal hai. Slowdown hai (dono-walks-add) divided by (the-longer-single-walk). Worst case mein saare 32 alag-alag fork chahte hain, aur tum 32 alag paths ek ke baad ek walk karte ho — 32 times slower. Aur yeh kabhi help nahi karta ki sirf ek baccha weird path chahta tha: poori zanjeer phir bhi woh path ek baar chalti hai, kyunki tum chain ke sirf ek link ke liye move decode nahi kar sakte.

Ise fix karna chahte ho? Dekho CUDA optimization patterns aur occupancy optimization; data-layout cure memory coalescing aur parallel algorithm design se connect hota hai.

Recall Quick self-test

Ek warp 3 paths mein split hota hai length 12, 40, 8 cycles. Diverged cost? ::: $12 + 40 + 8 = 60$ cycles. Wahi warp, ideal cost? ::: $max (12, 40, 8) = 40$ cycles. Efficiency? ::: $40/60 \approx 66.7%$ . Agar sirf 1 lane length-40 path leta hai aur 31 length-8 lete hain, toh kya 40-pipe sasti ho jaati hai? ::: Nahi — cost per distinct path hai, per lane nahi; phir bhi uske puri 40 cycles worth of issued instructions ki cost hoti hai.