Aaron Ang

Optimizing Matrix Multiply on CUDA, Part 1

A kernel is a function that runs on the GPU. An SGEMM kernel is single-precision general matrix multiply, using 32-bit floats. As part of a graduate course at UCSD, Jerry Ma and I wrote an SGEMM kernel to get as close as possible to NVIDIA’s cuBLAS. Our first correct kernel ran at around 100 GFLOP/s (billion floating-point operations per second). The last hit 4,780 GFLOP/s at N=2048N = 2048, roughly matching cuBLAS on the same T4.

Neural network operations such as attention, fully connected layers, and convolutions all use matrix multiply, so there is a lot of value in studying and optimizing this component. An NVIDIA T4 can do about 24 floating-point operations in the time it takes to fetch one byte. Meanwhile, the textbook algorithm boils down to just 0.25 operations per byte. How do we make up that difference?

The naive kernel gives each output its own thread, but each thread fetches its inputs repeatedly. Our implementation will try to have them share that work. The kernels are written in CUDA, with the code on GitHub.

We borrowed heavily from Simon Boehm’s worklog, which is well worth reading. We’ll follow the same optimizations here, with more background and our own measurements on the T4 GPU.

Counting the Work

Take C[i][j]C[i][j], the dot product of row ii of AA and column jj of BB. For N×NN \times N inputs, we multiply and add NN pairs. Counting a multiply-add as two floating-point operations (flops), that’s 2N2N flops for this output and 2N32N^3 for all N2N^2 outputs. At N=2048N = 2048, the kernel has about 17 billion flops to do.

Now move one column over to C[i][j+1]C[i][j+1]. The BB values change, but we need the same row of AA again:

One entry of C forms as the dot product of a row of A and a column of B, one multiply-add at a time. The next entry reads the same row of A again.
No kernel can skip any of the NN multiply-adds per output. To make a kernel faster, we need to fetch each value from main memory fewer times.

To see how much data reuse the kernel needs, we can compare the T4’s peak arithmetic throughput with its memory bandwidth:

Dividing peak throughput by memory bandwidth gives 7,680/320=247{,}680 / 320 = 24 flops per byte. To sustain that throughput, the kernel would need to perform about 24 flops for every byte fetched from global memory. Our naive kernel is far below that ratio: thread 0, which computes C[0][0]C[0][0], loads one 4-byte float from AA and another from BB for each multiply-add. Those 8 bytes support only 2 flops, giving 0.25 flops per byte, almost 100 times below the ratio needed to sustain peak throughput.

This ratio of flops to bytes fetched is called arithmetic intensity.1 We’ll follow thread 0 through the optimizations and count its loads per multiply-add, including its share when several threads divide up the work of loading their inputs.

Stage 1: Coalescing

A CUDA kernel launches thousands of threads. The hardware runs them 32 at a time, in groups called warps. The 32 threads of a warp move in lockstep, one instruction at a time. Warps are grouped into thread blocks (blocks for short), and each block is assigned to one SM.

In the naive kernel, each thread computes one output by looping over kk, the index along the shared dimension KK (the columns of AA and the rows of BB). Thread 0 loads A[0][k]A[0][k] and B[k][0]B[k][0] from global memory at each step. The cost of these loads also depends on the addresses requested by the other threads in its warp, because the GPU serves their requests in chunks called transactions.

When a warp reads 32 consecutive floats, the GPU can merge (coalesce) those requests into a few transactions. Addresses spread far apart may instead need a transaction each, transferring a chunk of memory for just one requested float. The figure below compares how much memory is transferred for the same number of values:

Eight threads of one warp load from global memory. Scattered addresses need one transaction each; consecutive addresses share a single wide transaction.
Eight threads stand in for a warp’s 32; the pattern is the same at full width.

Our first assignment put neighboring threads on neighboring rows of CC, leaving their AA reads NN floats apart. Switching those threads to neighboring columns made their BB reads and CC writes contiguous, so the GPU could serve the warp’s requests with fewer transactions. Throughput increased by roughly an order of magnitude,2 although each thread still requested 2 global-memory values per multiply-add. The improvement came from transferring fewer unused bytes with those requests.

