Worked examples — Warp divergence penalties

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

Yeh page parent topic ke liye worked-examples ki zameen hai. Parent ne tumhe dikhaya tha ki divergence kya hota hai; yahan hum har tarah ke case ko grind karte hain jo ek warp tumhare samne rakh sakta hai, ek number at a time. Agar koi symbol aata hai, toh hum use use karne se pehle define karte hain.

Recall Woh do numbers jo sab kuch decide karte hain

Pehle yeh padho — neeche ke saare examples sirf inhi do lines ka application hain.

• Maano $T_i$ un cycles ki sankhya hai ("cycle" matlab ek instruction jo hardware ko issue ki gayi) jo path $i$ ko chahiye.
• Ideal time (koi divergence nahi) $=\max (T_1,\dots ,T_k)$ — saare paths overlap karte hain, sabse slow wala pace set karta hai.
• Diverged time $=T_1+T_2+\cdots +T_k$ — paths ek ke baad ek chalte hain.
• Efficiency $=\frac{\text{ideal}}{\text{diverged}}=\frac{{\max }_i{T}_i}{{\sum }_i{T}_i}$.

Ek "path" ek distinct straight-line route hai code ke through jise warp mein kam se kam ek thread actually leta hai. Jo threads ek hi route lete hain woh ek path share karte hain — unka koi extra cost nahi.

Matrix se pehle, poore idea ki ek picture — taaki baad ke har example ka ek ghar ho.

Figure dekho: horizontal axis time in cycles hai. Upar wali bar mein saare 32 threads saath chalte hain (ek path). Neeche wali bar mein warp do groups mein split ho gaya — dhyaan do ki doosra group tabhi start kar sakta hai jab pehla group khatam ho jaye. Woh waiting gap hi penalty hai. Is page par koi cheez us gap se zyada complicated nahi hai.

---

Scenario matrix

Warp divergence ke baare mein har problem inhi cells mein se kisi ek mein aati hai. Hum har ek cell ko kam se kam ek worked example ke saath hit karenge.

Cell	Case class	Isme kya khaas hai
C1	Even 2-way split (if/else, half–half)	baseline; do paths, dono non-trivial
C2	Uneven split (1 thread vs 31)	"few threads = cheap?" trap ko test karta hai
C3	Zero divergence (saare threads ek hi path)	degenerate achha case, efficiency = 1
C4	Full divergence (har thread ka apna path)	worst case, $1/32$ limit
C5	Multi-way else if chain	$k>2$ paths, unequal lengths
C6	Loop / while divergence	trip-count har thread mein alag hoti hai
C7	Predication decision (branch ya predicate?)	limiting comparison $T_A+T_B$ vs $2\max$
C8	Nested ifs → orthogonal paths	path count multiply hoti hai
C9	Real-world word problem (ray tracing materials)	C4/C5 ko data par apply karta hai
C10	Exam twist (warp-boundary re-alignment)	C3 tak pahunchne ke liye restructure karo

Cross-links jo padhte waqt kaam aa sakte hain: 6.2.8-SIMT-execution-model (kyun ek instruction 32 lanes drive karta hai), 6.2.9-Warp-scheduling (kaise idle warps latency hide karte hain), 8.4.2-Branch-prediction (CPU cousin), 10.1.3-CUDA-optimization-patterns (scale par fixes).

---

Worked examples

Example 1 — Cell C1 (even 2-way split)

Forecast: Aage padhne se pehle efficiency guess karo. Zyaatar log "50% kyunki aadhe ek taraf jaate hain" kehte hain. Yeh soch pakad ke rakho.

1. Distinct paths identify karo. Do paths actually li ja rahi hain: A ($T_A=12$) aur B ($T_B=9$). Yeh step kyun? Cost liye gaye paths par depend karta hai, nahi ki kitne threads har ek lete hain — yahi 6.2.8-SIMT-execution-model ka poora lesson hai.
2. Diverged time $=T_A+T_B=12+9=21$ cycles. Yeh step kyun? Else-group wait karta hai jab tak if-group chalti hai, phir uske baad chalti hai (figure s01 mein gap dekho).
3. Ideal time $=\max (12,9)=12$ cycles. Yeh step kyun? Agar koi diverge nahi karta, toh saare 32 lanes overlap karte hain; akela slow wala path clock set karta hai.
4. Efficiency $=12/21=0.5714=57.1\%$. Yeh step kyun? Jo hum le sakte the aur jo hum liya uska ratio.

