Skip to main content

Thread Coarsening: More Work per Thread Block in CUDA

A tiled matrix multiply repeats global loads across neighboring blocks. Let one block compute several output tiles, then calculate the loads it saves and the SM slots it leaves idle.

Thread coarsening is an item on GPU performance checklists. Instead of launching one thread block for each piece of output, each block does the work of several, so that loads its neighbors would repeat are made once. The price is a smaller launch. A tiled matrix multiply shows both sides, and this page calculates them.

The price of parallelism

A launch with many small blocks is easy to spread over a GPU, but the blocks do not share anything. When the launch has more blocks than the GPU can run at once, the hardware runs them in turns anyway, and in a tiled matrix multiply every block in one row of output tiles loads the same tiles of A. Parallelism that the hardware cannot use at once is paid for with repeated work. Coarsening gives up some of that parallelism to remove the repetition.

A tiled matrix multiply, briefly

Each block of the tiled kernel computes one 32 x 32 tile of the output matrix, the product of A and B. The block walks along the shared dimension one phase at a time. In each phase it loads one 32 x 32 tile of A and one of B into shared memory, synchronizes, and every thread adds 32 products to its running sum. The memory hierarchy page covers shared memory, and the shared memory section of the CUDA matmul article builds the matching CUDA kernel, so this page does not repeat it.

C++
// C = A * B for square width x width row-major matrices. TILE is 32.
// Launch with dim3(TILE, TILE) threads per block and a
// dim3(width / TILE, width / TILE) grid. width must be a multiple of TILE.
// Each block computes one TILE x TILE tile of C.
__global__ void matmul_tiled(const float *A, const float *B, float *C,
                             int width) {
  __shared__ float a_tile[TILE][TILE];
  __shared__ float b_tile[TILE][TILE];

  int row = blockIdx.y * TILE + threadIdx.y;
  int col = blockIdx.x * TILE + threadIdx.x;
  float sum = 0.0f;

  // Walk along the shared dimension one tile at a time.
  for (int phase = 0; phase < width / TILE; ++phase) {
    a_tile[threadIdx.y][threadIdx.x] =
        A[row * width + phase * TILE + threadIdx.x];
    b_tile[threadIdx.y][threadIdx.x] =
        B[(phase * TILE + threadIdx.y) * width + col];
    __syncthreads();

    for (int k = 0; k < TILE; ++k) {
      sum += a_tile[threadIdx.y][k] * b_tile[k][threadIdx.x];
    }
    __syncthreads();
  }

  C[row * width + col] = sum;
}

With T = 32, a block loads 2 T^2 = 2,048 elements per phase for each output tile. The block one tile to the right loads the same A tile again.

Coarsening

In the coarsened kernel, one block computes C neighboring output tiles in a row. In each phase it loads the A tile once and then the C tiles of B, one at a time, and each thread keeps C running sums, one for each output tile. The shared memory stays at two 32 x 32 tiles, 8,192 bytes, for every C, because only one B tile is held at a time.

