Bank conflicts in shared memory: Question bank — Hinglish deep dive

6.2.9 · D5 · Hardware › GPU Architecture › Bank conflicts in shared memory

Shuru karne se pehle, teen words hain jo is poore page par kaam aate hain:

Warp = 32 threads ka ek group jo lockstep mein execute karta hai — ye sab ek hi waqt par same shared-memory instruction issue karte hain, isliye inke 32 addresses hi wo cheez hai jo hardware banks mein sort karta hai.
Bank = shared memory mein 32 physical slots mein se ek, har ek 4 bytes wide hai, aur har ek ek clock cycle mein ek address serve kar sakta hai.
Bank conflict = ek hi warp ke do threads alag-alag addresses maangna jo same bank par map ho jaate hain, jisse hardware unhe serialize karne par majboor ho jaata hai.

Wo ek formula jis par neeche sab kuch depend karta hai: word index $w$ (ek 4-byte chunk number) ke liye, uska bank hai $bank = w mod 32$ , aur word-stride $s$ ke saath read karne wale warp ke liye har bank par pile hone wale threads ki sankhya $g cd (s, 32)$ hai.

True ya false — justify karo

Bada stride hamesha worse bank conflict ka matlab hai

False — sirf 32 ke saath shared factors matter karte hain. Stride 3 (

g cd (3, 32) = 1

) conflict-free hai jabki stride 2 (

g cd (2, 32) = 2

) conflict karta hai; bada number safer ho sakta hai.

Odd strides hamesha conflict-free hote hain

True — koi bhi odd number 32 ke saath coprime hota hai (jo

2^{5}

hai), isliye

g cd (odd, 32) = 1

, aur

i \mapsto (i \cdot s) mod 32

sabhi 32 banks ka ek permutation ban jaata hai.

Do threads jo same warp mein same address read karte hain, conflict cause karte hain

False — definition ke liye alag addresses chahiye. Same-address reads ek broadcast se handle hoti hain: ek fetch ek hi cycle mein sab requesters ke saath share ho jaati hai.

Stride-1 access guaranteed conflict-free hota hai

True — thread

i

word

i

ko hit karta hai, isliye bank

i mod 32

sabhi 32 distinct banks mein se guzarta hai, ek-ek kar har thread ke liye.

8-byte double ke liye bank formula ko /8 se recompute karna padta hai

False — banks hamesha 4 bytes ke hote hain; ek double sirf do consecutive banks ko span karta hai, aur tum reason karte ho ki har 4-byte half kahan land karta hai, kabhi 8-byte bank invent nahin karte.

Bank conflicts global memory accesses ko slow karte hain

False — banks sirf shared memory mein exist karte hain. Global memory ki analogous concern 6.2.08-Memory-coalescing hai, jo ek bilkul alag mechanism hai.

32-way conflict shared memory ko registers se slower bana deta hai

True — full serialization jo ek cycle mein honi chahiye thi uske liye 32 cycles lagti hain, shared memory ko register speed se neeche le jaati hai aur uska saara faayda khatam kar deti hai.

[32][32] matrix ko [32][33] tak padding karna koi benefit ke bina memory waste karna hai

False — extra column har row ki bank ko exactly 1 se shift kar deta hai (kyunki

33 \equiv 1 (mod 32)

), ek 32-way column conflict ko conflict-free access mein badal deta hai; thodi si memory cost 32× speedup kharid leti hai.

Conflicts is baat par depend karte hain ki aap kis warp mein hain, sirf addresses par nahin

False — conflicts ek single warp ke andar decide hote hain. Alag warps ke threads kabhi shared-memory transaction share nahin karte, isliye cross-warp collisions impossible hain.

Error dhundho

"12 bytes apart wale threads zaroor conflict karenge, kyunki 12 ≠ 4."

Word stride

12/4 = 3

hai, aur

g cd (3, 32) = 1

hai, isliye .x access banks ka ek permutation hai — conflict-free. Byte gap akela kuch nahin batata; pehle word stride mein convert karo.

"4 floats ka ek struct safe hai kyunki 4 fields cheezein achhe se fill karti hain."

4-float struct 16 bytes = 4-word stride hai, aur

g cd (4, 32) = 4

har field par 4-way conflict deta hai. "Achhe" power-of-two sizes precisely dangerous wale hain.

"matrix[row][tid] aur matrix[tid][col] dono stride-1 chalte hain, isliye dono theek hain."

Sirf pehla stride-1 hai. Row-major [tid][col] stride 32 words ke saath ek column ke neeche chalta hai, isliye har thread same bank ko hit karta hai — ek 32-way conflict.

"Array-of-structures se structure-of-arrays mein switch karna sirf ek style choice hai."