Verify: Efficiency $\max /\sum \le 1$ aur $\ge \max /(k\cdot \max )=1/k=1/2$ satisfy karni chahiye. Humne $0.571$ paaya, jo $[0.5,1]$ mein hai. Note karo yeh 50% nahi hai — "half–half" intuition galat thi kyunki dono paths ki alag lengths hain. ✔

---

Example 2 — Cell C2 (uneven split, "few threads" trap)

Forecast: Tempting galat jawab hai $50+\frac{100}{32}\approx 53$ cycles — "sirf ek thread expensive kaam karta hai, toh amortise karo." Guess karo ki yeh sahi hai ya nahi.

1. Distinct paths liye gaye: do — ek 100-cycle path (1 thread) aur ek 50-cycle path (31 threads). Yeh step kyun? Ek bhi diverging thread ek poora doosra path create karta hai.
2. Sahi diverged cost $=100+50=150$ cycles. Yeh step kyun? Hardware poore warp ke liye 100-cycle path chalata hai (31 lanes masked off hain lekin phir bhi idle-waiting hain), phir 50-cycle path. Thread count kabhi cost ko divide nahi karta.
3. Naive (galat) estimate $=50+100/32=53.125$ cycles. Yeh step kyun? Hum ise sirf ek myth ke roop mein expose karne ke liye compute karte hain.
4. Ideal $=\max (100,50)=100$; efficiency $=100/150=0.6667=66.7\%$.

Verify: Sahi cost 150 vs naive 53.125 — inमें nearly $3\times$ ka fark hai, confirming karta hai ki myth dangerous hai. Efficiency $0.667\in [0.5,1]$. ✔

---

Example 3 — Cell C3 (zero divergence, degenerate good case)

Forecast: Padhne se pehle guess karo: kabhi bhi possible sabse acchi efficiency kya hai?

1. Distinct paths liye gaye: sirf ek — path B. Path A kisi bhi thread ke liye kabhi enter nahi ki jaati, toh is warp ke liye exist nahi karti. Yeh step kyun? Ek nahi li gayi branch free hai; hardware iske upar mask all-off ke saath skip karta hai, koi cycles issue nahi hote.
2. Diverged time $=9$ cycles. Ideal $=\max (9)=9$.
3. Efficiency $=9/9=1.00=100\%$.

Verify: Jab $k=1$, $\frac{\max }{\sum }=\frac{9}{9}=1$. Yeh degenerate ceiling hai — tum 100% se behtar kabhi nahi ho sakte. Yeh 10.1.3-CUDA-optimization-patterns mein har mitigation ka goal confirm karta hai: $k=1$ par collapse karo. ✔

---

Example 4 — Cell C4 (full divergence, $1/32$ limit)

Forecast: Efficiency ko ek simple fraction ke roop mein guess karo.

1. Distinct paths ki sankhya $k=32$ (sab alag). Yeh step kyun? $k$ actually walk ki gayi routes ka count hai; yahan yeh warp size par max ho jaata hai.
2. Diverged time $=32\times 7=224$ cycles. Yeh step kyun? 32 serial executions, har ek $n$ cycles.
3. Ideal time $=\max =7$ cycles (sab equal hain).
4. Efficiency $=7/224=1/32=0.03125=3.125\%$. Yeh step kyun? Yeh 32-thread warp ka theoretical floor hai — parent note mein quote kiya gaya "1/32nd of peak."

Verify: General case: agar saare $k$ paths ki equal length hai, efficiency $=\frac{L}{k\cdot L}=\frac{1}{k}$. $k=32$ ke saath: $1/32=0.03125$. ✔

---

Example 5 — Cell C5 (multi-way else if, unequal lengths)

Forecast: Kaunsa single path ideal time ko dominate karta hai? Step 3 se pehle guess karo.