C++
// C = A * B for square width x width row-major matrices. TILE is 32.
// Launch with dim3(TILE, TILE) threads per block and a
// dim3(width / (TILE * COARSE), width / TILE) grid. width must be a multiple
// of TILE * COARSE. Each block computes COARSE neighboring TILE x TILE tiles
// of C in one row, so it loads each A tile once and reuses it COARSE times.
// Shared memory is two TILE x TILE tiles (8 KB) for every COARSE, because
// only one B tile is held at a time.
template <int COARSE>
__global__ void matmul_coarsened(const float *A, const float *B, float *C,
                                 int width) {
  __shared__ float a_tile[TILE][TILE];
  __shared__ float b_tile[TILE][TILE];

  int row = blockIdx.y * TILE + threadIdx.y;
  int first_col = blockIdx.x * COARSE * TILE + threadIdx.x;
  float sum[COARSE];
  for (int c = 0; c < COARSE; ++c) {
    sum[c] = 0.0f;
  }

  for (int phase = 0; phase < width / TILE; ++phase) {
    // The A tile is loaded once per phase and used for all COARSE tiles.
    a_tile[threadIdx.y][threadIdx.x] =
        A[row * width + phase * TILE + threadIdx.x];

    for (int c = 0; c < COARSE; ++c) {
      // One B tile at a time. The first barrier also publishes the A tile.
      b_tile[threadIdx.y][threadIdx.x] =
          B[(phase * TILE + threadIdx.y) * width + first_col + c * TILE];
      __syncthreads();

      for (int k = 0; k < TILE; ++k) {
        sum[c] += a_tile[threadIdx.y][k] * b_tile[k][threadIdx.x];
      }
      // No thread may overwrite b_tile, or a_tile after the last c, until
      // every thread has read it.
      __syncthreads();
    }
  }

  for (int c = 0; c < COARSE; ++c) {
    C[row * width + first_col + c * TILE] = sum[c];
  }
}

The kernels on this page are in coarsening.cu; its README gives the build command, the inputs checked, the recorded run and the compiler's register report. They were compiled and checked for correct output against a CPU reference on an RTX A6000, and they were not timed.

Per phase, a coarsened block loads (1 + C) T^2 elements for C output tiles. C separate blocks of the tiled kernel load 2 C T^2 elements for the same tiles. Global loads therefore fall to (1 + C) / (2 C) of the uncoarsened kernel: 75% at C = 2, 62.5% at C = 4, 56.3% at C = 8 and 53.1% at C = 16. The ratio approaches one half and never reaches it, because the B tiles are still loaded once for every output tile. The mechanism is the A tile that is loaded once and reused C times, which the figure below does not show. It shows the effect on the loads and on the launch.

What the figure calculates

The figure computes for a square multiply of width W with 32 x 32 tiles. There are (W / 32)^2 output tiles and (W / 32)^2 / C blocks. Slots are the SMs times one block per SM. Waves are the blocks divided by the slots, rounded up. The first-wave fill is the number of slots that hold a block in the first wave, as a share of the slots. Start at factor 4, W = 1,024 and the RTX 5090, then change one control at a time.

Thread coarsening trade-off
Factor
Matrix
GPU

Output tiles, colored by block

All 32 x 32 tiles. A run of 4 tiles is one block.

Loads and first-wave fill, by factor

1,024 x 1,024 matrices on RTX 5090, 170 slots. The line marks factor 4.

Coarsening factor

global loads, share of factor 1 (solid)slots busy in the first wave (dashed)

Calculated, not measured. Loads count elements requested from global memory and ignore caches. The model assumes one 1,024-thread block per SM, so the slots are the SMs.

At 1,024 x 1,024 the multiply has 1,024 output tiles. Uncoarsened, the kernel launches 1,024 blocks and requests 67,108,864 elements from global memory. At factor 4 it launches 256 blocks and requests 41,943,040, which is 62.5% of the first number. These counts are elements requested, with caches ignored.

On the RTX 5090, with 170 slots, the 256 blocks of factor 4 need 2 waves: the first fills all 170 slots, and the second holds the other 86. At factor 8 there are 128 blocks, a single wave in which 128 of 170 slots are busy, 75.3%, and 42 stay idle. The loads fall only to 56.3% of factor 1, so the second step saved less than the first. It also did not raise the share of slots kept busy: factor 4 has 86 blocks in a partly empty second wave, and factor 8 moves those idle slots into the single wave. On the A100, with 108 slots, the same 128 blocks need 2 waves, with a full first wave of 108 and 20 blocks in the second.

Coarsening changes how many blocks fill the first wave and also how full the last wave is. Over the whole run, the share of slots that hold a block is the blocks divided by waves times slots, the wave factor that the tile and wave quantization page calculates. At W = 1,024 on the RTX 5090, factor 1 launches 1,024 blocks in 7 waves, with 4 in the last, and keeps 86.1% of the slots busy. Factors 2, 4 and 8 keep 75.3%: 512 blocks in 4 waves with 2 in the last, 256 blocks in 2 waves with 86 in the last, and 128 blocks in 1 wave. These shares are calculated from the block counts, not timed.

