Warp divergence penalties: Question bank — Hinglish deep dive

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

Yeh ek self-test page hai. Har line apna answer ::: ke baad hide karti hai. Right side cover karo, ek guess out loud karo, phir reveal karo. Har answer tumhe reasoning deta hai, sirf verdict nahi — aur wohi reasoning hai jo tumhe reproduce karni aani chahiye.

Agar koi word yahan unfamiliar lage (warp, mask, predication, reconverge), toh ruko aur use parent note Warp divergence penalties se rebuild karo pehle. Yeh bank assume karta hai ki tumhare paas woh definitions already hain, aur sirf test karta hai ki tum unhe pressure mein use kar sako.

Definition

Is page par use hone wale symbols Throughout, ek path ka matlab hai ek conditional ki ek branch (jaise if body, ya ek case). Path $i$ ke liye:

$T_{i}$ = path $i$ ki latency cycles mein, warp ke us path se ek serialized pass ke liye — yaani warp ko us path ki instructions chalane mein kitna time lagta hai, ek baar, jab us path ke lanes active hon aur baaki masked hon. Yeh ek per-warp-pass time hai, na per-thread time aur na kitne threads ne woh path liya usse multiply kiya gaya.
$T_{A}$ , $T_{B}$ = same quantity ek two-way branch ke liye, if path aur else path respectively.
$b$ = fixed branch/mask-stack overhead jo ek real conditional pay karta hai, chahe koi bhi path body run ho: woh cycles jo condition evaluate karne, active mask banane, divergence stack push/pop karne, aur jump karne mein jaate hain. Predication mein koi $b$ nahi hota (koi branch hi nahi hai), lekin woh hamesha dono bodies run karta hai.

Neeche har cost claim inhi se bani hai. Questions se pehle derivation box padho.

Intuition

Cost SUM of path times kyun hai (core claim, derived) SIMT ke under, ek warp ke saare 32 lanes ek program counter aur ek instruction decoder share karte hain. Hardware ek warp ke liye ek saath do alag instructions run nahi kar sakta. Toh jab lanes ek branch par disagree karte hain, woh yeh karta hai:

Path A ke liye ek active mask banao (ek 32-bit flag: 1 = execute, 0 = masked-off).
Path A ki instructions us mask ke saath run karo. Ab tak ka cost: $T_{A}$ .
Mask ko path B ke liye flip karo aur path B ki instructions run karo. Cost: aur $T_{B}$ .
Reconverge (full mask restore) karo aur continue karo.

Kyunki steps 2 aur 3 ek hi shared program counter par ek ke baad ek hote hain, times add hote hain: total $= T_{A} + T_{B}$ . Yeh kis baat par depend nahi karta ki kitne threads ne kaun sa path liya — count sirf decide karta hai ki kaun se mask bits set hain, pass kitna lamba hoga yeh nahi. $k$ paths tak generalize karne par $\sum_{i = 1}^{k} T_{i}$ milta hai. Yahi ek fact hai jo neeche almost har trap secretly violate karta hai, add karne ki jagah average karne ki koshish karke.

Yahi figure s01 draw karta hai: ek blue mask pass A ke liye path B ke pink mask ke upar stacked, unke beech yellow "serial in time" arrow, aur reconvergence par full yellow mask. Woh vertical stack trace karo aur tumne literally $T_{A} + T_{B}$ hote dekh liya.

Figure s01 — mask stack. Har row mein coloured (active) squares ki sankhya row ki length se irrelevant hai; sirf yeh fact ki dono rows ek-ke-neeche-ek (serial) run hoti hain, times ko add karwata hai. Jab bhi koi question tumhe thread count se average karne ke liye tempt kare, isko refer karo (har "Spot the error" averaging trap ka answer is picture se milta hai).

Definition

Reconvergence — "continue" actually kahan hota hai Reconvergence woh point hai jahan divergent lanes ek full mask ke neeche dobara milti hain. Modern NVIDIA hardware par yeh point branch ka immediate post-dominator (IPDOM) hota hai: woh earliest instruction jo har path guaranteed reach karta hai, chahe kaun si bhi branch li ho. Clean structured code (if/else, for, while) ke liye IPDOM bas woh obvious merge point hai jo construct ke theek baad hai. Unstructured control flow (goto, nested loops se break, overlapping branches) ke liye merge point obvious nahi hota, aur compiler ko IPDOM explicitly compute karna padta hai — reconvergence delay ho sakta hai, ya pre-Volta hardware par, jahan expect karo wahan nahi hota. Isliye structured code ke bahar "bas merge point draw karo" unreliable hai.