1. Paths liye gaye: charon present hain (har type mein ≥1 thread hai), toh $k=4$. Yeh step kyun? Thread counts (8,10,8,6) humein batate hain ki kaunse paths live hain, cost nahi.
2. Diverged time $=20+30+25+5=80$ cycles.
3. Ideal time $=\max (20,30,25,5)=30$ cycles — exp path dominate karta hai. Yeh step kyun? Agar koi diverge nahi karta, toh akela longest live path clock set karta hai.
4. Efficiency $=30/80=0.375=37.5\%$.

Verify: $0.375\in [1/4,1]$ kyunki $k=4\Rightarrow$ floor $=1/4=0.25$. Parent note ke Example 2 se exactly match karta hai. ✔

---

Example 6 — Cell C6 (loop divergence)

Forecast: Warp tab khatam hoga jab aakhri thread khatam hoga. Guess karo: kya total counts ke sum par depend karta hai ya counts ke max par?

1. Loop back-edge ek branch hai. Har iteration mein, woh threads jinke liye $i\ge \text{counts}[idx]$ hai drop out ho jaate hain (masked off) lekin warp loop karta rehta hai. Yeh step kyun? Figure s02 dekho: active-lane count har iteration mein shrink karti hai lekin loop tab tak exit nahi kar sakta jab tak sabse lamba bar (count = 20) khatam nahi ho jaata.
2. Total cycles $=\max \text{counts}=20$ (ek cycle per iteration, sabse slow thread par warp-serialized). Yeh step kyun? Warp apne sabse zyada der tak chalne wale thread ka hostage hai.
3. Kiya gaya useful work $=\sum \text{counts}=240$ thread-iterations.
4. Utilization $U=\frac{240}{32\times 20}=\frac{240}{640}=0.375=37.5\%$. Yeh step kyun? Hardware kar sakta tha $32\times 20=640$ lane-iterations, unमें se sirf 240 real work thi.

Verify: $U=240/640=0.375$, aur $U\le 1$ hamesha kyunki $\sum \text{counts}\le 32\max$. Do short (count-3) threads $2\times (20-3)=34$ lane-iterations waste karte hain — loss ka ek bada hissa. ✔

---

Example 7 — Cell C7 (branch vs predication — limiting comparison)

Forecast: Chhote branches ke liye, guess karo ki predication kabhi harti hai ya nahi.

1. Predicated cost. a aur b dono har thread ke liye unconditionally compute hote hain: $T_{\text{pred}}=T_A+T_B=4+3=7$ cycles, bina kisi branch/mask-stack overhead ke. Yeh step kyun? Predication branch ko poori tarah hata deta hai — koi divergence stack push/pop nahi.
2. Branch (diverged) cost. Kyunki yeh half–half diverge hota hai: $T_{\text{branch}}=T_A+T_B+O=7+O$, jahan $O$ branch/reconverge overhead hai ($O>0$). Yeh step kyun? Wahi serialized path sum, saath mein divergence stack manage karne ki cost.
3. Compare. $T_{\text{pred}}=7<7+O=T_{\text{branch}}$. Predication exactly $O$ se jeetta hai. Yeh step kyun? Jab dono paths chhote hain aur dono divergence ke underaise bhi chalenge, branch machinery skip karna pure profit hai.
4. Jahan predication harti hai: agar ek path lamba hai aur often not taken (jaise Example 3 ka C3 case), toh branching hardware ko nahi li gayi path poori tarah skip karne deta hai; predication use force karke chalata. Predicate sirf short, both-usually-needed paths ke liye karo.

Verify: $T_{\text{pred}}=7$, $T_{\text{branch}}=7+O$ with $O>0\Rightarrow T_{\text{pred}}<T_{\text{branch}}$. Short-branch case ke liye inequality strict hai. ✔ (Dekho 6.2.12-Occupancy-optimization kyun branches hatana divergence stack bhi free karta hai.)

---

Example 8 — Cell C8 (nested ifs → orthogonal paths multiply karte hain)

Forecast: Worst case mein kitne distinct paths hain? 2? 3? 4?

