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

Before we start, three words earn their keep on this whole page:

Warp = a group of 32 threads that execute in lockstep — they all issue the same shared-memory instruction at the same instant, so their 32 addresses are what the hardware sorts into banks.
Bank = one of 32 physical slots in shared memory, each 4 bytes wide, each able to serve one address per clock cycle.
Bank conflict = two threads of the same warp asking for different addresses that map to the same bank, forcing the hardware to serialize them.

The single formula everything below leans on: for a word index $w$ (a 4-byte chunk number), its bank is $bank = w mod 32$ , and for a warp reading with word-stride $s$ the number of threads piled on each bank is $g cd (s, 32)$ .

True or false — justify

A larger stride always means a worse bank conflict

False — only the shared factors with 32 matter. Stride 3 (

g cd (3, 32) = 1

) is conflict-free while stride 2 (

g cd (2, 32) = 2

) conflicts; a bigger number can be safer.

Odd strides are always conflict-free

True — any odd number is coprime to 32 (which is

2^{5}

), so

g cd (odd, 32) = 1

, and

i \mapsto (i \cdot s) mod 32

becomes a permutation of all 32 banks.

Two threads reading the same address in the same bank cause a conflict

False — the definition requires different addresses. Same-address reads are handled by a broadcast: one fetch is shared with all requesters in a single cycle.

A stride-1 access is guaranteed conflict-free

True — thread

i

hits word

i

, so bank

i mod 32

runs through all 32 distinct banks exactly once, one per thread.

An 8-byte double needs the bank formula recomputed with /8

False — banks are always 4 bytes; a double simply spans two consecutive banks, and you reason about where each 4-byte half lands, never inventing an 8-byte bank.

Bank conflicts slow down global memory accesses

False — banks exist only in shared memory. The analogous global-memory concern is 6.2.08-Memory-coalescing, which is a different mechanism entirely.

A 32-way conflict makes shared memory slower than registers

True — full serialization costs 32 cycles for what should be one, dropping shared memory below register speed and erasing its whole advantage.

Padding a [32][32] matrix to [32][33] wastes memory for no benefit

False — the extra column shifts each row's bank by exactly 1 (since

33 \equiv 1 (mod 32)

), turning a 32-way column conflict into conflict-free access; the tiny memory cost buys a 32× speedup.

Conflicts depend on which warp you're in, not just the addresses

False — conflicts are decided within a single warp. Threads in different warps never share a shared-memory transaction, so cross-warp collisions are impossible.

Spot the error

"Threads 12 bytes apart must conflict, since 12 ≠ 4."

The word stride is

12/4 = 3

, and

g cd (3, 32) = 1

, so the .x access is a permutation of banks — conflict-free. The byte gap alone tells you nothing; convert to word stride first.

"A struct of 4 floats is safe because 4 fields nicely fill things."

A 4-float struct is 16 bytes = 4-word stride, and

g cd (4, 32) = 4

gives a 4-way conflict on every field. "Nice" power-of-two sizes are precisely the dangerous ones.

"matrix[row][tid] and matrix[tid][col] both walk stride-1, so both are fine."

Only the first is stride-1. Row-major [tid][col] walks down a column with stride 32 words, so every thread hits the same bank — a 32-way conflict.

"Switching from array-of-structures to structure-of-arrays is just a style choice."

SoA forces every field into a stride-1 array, guaranteeing conflict-freedom regardless of struct size, so it removes a real correctness-of-performance hazard, not just aesthetics.

"bank = (i·33 + col) mod 32 still has that ×33, so it can't be conflict-free."

Because

33 \equiv 1 (mod 32)

, the whole thing collapses to

(i + col) mod 32

, which sweeps all 32 banks as

i

runs 0..31 — perfectly conflict-free.

"To find the bank of matrix[i][j] in words, divide the word index by 4 again."

No — the

/4

converts bytes to words. Once you are already in word units, you apply

mod 32

directly; dividing again double-counts the word width.

Why questions

Why does shared memory have banks at all instead of one big block

One monolithic block could serve one address per cycle; 32 banks let a warp's 32 requests complete in parallel, the whole point covered in 6.2.07-Shared-memory-architecture.

Why is the conflict degree

g cd (s, 32)

and not just

s

Threads repeat banks every

32/ g cd (s, 32)

steps, so exactly

g cd (s, 32)

threads pile onto each bank; the shared factor with 32, not

s

itself, sets how many collide.

Why does padding to 33 (not 34 or 40) fix the transpose case

33 is the smallest inner width with

33 \equiv 1 (mod 32)

, giving a per-row bank shift of exactly 1. Any width

\equiv 1 (mod 32)

works, but 33 wastes the least memory.

Why do broadcasts not count as conflicts

A conflict is serialized different data; a broadcast is the same address duplicated to many threads, which the hardware satisfies with one read shared to all — one cycle, no penalty.

Why does the column-walk conflict matter so much in practice

Matrix transpose reads a row and writes a column (or vice versa), so the column-walk 32-way conflict is unavoidable without padding — the core motivation of 6.3.01-Matrix-transpose-optimization.

Why can't you just always use SoA and forget about conflicts

SoA fixes stride, but you can still create conflicts with strided indexing (e.g. x[tid*2]), and it can hurt other goals like cache locality; it removes the struct-size trap, not all conflict risk.

Edge cases

A warp where all 32 threads read the identical address — conflict?

No — identical addresses trigger a broadcast, resolved in a single cycle. This is the harmless extreme, not the worst case.

A warp where all 32 threads read 32 different addresses that all map to bank 0

This is the true worst case: a 32-way conflict, fully serialized over 32 cycles. Different addresses + same bank is what serializes.

Stride 0 (every thread computes the same index) — what happens

With

s = 0

every thread's word is identical, so it's the same-address broadcast case — one cycle, conflict-free, not a

g cd (0, 32)

disaster.

A half-warp of 16 active threads with the other 16 masked off

Only active threads issue addresses, so conflicts are computed among the live lanes; masked threads contribute nothing, which can turn a "32-way" pattern into a milder one. See 6.2.11-Warp-divergence for how masks arise.

Stride equal to 32 exactly

g cd (32, 32) = 32

— the maximal 32-way conflict, since every thread lands on the same bank. This is the column-walk case in disguise.

Padding so aggressively that occupancy suffers

Extra padding grows the shared-memory footprint per block, which can reduce how many blocks fit per SM — a trade-off tracked by 6.2.10-Occupancy-and-resource-limits. Fix conflicts, but watch the memory budget.

Recall One-line litmus test

To judge any strided shared-memory access: reduce to a word stride $s$ , compute $g cd (s, 32)$ . Result 1 = conflict-free; result $d$ = $d$ -way conflict = $d$ cycles.