Memory

Global Memory Coalescing

Global Memory Coalescing

Global memory (device DRAM) is served in 128-byte cache line transactions. Whether a warp of 32 threads consumes 1 transaction or 32 depends entirely on the access pattern.

How Transactions Work

When a warp issues a load or store:

  1. ▸The hardware collects all 32 thread addresses
  2. ▸It groups them into 128-byte aligned cache line segments
  3. ▸One memory transaction is issued per unique segment required

Best case — fully coalesced: 32 threads × 4-byte float = 128 bytes, all within one 128-byte aligned segment → 1 transaction, peak bandwidth (~1–3 TB/s)

Worst case — fully divergent: 32 threads each touch a different 128-byte cache line → 32 transactions, ~3% of peak bandwidth

Access Pattern Impact

| Pattern | Transactions | Bandwidth efficiency | |---|---|---| | Stride-1: array[i] | 1 | ~100% | | Stride-2: array[2*i] | 2 | ~50% | | Stride-4: array[4*i] | 4 | ~25% | | Stride-32: array[32*i] | 32 | ~3% | | Random | up to 32 | ~3% |

Alignment

cudaMalloc guarantees 256-byte aligned base pointers. Misaligned accesses can add extra transactions even for stride-1 patterns. Use __align__(16) for structs in device memory.

The Column-Access Problem

Row-major storage: A[row][col] = A[row * N + col]

  • ▸Row access — thread i reads A[row * N + i]: consecutive threads touch consecutive addresses → coalesced ✓
  • ▸Column access — thread i reads A[i * N + col]: consecutive threads are N elements apart → non-coalesced ✗

Matrix transpose is the canonical example: one direction of access is always non-coalesced unless you use shared memory as a staging tile.

The Shared Memory Fix

Standard pattern for correcting non-coalesced access:

  1. ▸Coalesced read from global memory → shared memory tile
  2. ▸__syncthreads()
  3. ▸Read from shared memory in any order (no coalescing penalty)
  4. ▸Coalesced write from shared memory → global memory

This turns one non-coalesced pass into two coalesced passes — net win once the tile has enough reuse.

The __restrict__ Qualifier

Tells the compiler two pointers don't alias, enabling better instruction scheduling and load/store optimization:

c
__global__ void scale(float * __restrict__ out,
                      const float * __restrict__ in, float s, int n) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i < n) out[i] = in[i] * s;
}

Measuring Bandwidth

effective_bandwidth (GB/s) = bytes_transferred / time_s / 1e9

For a simple copy kernel (1 read + 1 write per element):

c
float ms; cudaEventElapsedTime(&ms, t0, t1);
float bw = 2.0f * N * sizeof(float) / ms / 1e6f;  // GB/s
printf("%.1f GB/s (peak: %.1f GB/s)\n", bw, peakBandwidth);

// CODE EXAMPLE

example.cu
#define N    1024
#define TILE 32

// SLOW: non-coalesced — consecutive threads are N elements apart
__global__ void colSumNaive(const float *A, float *out, int n) {
    int col = blockIdx.x * blockDim.x + threadIdx.x;
    if (col >= n) return;
    float sum = 0.f;
    for (int row = 0; row < n; row++)
        sum += A[row * n + col];  // stride-N access: 1 transaction per thread
    out[col] = sum;
}

// FAST: coalesced via shared memory staging
__global__ void colSumShared(const float *A, float *out, int n) {
    __shared__ float tile[TILE][TILE];

    int col = blockIdx.x * TILE + threadIdx.x;
    int row = blockIdx.y * TILE + threadIdx.y;

    // Coalesced read: all threads in a row access consecutive columns
    if (row < n && col < n)
        tile[threadIdx.y][threadIdx.x] = A[row * n + col];
    __syncthreads();

    // Now accumulate from shared memory (fast, no coalescing requirement)
    if (blockIdx.y == 0 && col < n) {
        float sum = 0.f;
        for (int k = 0; k < TILE; k++) sum += tile[k][threadIdx.x];
        atomicAdd(&out[col], sum);
    }
}

// TRY IT

GPU execution
main.cu
loading editor…