Figure s02 — 4-path example ke liye divergent execution timeline. Numerator mein $max (T_{i})$ aur denominator mein $\sum T_{i}$ ke baare mein "Why questions" ka har item seedha top bar versus bottom bars ki row se map karta hai.

Definition

"Warp-aligned condition" ka matlab kya hai Ek branch condition warp-aligned hoti hai jab warp ke saare 32 threads guaranteed isko same tarike se evaluate karte hain, toh warp kabhi split nahi hota. Example: if ((idx / 32) % 2 == 0) — kyunki idx / 32 warp id hai, ek warp ki saari 32 lanes ise share karti hain, toh saari 32 agree karti hain. Contrast karo if (idx % 2 == 0) se, jahan har doosre thread par lanes disagree karti hain. Sirf blockIdx, warpId = idx/32, ya ek compile-time constant se jo bhi derived hai woh warp-aligned hai; jo threadIdx se sub-warp granularity par derived hai woh generally nahi hota.

Figure s03 puri mitigation story ek picture mein hai: left mein, idx % 2 == 0 lanes ko alternately blue/pink paint karta hai — ek split mask, cost $T_{A} + T_{B}$ . Right mein, (idx / 32) % 2 == 0 har lane ko same colour paint karta hai — ek full mask, cost sirf $T_{A}$ . blockIdx/warpId par decision move karne ke baare mein koi bhi "Spot the error" ya "Why" item in dono panels ko compare karke answer hota hai.

Figure s03 — sub-warp condition (diverges, left) versus warp-aligned condition (no split, right). Jab bhi tum neeche "warp-aligned" word padho, yahi visual tumhare dimag mein honi chahiye.

Recall

Mask ko khud step-through karo (questions se pehle yeh karo) Ek line at a time reveal karo aur mentally figure s01 ki rows colour karo jaise jao — yeh "animation" haath se ki gayi hai. Step 1 — saari 32 lanes branch hit karti hain, ek shared PC, full mask. Mask kaisa dikhta hai? ::: Saare 32 squares lit; abhi koi split nahi — yeh figure s01 ke top ka hissa hai, fork se pehle. Step 2 — lanes condition evaluate karti hain aur disagree karti hain. Mask ke saath kya hota hai? ::: Yeh s01 ki blue (path A) row aur pink (path B) row mein split ho jaata hai; hardware ek ko divergence stack par push karta hai. Step 3 — path A run hoti hai. Kaun si lanes cycles burn karti hain, kaun si idle hain? ::: Blue lanes $T_{A}$ cycles ke liye active, pink lanes idle-but-still-waiting; warp ka clock $T_{A}$ se advance hota hai. Step 4 — path B run hoti hai. Ab tak ka running total kya hai? ::: Pink lanes $T_{B}$ aur cycles ke liye active; running total $T_{A} + T_{B}$ — s01 ki do stacked rows. Step 5 — IPDOM par reconverge. Kya restore hota hai? ::: Full 32-lane mask (s01 ki bottom yellow row); execution lockstep mein continue hoti hai.

True or false — justify

True or false: Agar 32 mein se 31 threads path A leti hain aur sirf 1 path B leti hai, toh warp path B ke liye almost kuch nahi pay karta.

False. Warp path B us akele thread ke liye poori tarah execute karta hai jabki baaki 31 masked-off baithe rehte hain; cost

T_{A} + T_{B}

hai (dono full path latencies), 31-to-1 split se unaffected — exactly figure s01 ki do stacked rows, chahe ek row mein kitne bhi kam squares lit hon.

True or false: Ek branch jahaan saare 32 threads condition ko same tarike se evaluate karte hain, koi divergence penalty nahi cause karta.

True. Agar har thread agree kare, toh sirf ek path li jaati hai aur doosri kabhi enter nahi hoti — serialize karne ke liye kuch nahi, toh mask poora time full rehta hai (figure s03 ka right panel).

True or false: Divergence ek hi block ke do alag warps ke beech ho sakta hai.

False. Divergence ek single warp ke andar defined hai. Do warps alag paths lena sirf do independent warps ke roop mein run karna hai — yeh normal scheduling hai, divergence nahi.

True or false: Divergent path ke dauran masked-off threads ALU issue slots exactly active threads ki tarah consume karti hain.