Stage 2: Shared-Memory Tiling

Thread 0 reads all of row 0 of AA, but the threads computing C[0][1]C[0][1] and C[0][2]C[0][2] need that same row too. Keeping a copy near those threads would let them reuse it rather than fetch it again. For this, we can compare global memory with CUDA’s shared memory:

We can’t keep all of AA and BB in that small scratchpad. Instead, we assign a square tile of CC to the block and walk through KK a chunk at a time. Each chunk is a KK slice (slice for short).

The threads first divide up the loads for two input tiles, one from AA and one from BB. After __syncthreads(), they can all read the shared copies to update their partial sums. Reuse that storage for the next slice and repeat until the output tile is finished:

For each K slice, a block copies one tile of A and one of B from global into shared memory, waits at a barrier, and every thread reads both tiles to update its running sum.
Each grid cell is a whole tile, not a single value.

With a T×TT \times T tile, each value fetched from global memory contributes to TT outputs, giving roughly T/4T/4 flops per byte. A 32×32 tile therefore raises arithmetic intensity from 0.25 to 8 flops per byte, a factor of 32. Measured throughput increased by only 20%–70%, reaching about 1,000 GFLOP/s, so reducing global-memory traffic had not removed all the work limiting the kernel.

Let’s observe the two kinds of loads for thread 0. Its share of the block’s global loads is now 1 per 16 multiply-adds, down from 2 per multiply-add. Shared-memory loads are still 2 per multiply-add: one input from AA, one from BB.

Shared-memory reads still consume instructions and bandwidth inside the SM. Giving each thread several outputs would let it keep inputs in registers and reuse them across multiply-adds, reducing those reads as well.

Stage 3: Register Tiling

The fastest storage on the GPU is the register file, with 64K 32-bit registers per SM. Registers are private to each thread and are where arithmetic happens. By giving a thread more outputs to compute, register tiling lets it use one value loaded from shared memory for several multiply-adds. We approached this in two steps.

1-D tiling gives each thread a short column of outputs instead of a single one. One value loaded from BB’s tile then serves every output in that column. According to the course report, throughput on the T4 nearly doubled.

For 2-D tiling, let’s give thread 0 rows 0–7 and columns 0–7 of CC: an 8×8 patch within the block’s tile. It still loops over kk, but only across the slice currently in shared memory. At each step kk, the thread loads 8 values from column kk of AA’s tile and 8 values from row kk of BB’s tile into registers. It then multiplies every AA value by every BB value. This is an outer product, and it gets 64 multiply-adds from 16 loads.

The figure below shows the outer product that each thread computes:

One thread holds an 8×8 patch of C in registers. At each step k it loads 8 values of A and 8 of B, then does all 64 multiply-adds between them.
The 64 running sums stay in registers for the whole KK loop and are written to CC once, at the end.

This reduces shared-memory loads per multiply-add eightfold, from 2 to 0.25.

The inner loop of the final T4 kernel looks like this (unrolling pragmas omitted):

for (uint dotIdx = 0; dotIdx < TILEDIM_K; ++dotIdx) {
    for (uint i = 0; i < TILESCALE_M; ++i)
        regM[i] = As[threadRow * TILESCALE_M + i][dotIdx];
    for (uint i = 0; i < TILESCALE_N; ++i)
        regN[i] = Bs[dotIdx][threadCol * TILESCALE_N + i];
    for (uint m = 0; m < TILESCALE_M; ++m)
        for (uint n = 0; n < TILESCALE_N; ++n)
            threadResults[m][n] += regM[m] * regN[n];
}

The final T4 configuration:

This configuration is essentially kernel 5 in Boehm’s worklog. On the T4, it raised throughput from ~1,000 to 4,780 GFLOP/s.

Getting this short loop right took most of our implementation time. We initially interpreted “block tile” as the tile assigned to each thread, so every thread computed a large tile on its own. That made the kernel slower than 1-D tiling: its shared-memory loads no longer coalesced, and each thread needed more storage than its registers could hold.

