Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 31 ยท Memory

Bank Conflicts and Padding

Learn how CUDA shared memory is split into 32 banks, which access patterns conflict, how padding removes conflicts and why a tiled transpose needs it.

Shared memory is fast, but only when the 32 threads of a warp spread their accesses across its internal pieces. Shared memory is built from 32 banks, like 32 independent single-lane roads. If every thread of the warp uses a different road, all 32 accesses happen in one step. If several threads want the same road at the same time, the hardware has to serialize them, and a load that should take one step takes two, four or even 32. This slowdown is called a bank conflict.

You can avoid almost all bank conflicts with one simple trick: add one unused column to a shared array. This lesson shows exactly how banks work, which patterns conflict, why padding fixes them, and how that makes the tiled matrix transpose fast. It builds directly on Shared Memory and Tiling.

CUDA code is read-only here because the site has no GPU. The Python examples count conflicts with the same rule the hardware uses for ordinary 32-bit accesses, so their numbers are exact for that rule. Real kernels may differ in details such as 64-bit accesses and compiler transformations; confirm with the profiler.

How banks are laid out

Think of shared memory as a sequence of 4-byte words. Word 0 lives in bank 0, word 1 in bank 1, and so on up to word 31 in bank 31. Word 32 wraps around to bank 0 again. In one formula:

Text
bank = word_index % 32

where word_index is the byte address divided by 4. For a float array s, element s[i] is word i, so it sits in bank i % 32.

flowchart LR
    subgraph row0["Words 0 to 31"]
        B0["bank 0"] --- B1["bank 1"] --- B2["..."] --- B31["bank 31"]
    end
    subgraph row1["Words 32 to 63"]
        C0["bank 0"] --- C1["bank 1"] --- C2["..."] --- C31["bank 31"]
    end
    row0 --> row1

Consecutive words go to consecutive banks, then the pattern repeats every 32 words.

When a warp executes a shared memory load or store, the hardware checks the 32 word indices:

  • If all threads hit different banks, the access takes one step.
  • If several threads hit the same word of one bank, that word is read once and broadcast; no conflict.
  • If threads hit different words in the same bank, those accesses are serialized. The cost is the largest number of different words that any single bank must serve: an n-way bank conflict takes n steps.

Counting conflicts

The function below is the whole rule in a few lines: group the word indices by bank, count the distinct words in each bank, and take the maximum.

Python Bank-conflict counter for strides

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at what the output teaches:

  • Stride 1 (neighbouring threads, neighbouring words) is conflict-free: each thread owns one bank.
  • Stride 2 gives a 2-way conflict, stride 4 a 4-way conflict and so on up to stride 32, a 32-way conflict. With stride 32 every thread's word is a multiple of 32, so all land in bank 0 and the warp needs 32 steps.
  • Strides 3 and 33 are conflict-free. The rule: a stride is conflict-free exactly when it shares no common factor with 32, that is, when it is odd. Any even stride shares a factor of two or more.
  • A broadcast, every thread reading the same word, costs one step.

The classic trap: column access in a tile

Stride 32 is not exotic. It appears whenever threads of a warp walk down a column of a 32-wide shared array. Take __shared__ float tile[32][32]. Element tile[row][col] is word row * 32 + col. If thread t reads tile[t][c] for a fixed c, the word index is t * 32 + c: stride 32, all in bank c.

That is exactly what a transpose does. A transpose reads a tile row by row from global memory, which is coalesced, then writes it to global memory also row by row, which means reading the shared tile column by column:

C++
#define TILE 32

__global__ void transposeNaive(const float* in, float* out, int n) {
    __shared__ float tile[TILE][TILE];
    int x = blockIdx.x * TILE + threadIdx.x;
    int y = blockIdx.y * TILE + threadIdx.y;
    tile[threadIdx.y][threadIdx.x] = in[y * n + x];   // row write: conflict-free
    __syncthreads();

    x = blockIdx.y * TILE + threadIdx.x;              // swap the block coordinates
    y = blockIdx.x * TILE + threadIdx.y;
    out[y * n + x] = tile[threadIdx.x][threadIdx.y];  // column read: 32-way conflict
}