False — yeh nuance hai. Masked lanes useful work retire nahi karti aur kai architectures par ALU pipeline ko same tarike se occupy nahi karti (kuch whole-mask-off cases ke liye issue skip bhi kar sakti hain). Lekin warp phir bhi shared PC par

T_{A}

phir

T_{B}

time kharch karta hai, toh wall-clock cost add hoti hai aur power phir bhi burn hoti hai. Per-lane slot accounting nahi, serialized time dard deta hai.

True or false: Ek if jisme else nahi hai, divergence cause nahi kar sakta kyunki sirf ek body hai.

False. "Else" implicitly "kuch mat karo aur merge point tak skip karo" hai. Jo threads condition fail karti hain woh body run hone ke dauran masked rehti hain, toh tum phir bhi taken body ko skip ke against serialize kar rahe ho.

True or false: ? : (ternary) use karna if/else ki jagah hamesha divergence penalty remove karta hai.

False. Yeh sirf tab help karta hai jab compiler ise short bodies ke liye predication mein convert kare. Long ya side-effect-heavy bodies ke liye yeh phir bhi real branch mein compile hota hai, aur dono sides phir bhi run hoti hain.

True or false: 4 cases wala switch statement worst case mein ek warp mein saari 4 case bodies ka sum cost kar sakta hai.

True. Agar warp ke threads saari 4 cases mein scatter ho jaayein, toh hardware saare chaar masked passes serialize karta hai —

\sum_{i = 1}^{4} T_{i}

— exactly 4-way if/else-if chain ki tarah (figure s02 ke chaar end-to-end bars).

True or false: Loop divergence warp mein average trip count se bound hota hai.

False. Yeh maximum trip count se bound hota hai. Warp iterate karta rehta hai (shrinking mask ke saath) jab tak last thread ka loop condition fail na ho.

True or false: Do warps jo each internally same tarike se diverge karte hain, woh apne peak throughput ka same fraction waste karte hain.

True. Efficiency ek per-warp ratio

\frac{max ( T _{i} )}{\sum T _{i}}

hai; identical path distributions identical efficiency deti hain chahe tum kaun sa warp dekho.

True or false: Agar ek branch data-dependent ho (memory se loaded values par depend kare), toh compiler ise predict kar sakta hai aur divergence avoid kar sakta hai.

False. Yeh CPU-style branch prediction hai (dekho 8.4.2-Branch-prediction). GPUs divergent lanes ke liye aise speculation nahi karte; data-dependent branches runtime par diverge hote hain jab bhi loaded values disagree karti hain.

True or false: Clean if/else ke liye reconvergence hamesha else block ke theek baad wali instruction par hoti hai.

Structured code ke liye True — woh instruction immediate post-dominator hai, pehla point jo har path reach karta hai. Unstructured control flow (early goto, nested loops se bahar break) ke liye IPDOM kahin aur ya delayed ho sakta hai, toh tum naive merge point assume nahi kar sakte.

Spot the error

Spot the error: "32 mein se sirf 2 threads else hit karti hain, toh cost ≈ 50 + 100/32 ≈ 53 cycles."

Wrong model — tumne else ko 32 threads se average kar diya. Real cost

T_{A} + T_{B} = 50 + 100 = 150

hai: dono path latencies poori tarah add hoti hain, kisi cheez se weight nahi hoti (figure s01 ki do stacked rows, thread-count average nahi).

Spot the error: "if (idx % 2 == 0) kaam evenly split karta hai, toh warp 50% busy rehta hai poora time."

50% figure per-lane utilization hai, lekin time double ho jaata hai kyunki dono halves serially run hoti hain. Even-odd splitting ek textbook non-warp-aligned condition hai (figure s03 ka left panel): yeh guarantee karta hai har warp mein divergence.

Spot the error: "if ko if ke andar nest karna hamesha penalty multiply karta hai, toh sab kuch flatten karo."

Ek single already-taken path ke andar nesting sirf us path ke

T_{i}

mein add karti hai — koi nayi serialization nahi. Sirf woh nesting jo orthogonal path splits create kare, distinct paths ki sankhya multiply karti hai.

Spot the error: "Maine data ko type ke hisaab se sort kar diya, toh ab kahin bhi zero divergence hai."

Sirf tab agar sort warp size (32) ke liye aligned ho. Agar koi type boundary ek warp ke beech mein pade, toh woh boundary warp phir bhi diverge karta hai. Ise fully eliminate karne ke liye sorting 32 ke multiples mein bucket karni chahiye.