With help from the course TA, we clarified the distinction between the block’s output tile and the smaller patch computed by each thread. The block shares the input tiles in shared memory, while each thread holds only its own patch’s running sums in registers. Choosing the thread grid and patch dimensions together sets the block’s output tile, which led us to try the combinations below:

Configuration sweep at N=2048N = 2048 (GFLOP/s)
Threads per blockOutputs per threadBlock tileThroughput
32×322×264×64~2,210
8×88×864×64~2,470
16×164×464×64~3,720
16×168×8128×1284,780

With only a 2×2 patch per thread, the kernel still spent most of its execution time loading values, with little reuse across outputs. Keeping the grid at 16×16 threads and increasing each patch from 4×4 to 8×8 raised throughput from ~3,720 to 4,780 GFLOP/s. The larger patch also quadrupled the running sums held by each thread, so we needed to account for that register usage when examining occupancy.

Performance Analysis

Register tiling raised the kernel’s throughput to 4,780 GFLOP/s, compared with around 100 GFLOP/s for the first version. The table below compares each stage with cuBLAS, before we examine what still kept our kernel below the T4’s peak throughput:

Throughput by stage (GFLOP/s, NVIDIA T4)
StageIdeaThroughput
NaiveOne thread per output, everything from global memory~35–120
CoalescedNeighboring threads read neighboring addresses~550–860
Shared-memory tilingA block stages tiles of AA and BB on-chip~650–1,030
2-D block tilingEach thread computes an 8×8 patch from registersup to 4,780
cuBLASNVIDIA’s library, for reference~2,450–4,570
Ranges span the matrix sizes we tested, from N=256N = 256 to N=2049N = 2049.

The peak timing hides some awkward cases. Our largest tile is actually the slowest at small NN, and adding one row and column can cause a large throughput drop. Before looking at those cases, let’s check how close this kernel is to the hardware’s limits.

The Roofline

We counted flops per byte and measured flops per second. Williams, Waterman, and Patterson’s roofline puts those on the x- and y-axes of one plot. At low intensity, multiplying bandwidth by intensity gives the throughput ceiling. As intensity increases, that sloped ceiling reaches peak compute and becomes flat. The meeting point, or ridge, is about 24 flops per byte for our T4.

The shared-memory kernel with 32×32 tiles and the final 128×128 kernel sit on the roofline as shown below:

Schematic roofline: a sloped memory roof meets a flat compute roof at the ridge. The 32×32 shared-memory kernel sits left of the ridge, below the memory roof; the 128×128 tile moves it past the ridge at about 24 flops per byte, to 32.
Both axes are log scale, and the positions are schematic, not measured.

The 128×128 block tile performs 64 multiply-adds per value loaded from global memory: 128 flops for each 4-byte float, or 32 flops per byte.3 That places the kernel to the right of the ridge even though it reaches only 62% of peak compute. The roofline suggests that further global-memory reuse would offer less than reducing work within the SM, where shared-memory loads, indexing, and barriers could account for the remaining gap.

One possible cost was bank conflicts in the shared-memory reads. Shared memory has 32 banks, and when threads in a warp request different values from the same bank, those reads have to take separate turns. We estimated roughly 2 threads per bank when reading BB’s tile, requiring about 2 turns instead of 1. This gave us a reason to investigate the access pattern further, though we didn’t measure a bank-conflict fix on the T4.

Occupancy

An SM can run another ready warp while one waits on memory. How many does our kernel give it to choose from? A T4 SM has 32 warp slots, and the fraction occupied by resident warps is occupancy. To find ours, we need to count registers and shared memory.

Registers. On paper, a thread needs about 80 registers for its 64 accumulators and 16 values from AA and BB. The compiler’s ptxas -v output reports 172 per thread, since pointers, indices, and loop counters also need storage. The exact count varies slightly between CUDA versions, but we need to budget for the compiled kernel rather than just the variables counted by hand. At 172 registers each, a block of 256 threads needs about 44,000 of the SM’s 65,536 registers, leaving room for only one block. Two blocks would require at most 128 registers per thread.