The global memory traffic is perfect (both the read and the write are coalesced), but the shared read tile[threadIdx.x][threadIdx.y] has 32 threads hitting the same bank.

Padding fixes it

Change the declaration to __shared__ float tile[TILE][TILE + 1];. Now row r starts at word r * 33. A column walk becomes stride 33, which is odd, and therefore conflict-free. The row access (tile[ty][tx]) is still stride 1. The extra column is never used; it just shifts each row by one bank.

The next program measures both layouts for the full transpose of one 32 x 32 tile: 32 warps write rows, and 32 warps read columns.

Python Padding a transpose tile

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the unpadded tile, each of the 32 column-reading warps needs 32 steps, 1,024 in total, against 32 for the padded tile. The writes are unaffected. The price is 128 bytes of shared memory per tile, which is a bargain. In practice this one-character change is often worth a large speed-up on the transpose kernel, though the exact gain depends on the GPU.

The fixed version in CUDA:

C++
__global__ void transposeFast(const float* in, float* out, int n) {
    __shared__ float tile[TILE][TILE + 1];            // +1 column of padding
    int x = blockIdx.x * TILE + threadIdx.x;
    int y = blockIdx.y * TILE + threadIdx.y;
    if (x < n && y < n) tile[threadIdx.y][threadIdx.x] = in[y * n + x];
    __syncthreads();

    x = blockIdx.y * TILE + threadIdx.x;
    y = blockIdx.x * TILE + threadIdx.y;
    if (x < n && y < n) out[y * n + x] = tile[threadIdx.x][threadIdx.y];
}

In a real launch you would use a 32 x 8 thread block with each thread handling four rows of the tile (a loop over j += 8), to reduce per-thread overhead. That variant is a refinement; the padding is the essential idea.

Does the transpose still come out right?

Padding changes where elements are stored but not what they mean. This model runs the tiled transpose with a padded tile and checks it against NumPy's .T.

Python Padded tiled transpose is still correct

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other ways to avoid conflicts

Padding is the most common fix, but not the only one:

  • Swizzling: instead of padding, permute the column index with an XOR, for example tile[row][col ^ row]. The array stays square (no wasted memory) and the column walk becomes conflict-free. Libraries such as CUTLASS use this heavily.
  • Change the access pattern, for instance by letting each thread process an element in a different order.
  • Use a different data layout for the shared array so warps walk along rows, not columns.

Remember that bank conflicts only exist within one warp's access. Two different warps touching the same bank at different moments never conflict with each other.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Shared memory has 32 banks. Which bank holds the float s[70]?

    The bank is the word index modulo 32, and 70 mod 32 is 6.
  2. 2. All 32 threads of a warp read the same shared float. What happens?

    Reading one word from one bank is served once and broadcast to every thread that asked for it, so there is no conflict.
  3. 3. Thread t reads s[2 * t] from a float array. What is the conflict degree?

    Even strides share a factor with 32. With stride 2, the 32 threads use only 16 banks, two distinct words per bank, so each bank serves two accesses.
  4. 4. Why does declaring tile[32][33] speed up a transpose?

    With a row length of 33 words, walking down a column advances 33 words per thread. That is odd, so every thread falls in a different bank.

Summary

  • Shared memory has 32 banks of 4-byte words; the bank of word i is i % 32.
  • Different words in one bank serialize (an n-way conflict costs n steps); identical words are broadcast for free.
  • Odd strides are conflict-free; even strides conflict, and stride 32 is the worst case at 32-way.
  • Walking down a column of a 32-wide shared array is a stride-32 access, which is why the naive tiled transpose is slow.
  • Padding the row length to 33 (or swizzling the index) removes the conflict for a tiny cost in memory.
  • Conflicts matter only within a single warp's access.

Next, we leave the chip and look at the cost of moving data between host and device: Moving Data: Pinned, Managed and Unified Memory.