Spot the error: "Predication sirf tab help karta hai jab

T_{A} + T_{B} > 2 max (T_{A}, T_{B})

Ulta hai. Predication hamesha dono sides execute karta hai, toh iska cost exactly

T_{A} + T_{B}

hai, jo

2 max (T_{A}, T_{B})

se kabhi exceed nahi ho sakta. Predication tab worth it hai jab iska fixed cost expected branch cost se behat ho — neeche "why" mein derivation dekho; useful regime woh hai jab dono bodies short hoon, tab nahi jab upar wali inequality hold kare (woh kabhi nahi hoti).

Spot the error: "counts = [1,1,1,...,1,1000] — ek bada thread, toh cost ≈ average ≈ 32 iterations."

Single count-1000 thread poore warp ko 1000 iterations ke liye hostage rakhta hai. Loop cost max track karta hai, toh yeh ~1000 iterations of the loop body hai, 31 lanes almost poore time idle hain.

Spot the error: "Maine apna if threadIdx ki jagah blockIdx par depend karne ke liye move kar diya, lekin divergence unchanged hai."

blockIdx par ek condition warp-aligned hai — ek warp ka har thread value share karta hai → sab agree → koi divergence nahi (figure s03 ka right panel). Decision ko block ya warp granularity par move karna exactly woh fix hai.

Why questions

Why can't the hardware sirf masked-off threads ke liye instructions skip kar deta instead of issue karne ke?

SIMT mein ek single decoder ek instruction ko ek program counter se saari 32 lanes ko broadcast karta hai. Koi per-lane program counter nahi hai jo independently aage run kar sake, toh ek divergent path ko apne masked pass ke roop mein walk karna hi padta hai aur passes time mein serialize hote hain.

Why, precisely, predication kabhi worth it hai agar woh hamesha dono sides

T_{A} + T_{B}

cost par run karta hai?

Ek real divergent branch bhi

T_{A} + T_{B}

cost karta hai jab warp split ho, plus fixed branch/mask-stack overhead

b

jo symbols box mein define hai (condition eval, mask build, stack push/pop, jump). Agar branch rarely split ho, toh iska expected cost

max (T_{A}, T_{B}) + b

ke kareeb hota hai. Predication tab win hoti hai jab dono bodies itni short hoon — roughly

\leq 4 - 5

instructions each, toh

T_{A}, T_{B}

tiny hain — ki

T_{A} + T_{B}

har baar pay karna (bina kisi

b

ke) phir bhi branch overhead

b

aur full split ke risk se sasta ho. Lambi bodies

T_{A} + T_{B}

ko dominant bana deti hain aur predication haar jaata hai.

Why data-dependent branching (ray tracing, particle types) ko "catastrophic" kyun kehte hain jabki ek fixed idx < 16 split sirf bad hai?

Ek fixed split mein zyada se zyada 2 paths hain; data-dependent code ek warp mein threads ko kai paths mein scatter kar sakta hai, aur worst case mein 32 threads mein se har ek unique path leta hai — cost

\sum_{i = 1}^{32} T_{i}

32 \times

slowdown tak.

Why warp boundaries par divergence align karna penalty fully eliminate karta hai, sirf reduce kyun nahi karta?

Ek warp-aligned condition saari 32 lanes ko agree kara deti hai, toh sirf ek path kabhi enter hoti hai — doosri kabhi execute hi nahi hoti (figure s03, right panel). Literally serialize karne ke liye kuch nahi, toh penalty zero hai, sirf chhoti nahi.

Why efficiency formula mein numerator mein

max (T_{i})

kyun hai?

max (T_{i})

woh hai jo same kaam would cost karta agar saare threads parallel run karte (slowest path pace set karta) — figure s02 mein single top bar. Woh ideal parallel time ko serialized sum

\sum T_{i}

(bottom bars ki row) se divide karna tumhe woh fraction deta hai jo peak ka actually milta hai.

Why sorting data by type ideal case mein divergence fully fix kar sakta hai, lekin branch predication nahi kar sakta?

Sorting har thread ko warp mein agree kara deti hai (warp-aligned), toh branch kabhi diverged nahi hoti. Predication disagreement ko wahan chhod deta hai aur dono sides anyway execute karta hai — yeh branch hide karta hai, wasted work nahi.

Why unstructured control flow ke liye reconvergence location matter karta hai?