Shared memory. Each block needs 32 KB for its tiles, so the SM’s 64 KB could hold two blocks if the register budget allowed it.

The resident block has 8 warps in an SM with 32 warp slots, giving us 25% occupancy. Yet we’re reaching 62% of peak compute with three-quarters of those slots empty. Vasily Volkov’s Better Performance at Lower Occupancy explains another way to hide latency: fewer warps, each with lots of independent work. Thread 0 has 64 independent accumulators, so dozens of multiply-adds can issue while a load is in flight.

Small and Odd Sizes

The largest configuration in the sweep (128×128 tile) did not win at every size. At N=256N = 256, it was the slowest of the four, at under 500 GFLOP/s. Every configuration also lost throughput when NN was just past a multiple of the tile size, which this post calls an odd size:

Best kernel at different sizes (GFLOP/s)
NNTiles of 128 per sideGFLOP/s
512exactly 42,167
1023just under 83,830
1024exactly 83,920
1025just over 8~2,900
2048exactly 164,780
2049just over 164,181
Measured on an NVIDIA T4 with the 16×16 threads, 8×8 per thread configuration.

At the edges of a matrix that isn’t a multiple of 128, tiles hang off the right and bottom sides. We need bounds checks, with lanes outside the matrix supplying zeros. That splits a warp across branches and incurs additional compute. But N=1023N = 1023 does those checks too; divergence doesn’t explain why N=1025N = 1025 is so much slower.

Let’s count blocks instead. The GPU runs them in waves, filling each SM with as many blocks as will fit. We need ⌈N/128⌉2\lceil N/128 \rceil^2 blocks, one per 128×128 output tile. Only one block fits on each SM, so our 40 SMs can finish 40 blocks in a wave. If the last wave has fewer blocks, the busy SMs still have to finish theirs while the rest sit idle.

This is especially bad at small sizes:

Now compare the sizes around a tile boundary. How many waves does each need?

The A100’s 108 SMs show this too. NVIDIA’s plot rises as the tiles fill a wave, then drops when one more tile starts the next:

Throughput against N for a matrix multiply on an A100: it rises in a sawtooth and drops sharply at each multiple of 108 tiles.
Each drop is the first tile of a new wave. Panel (a) of Figure 8 in NVIDIA’s Matrix Multiplication Background User’s Guide.

This phenomenon is known as wave quantization, or the tail effect. cuBLAS selects different kernels at different sizes to deal with it. Our 128×128 tile wins at N=2048N = 2048, but using 64×64 at N=256N = 256 would put 16 SMs to work instead of 4. Fitting two blocks per SM would also double a wave’s capacity and reduce the tail cost, provided we could bring the register allocation down to 128 per thread.

Looking Back

We ended the course project at 4,780 GFLOP/s, with thread 0’s global loads down from 2 per multiply-add to 1 per 64, and shared-memory loads down to 1 per 4. The kernel still computes the same dot products we started with.

The roofline, register usage, and partly filled waves suggested three optimizations to test next:

We ran out of time to measure these changes on the T4.

In Part 2, I returned to these questions on an NVIDIA GB10 and compared the resulting kernels against cuBLAS.


  1. If each element of AA and BB were fetched just once, the kernel would read 2N22N^2 floats, or 8N28N^2 bytes, for 2N32N^3 flops. That gives an upper bound of N/4N/4 flops per byte, or 512 at N=2048N = 2048. Our kernels do not reach that bound. ↩︎

  2. The repository only has code for the naive and final versions. For the stages in between, this post describes the idea and quotes approximate numbers from the course report. ↩︎

  3. Each KK slice brings 128×32 + 32×128 = 8,192 floats into shared memory, and the block performs 128 × 128 × 32 = 524,288 multiply-adds with them: one global load per 64 multiply-adds, compared with one per 16 for 32×32 tiles. Intensity is measured per byte, not per element, because the ridge point is defined in bytes. The figure of 32 flops per byte assumes each value is read from global memory once per tile and ignores caches. ↩︎

#Engineering #Research