The smallest matrix shows the limit. At W = 512 there are 16 x 16 output tiles, and factor 16 makes one block for each row, 16 blocks in all. They fill 16 of 170 slots, 9.41%, for the whole launch. The output map draws the top-left 32 x 32 tiles when there are more, as at W = 4,096, where factor 1 launches 16,384 blocks.

Costs

  • Fewer blocks. A launch with fewer blocks than slots leaves SMs idle for its whole run, and a launch whose block count is just over a multiple of the slots ends with a nearly empty wave. The tile and wave quantization page calculates that rounding.
  • More registers per thread. A thread with C running sums needs registers for them, and a kernel that needs more registers per thread can fit fewer threads on an SM. That lowers occupancy, which the occupancy section of the SM page describes as one of three competing limits. This is a general risk. For these kernels compiled for the RTX A6000 (sm_86) with CUDA 12.3 and nvcc -O2 -Xptxas -v, ptxas reports 36 registers per thread for the tiled kernel and the C = 1 kernel and 40 for every coarsened kernel from C = 2 to C = 16, so in this compile the count does not grow with C beyond C = 2 (compile output, recorded in the check program's README). Other architectures and compilers can report different counts, so check the count for the kernel and target in use, for example with -Xptxas -v.
  • Fewer warps. When several blocks share an SM, fewer blocks mean fewer warps ready to cover the latency of a load, as the latency section of the SM page explains. Under the figure's one-block-per-SM model each SM that runs a block holds 32 warps at every factor, so the figure does not show this cost.

The thread limit is what makes the figure assume one block per SM. A block of this kernel has 32 x 32 = 1,024 threads. For compute capability 12.0, which NVIDIA's CUDA GPUs list gives to the GeForce RTX 5090, the occupancy section of the Blackwell Tuning Guide gives 48 concurrent warps per SM, which is 1,536 threads, so a second 1,024-thread block cannot be resident. The A100 preset uses the same one-block assumption so that the two GPUs differ only in their SM count. It is an assumption of the figure, not a property of every kernel.

Coarsening pays most when the launch has many more blocks than the GPU runs at once. Under the figure's one-block-per-SM model, the blocks beyond the first wave run in turns anyway, so merging them removes repeated loads without taking away work the GPU could run at the same time. A launch that still fills the first wave can nevertheless end on a partly empty wave, so the busy share can fall even then, as the W = 1,024 numbers above show. Once the launch fits in one wave, coarsening still cuts loads, but only by leaving SMs idle: at W = 512 on the RTX 5090, going from factor 2 to factor 4 keeps one wave, cuts the blocks from 128 to 64 and the loads from 75% to 62.5% of factor 1, and lowers the first-wave fill from 75.3% to 37.6%. The chapter on performance considerations in Programming Massively Parallel Processors discusses when coarsening pays and the cost of applying it where it is not needed.

Coarsening elsewhere

  • Register tiling. The register tiling section of the CUDA matmul article has each thread compute an 8 x 8 block of outputs, so one value loaded from shared memory feeds several multiply-adds. That is coarsening applied to threads inside the block.
  • Kernel 3 of the eight-kernels article. Kernel 3 gives each thread several output values and keeps their running sums in registers, so it is a worked case of the same idea. This page repeats none of that article's measured numbers.
  • Grid-stride loops. In an elementwise kernel, each thread loops over elements spaced a grid apart, so a launch of any size covers any input.
  • The histogram. On the privatization page, each block merges a private copy into global memory. Giving each thread more input values means fewer blocks to launch, and so fewer copies to merge.

Further reading

If you found this explanation helpful, consider sharing it with others.

Mastodon