Hardware full mask immediate post-dominator par restore karta hai. Clean code mein woh obvious merge point hota hai, lekin goto/nested break ke saath earliest guaranteed-common instruction kaafi downstream ho sakti hai, toh lanes expect se zyada der tak diverged rehti hain aur utilization suffer karta hai jab tak woh finally rejoin na karein.

Why warp divergence occupancy tuning (6.2.12-Occupancy-optimization) ke liye relevant hai, chahe occupancy resident warps ke baare mein hai, branches ke nahi?

Divergence per-warp useful throughput lower kar deta hai, toh wasted cycles hide karne ke liye tumhe zyada resident warps chahiye ho sakte hain. High occupancy divergence latency ko partially mask kar sakta hai lekin serialized instruction count khud kabhi remove nahi kar sakta.

Why coalesced memory access (6.2.10-Memory-coalescing) kabhi kabhi us divergence pattern se exactly destroy ho jaata hai jo tumne introduce kiya?

Jab threads alag paths par split ho jaate hain, har pass mein active lanes warp ka ek scattered subset hoti hain, toh unke memory addresses woh contiguous, aligned run nahi banate jo coalescing ko chahiye — tum parallelism aur bandwidth dono kho dete ho.

Edge cases

Edge case: Ek warp jahaan saare threads iteration 0 par loop exit kar dete hain (har count 0 hai).

Kisi ke liye koi iteration run nahi hoti; loop-entry branch unanimously false hai, toh koi divergence nahi aur essentially koi cost nahi — degenerate zero case actually sabse sasta hai.

Edge case: Ek warp sirf partially filled hai (jaise 20 threads ka block, last warp mein 12 real threads hain).

20 "missing" lanes shuroo se hi inactive hain (unka mask bit poore kernel ke liye off hai). Yeh divergence nahi hai, lekin woh slots waste karte hain — ek alag under-utilization, per-branch penalty nahi.

Edge case: Warp ka har thread same path leta hai lekin us path mein ek internal loop hai equal trip counts ke saath.

Zero divergence: har branch par identical conditions matlab mask kabhi fragment nahi hota, aur equal trip counts ensure karte hain ki har lane same iteration par loop exit kare. Warp poori tarah converged rehta hai aur full efficiency par run karta hai, loop ke IPDOM par cleanly reconverge karta hai.

Edge case: Ek if/else jahaan path A 1000 cycles hai aur path B 1 cycle, aur exactly ek thread A leta hai.

Cost

T_{A} + T_{B} = 1000 + 1 = 1001

cycles hai. Single A-thread poore warp ko 1000 masked cycles ke through drag karta hai; splitting count irrelevant hai — yeh classic "one slow lane" trap hai, figure s01 ka extreme version.

Edge case: Nested branches 4 orthogonal paths produce karti hain, lekin ek particular warp mein saare 32 threads same leaf mein land karte hain.

Woh warp diverge bilkul nahi karta — woh kabhi sirf ek leaf path mein enter karta hai. Worst-case potentially 4 paths hain, lekin actual cost runtime distribution par depend karta hai, jo yahan unanimous hai.

Edge case: Ek while loop jiska condition saari lanes ke liye true hai jab tak ek data-dependent break na ho, aur ek lane baaki se 100× baad break kare.

Warp tab tak run karta hai jab tak last lane break na kare (loop ke IPDOM par reconvergence), toh ~100 extra iterations single active lane ke saath execute hoti hain. Effective utilization us tail ke dauran

1/32

ki taraf collapse ho jaata hai.

Edge case: Do disjoint if blocks back-to-back, dono diverge karte hain, lekin same 16/16 split par.

Woh 4 paths mein compound nahi hote — har ek independent 2-path region hai jo agli se pehle reconverge hota hai. Total cost dono regions ke path sums ka sum hai, unका product nahi.

Recall

Ek-line summary jo saath le jaao Divergence cost = ==sum of the path latencies $\sum T_{i}$ , per warp; fix yeh hai ki warp ke 32 threads ko agree karwao via a warp-aligned condition== (derived from warpId/blockIdx, ya data ko 32 ke multiples mein sort karo) ya predicate sirf short (≤~5-instruction) bodies. Reconvergence immediate post-dominator par hota hai.

See also: 6.2.9-Warp-scheduling, 9.3.5-Parallel-algorithmsdesign, 10.1.3-CUDA-optimization-patterns, aur Hinglish walkthrough 6.2.11 Warp divergence penalties (Hinglish).