SoA har field ko ek stride-1 array mein force karta hai, struct size ki parwah kiye bina conflict-freedom guarantee karta hai, isliye ye ek real correctness-of-performance hazard hatata hai, sirf aesthetics nahin.

"bank = (i·33 + col) mod 32 mein abhi bhi wo ×33 hai, isliye ye conflict-free nahin ho sakta."

Kyunki

33 \equiv 1 (mod 32)

hai, poori cheez

(i + col) mod 32

mein collapse ho jaati hai, jo sabhi 32 banks ko sweep karta hai jab

i

0..31 run karta hai — perfectly conflict-free.

"matrix[i][j] ka bank words mein paane ke liye, word index ko 4 se phir divide karo."

Nahin —

/4

bytes ko words mein convert karta hai. Jab aap already word units mein hain, toh aap directly

mod 32

apply karte hain; dobara divide karna word width ko double-count karna hai.

Why questions

Shared memory mein banks kyun hote hain instead of ek bade block ke

Ek monolithic block ek cycle mein ek address serve kar sakta tha; 32 banks ek warp ke 32 requests ko parallel mein complete karne dete hain, jo 6.2.07-Shared-memory-architecture mein cover poora point hai.

Conflict degree

g cd (s, 32)

kyun hai aur sirf

s

kyun nahin

Threads har

32/ g cd (s, 32)

steps mein banks repeat karte hain, isliye exactly

g cd (s, 32)

threads har bank par pile hote hain; 32 ke saath shared factor,

s

khud nahin, set karta hai ki kitne collide karte hain.

Transpose case ko fix karne ke liye 33 tak padding kyun (34 ya 40 nahin)

33 sabse chhota inner width hai jiske liye

33 \equiv 1 (mod 32)

hai, exactly 1 ka per-row bank shift deta hai. Koi bhi width

\equiv 1 (mod 32)

kaam karta hai, lekin 33 sabse kam memory waste karta hai.

Broadcasts conflicts kyun nahin count hote

Conflict serialized different data hai; broadcast ek hi same address hai jo kai threads ko duplicate hoti hai, jise hardware ek read se sab ko satisfy karta hai — ek cycle, koi penalty nahin.

Column-walk conflict practice mein itna zyada kyun matter karta hai

Matrix transpose ek row read karta hai aur ek column write karta hai (ya vice versa), isliye column-walk 32-way conflict padding ke bina unavoidable hai — 6.3.01-Matrix-transpose-optimization ki core motivation.

Tum hamesha SoA use karke conflicts ke baare mein kyun nahin bhool sakte

SoA stride fix karta hai, lekin aap abhi bhi strided indexing ke saath conflicts create kar sakte hain (jaise x[tid*2]), aur ye doosre goals jaise cache locality ko hurt kar sakta hai; ye struct-size trap hatata hai, poora conflict risk nahin.

Edge cases

Ek warp jahan sabhi 32 threads identical address read karte hain — conflict?

Nahin — identical addresses ek broadcast trigger karte hain, ek hi cycle mein resolve hota hai. Ye harmless extreme hai, worst case nahin.

Ek warp jahan sabhi 32 threads 32 alag-alag addresses read karte hain jo sab bank 0 par map hote hain

Ye sach muchi worst case hai: ek 32-way conflict, 32 cycles mein fully serialized. Alag addresses + same bank hi serialize karta hai.

Stride 0 (har thread same index compute karta hai) — kya hota hai

s = 0

ke saath har thread ka word identical hai, isliye ye same-address broadcast case hai — ek cycle, conflict-free, koi

g cd (0, 32)

disaster nahin.

16 active threads aur baaki 16 masked off wala ek half-warp

Sirf active threads addresses issue karte hain, isliye conflicts live lanes ke beech compute hote hain; masked threads kuch contribute nahin karte, jo ek "32-way" pattern ko ek milder mein badal sakta hai. Masks kaise arise karte hain, uske liye 6.2.11-Warp-divergence dekhein.

Stride exactly 32 ke barabar

g cd (32, 32) = 32

— maximum 32-way conflict, kyunki har thread same bank par land karta hai. Ye disguise mein column-walk case hai.

Itni aggressively padding ki occupancy suffer kare

Extra padding per block shared-memory footprint badhata hai, jo reduce kar sakta hai ki per SM kitne blocks fit hote hain — ek trade-off jo 6.2.10-Occupancy-and-resource-limits track karta hai. Conflicts fix karo, lekin memory budget dekhte raho.

Recall Ek-line litmus test

Kisi bhi strided shared-memory access ko judge karne ke liye: ek word stride $s$ mein reduce karo, $g cd (s, 32)$ compute karo. Result 1 = conflict-free; result $d$ = $d$ -way conflict = $d$ cycles.