1. Distinct paths count karo. Outer test 2 groups mein split karta hai; har group ka inner test phir split karta hai. Worst case: $2\times 2=4$ live paths. Yeh step kyun? Orthogonal (independent) conditions path count ko multiply karte hain — nesting additive nahi hoti.
2. Diverged time $=p_1+p_2+p_3+p_4=6+8+5+7=26$ cycles. Yeh step kyun? Char serialized paths, ek ke baad ek.
3. Ideal time $=\max (6,8,5,7)=8$ cycles.
4. Efficiency $=8/26=0.3077=30.8\%$.

Verify: $k=4$ ke saath, floor $=1/4=0.25$; $0.3077\in [0.25,1]$. Naive "ek extra branch → 3 paths" undercount karta hai; actual $k=4$ ise aur bura banata hai. ✔

---

Example 9 — Cell C9 (real-world: ray-tracing materials)

Forecast: Guess karo ki sorting humein 100% tak pahuncha sakti hai ya nahi.

1. As-is, paths live: $k=4$, costs $\{12,40,60,4\}$. Yeh step kyun? Har material present hai ⇒ har path serialized.
2. Diverged time $=12+40+60+4=116$ cycles; ideal $=\max =60$.
3. Efficiency (a) $=60/116=0.5172=51.7\%$.
4. Sorting ke baad: ek warp ab sirf ek material rakhta hai ⇒ $k=1$ ⇒ diverged $=$ ideal. Efficiency (b) $=60/60=1.00=100\%$ all-glass warp ke liye (aur 100% har uniform warp ke liye). Yeh step kyun? Sorting C4→C3 collapse hai: similar kaam ko warp size tak bucket karo, exactly wahi fix jo 9.3.5-Parallel-algorithmsdesign aur 10.1.3-CUDA-optimization-patterns mein hai.

Verify: (a) $60/116=0.51724\dots$; (b) koi bhi single-path warp $\max /\sum =1$ deta hai. Sorting yahan throughput almost double kar deti hai ($0.517\to 1.0$). ✔

---

Example 10 — Cell C10 (exam twist: warp boundary par re-align karo)

Forecast: idx % 2 har warp ke andar split karta hai. Compute karne se pehle (a) guess karo.

1. As-is: kisi bhi warp mein, even aur odd lanes dono present hain ⇒ dono paths live, $k=2$. Yeh step kyun? idx % 2 warp ke andar alternate karta hai — guaranteed divergence.
2. Diverged $=10+14=24$; ideal $=\max (10,14)=14$. Efficiency (a) $=14/24=0.5833=58.3\%$.
3. Rewrite: (idx/32)%2 ek warp ke saare 32 lanes mein constant hai (woh ek hi idx/32 share karte hain). Toh ek warp poori tarah X ya poori tarah Y hai ⇒ $k=1$. Yeh step kyun? Branch key ko warp granularity ke saath align karna intra-warp divergence khatam kar deta hai — 6.2.10-Memory-coalescing ke sibling idea ka core mitigation (32 ke hisaab se group karo).
4. Efficiency (b): ek pure-X warp $=10/10=100\%$; ek pure-Y warp $=14/14=100\%$.

Verify: (a) $14/24=0.58333\dots \in [0.5,1]$. (b) single-path ⇒ 1.0. Re-alignment efficiency 58.3% se 100% tak le jaata hai. ✔

---

Recall Quick self-test (answers reveal karo)

Do paths, 5 aur 5 cycles, half–half. Diverged time? ::: $5+5=10$ cycles. …aur uski efficiency? ::: $\max /\sum =5/10=50\%$. Ek thread 90-cyc path par, 31 ek 10-cyc path par — cost? ::: $90+10=100$ cycles (amortised nahi). Saare 32 threads ek hi 8-cyc path lete hain — efficiency? ::: $8/8=100\%$ ($k=1$). 32-thread warp ke liye equal paths ke saath worst-case efficiency? ::: $1/32\approx 3.125\%$. Loop jisme $\sum \text{counts}=240,\max =20$ — utilization? ::: $240/(32\cdot 20)=37.5\%$.