Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 31 ยท Projects

Project: Fast Matrix Multiplication

Take CUDA matrix multiplication from a naive kernel to tiled and register-blocked versions, learn the GFLOPS arithmetic and see why cuBLAS wins.

Matrix multiplication is the benchmark of GPU programming. It is simple to state, it dominates deep learning and scientific computing, and it shows every optimization idea in one place: global memory traffic, shared memory, registers and the gap between your code and a library. In this project you take C = A x B through three versions of increasing sophistication, learn how to turn a runtime into a GFLOPS number, and finally see how a tuned library fits in.

You already met the first two versions in Shared Memory and Tiling. Here we go one step further (register blocking), measure each step with a consistent yardstick, and verify correctness the way a careful engineer does.

The CUDA C++ is read-only: no GPU is available on the site. The Python examples run for real, but they are models. They count loads, multiply small matrices with NumPy to prove the algorithms are correct, and apply a cost model with round example numbers (a made-up GPU with 20 TFLOPS and 900 GB/s, not any real card). Nothing here is a benchmark.

The arithmetic of matrix multiply

For square n x n matrices every output element is a dot product of length n. That is n multiplications and n additions, or n fused multiply-adds (FMAs). Across n^2 outputs the program does n^3 FMAs. By convention one FMA counts as 2 floating-point operations, so:

FLOPs = 2 * n^3

For n = 4096 that is about 137 billion operations. Once you measure a time t in seconds, the speed is

GFLOPS = FLOPs / t / 1e9

and you can compare it with the peak of the GPU (its datasheet FP32 rate) to see how efficient you are. A matrix multiply is one of the few kernels that can come close to peak, because it does O(n^3) work on O(n^2) data. Reuse is built into the problem. Every version below is an attempt to exploit that reuse better.

Version 1: naive

One thread per output element, reading a row of A and a column of B straight from global memory:

C++
__global__ void matmulNaive(const float* A, const float* B, float* C, int n) {
    int row = blockIdx.y * blockDim.y + threadIdx.y;
    int col = blockIdx.x * blockDim.x + threadIdx.x;
    if (row >= n || col >= n) return;

    float acc = 0.0f;
    for (int k = 0; k < n; ++k) {
        acc += A[row * n + k] * B[k * n + col];
    }
    C[row * n + col] = acc;
}

Threads of a warp have consecutive col, so the reads of B[k * n + col] are coalesced, and all lanes read the same A[row * n + k] (a broadcast). It works, and it is correct, but each FMA needs two loads: the ratio of math to memory traffic is terrible. This is memory bound.

Version 2: tiled with shared memory

Each block computes a T x T tile of C and loops over tiles of A and B in shared memory (see the full kernel in Shared Memory and Tiling). Global loads shrink by a factor of T. But look at the inner loop: every FMA still reads two values from shared memory, one from As and one from Bs. Shared memory is fast but not free, and now it is the bottleneck.

Version 3: register blocking

The fix is to let each thread compute several outputs, say an R x R patch, and keep its partial sums in registers. For each step k, a thread loads R values from the A tile and R values from the B tile into registers, then does R x R FMAs with them. That is 2R shared reads for R^2 FMAs: the shared traffic per FMA drops from 2 to 2/R.

flowchart LR
    G["Global memory"] -->|"tile loads"| S["Shared memory<br/>As and Bs"]
    S -->|"2R reads per k"| Rg["Registers<br/>a[R], b[R]"]
    Rg -->|"R x R FMAs"| Acc["acc[R][R]<br/>in registers"]
    Acc -->|"write once"| G

Each level of memory is read less often per FMA than the one before it.

Here is a complete version in which a block of 16 x 16 threads computes a 64 x 64 tile, so each thread owns a 4 x 4 patch:

C++
#define BM 64
#define BN 64
#define BK 16
#define TM 4
#define TN 4

__global__ void matmulBlocked(const float* A, const float* B, float* C, int n) {
    __shared__ float As[BM][BK];
    __shared__ float Bs[BK][BN];

    int tid     = threadIdx.y * blockDim.x + threadIdx.x;   // 0..255
    int rowBase = blockIdx.y * BM;
    int colBase = blockIdx.x * BN;
    float acc[TM][TN] = {};                                  // lives in registers

    for (int k0 = 0; k0 < n; k0 += BK) {
        // 256 threads cooperatively load 64x16 floats of A and 16x64 floats of B
        for (int i = tid; i < BM * BK; i += 256) {
            int r = i / BK, c = i % BK;
            int gr = rowBase + r, gc = k0 + c;
            As[r][c] = (gr < n && gc < n) ? A[gr * n + gc] : 0.0f;
        }
        for (int i = tid; i < BK * BN; i += 256) {
            int r = i / BN, c = i % BN;
            int gr = k0 + r, gc = colBase + c;
            Bs[r][c] = (gr < n && gc < n) ? B[gr * n + gc] : 0.0f;
        }
        __syncthreads();

        for (int k = 0; k < BK; ++k) {
            float a[TM], b[TN];
            for (int i = 0; i < TM; ++i) a[i] = As[threadIdx.y * TM + i][k];
            for (int j = 0; j < TN; ++j) b[j] = Bs[k][threadIdx.x * TN + j];
            for (int i = 0; i < TM; ++i)
                for (int j = 0; j < TN; ++j)
                    acc[i][j] += a[i] * b[j];
        }
        __syncthreads();
    }

    for (int i = 0; i < TM; ++i)
        for (int j = 0; j < TN; ++j) {
            int r = rowBase + threadIdx.y * TM + i;
            int c = colBase + threadIdx.x * TN + j;
            if (r < n && c < n) C[r * n + c] = acc[i][j];
        }
}
// dim3 block(16, 16);
// dim3 grid((n + BM - 1) / BM, (n + BN - 1) / BN);

A larger per-thread patch means more registers per thread, which lowers occupancy: the usual trade-off from Warps, SMs and the Hardware. Production kernels tune BM, BN, BK, TM and TN together, and add details such as padding against bank conflicts and double-buffered tiles.

Counting the traffic

The model below runs all three algorithms on a real 32 x 32 problem and counts what each level of memory must supply. tiled counts two shared reads per FMA; blocked counts the 2R reads per step for each thread.

Python Naive, tiled and register-blocked: results and traffic

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.

All four versions agree with NumPy. Going from naive to the 8 x 8 tiled version cuts global loads from 65,536 to 8,192 (8 times, equal to the tile width), but costs two shared reads per FMA. Register blocking with R = 2 halves the shared traffic to 1.00 per FMA and also halves the global loads again, since the block tile is bigger. With R = 4 the numbers fall to 0.50 and 2,048. That is the whole idea in numbers: each memory level is asked for less per unit of math.

From traffic to GFLOPS: the roofline estimate

A kernel cannot run faster than either its math allows or its memory delivers. The arithmetic intensity is the number of FLOPs per byte moved from DRAM. With a peak of P GFLOPS and a bandwidth of BW GB/s, the best possible speed is min(P, AI x BW) (the roofline model; see The Optimization Workflow). The next example applies it to an n = 4096 multiply on the invented GPU.

Python Roofline ceilings for the three versions

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.

Read the table as ceilings, never as predictions. The naive kernel cannot beat 225 GFLOPS here, about 1% of the peak, however well you write it. Tiling lifts the ceiling to 3,600 GFLOPS, and a 128 x 128 block tile reaches the point where the math units, not the memory, limit you (an arithmetic intensity of 32 FLOP/byte is above the ridge point of 22). Real kernels fall below their ceilings because of instruction overhead, bank conflicts, latency and tail effects, which is exactly the gap that a library closes.

Measuring on a real GPU

On hardware you time the kernel with events (see Streams and Events), do a warm-up launch first, and average several runs:

C++
cudaEvent_t start, stop;
cudaEventCreate(&start);  cudaEventCreate(&stop);

matmulBlocked<<<grid, block>>>(dA, dB, dC, n);       // warm-up, not timed
cudaEventRecord(start);
for (int i = 0; i < 20; ++i) matmulBlocked<<<grid, block>>>(dA, dB, dC, n);
cudaEventRecord(stop);
cudaEventSynchronize(stop);

float ms = 0;  cudaEventElapsedTime(&ms, start, stop);
double seconds = (ms / 1000.0) / 20.0;
double gflops  = 2.0 * n * (double)n * n / seconds / 1e9;
printf("%.1f GFLOPS\n", gflops);

Comparing with cuBLAS

Your hand-written kernel is for learning. In real code you call cuBLAS, NVIDIA's tuned linear-algebra library, whose SGEMM routine uses architecture-specific tile shapes, double buffering, tensor cores where allowed and many other tricks. One catch: cuBLAS stores matrices in column-major order. A row-major C = A x B equals a column-major C^T = B^T x A^T, so you pass the operands swapped, without any copying:

C++
#include <cublas_v2.h>

cublasHandle_t handle;
cublasCreate(&handle);
const float alpha = 1.0f, beta = 0.0f;
// row-major C = A * B  ==  column-major C^T = B^T * A^T
cublasSgemm(handle, CUBLAS_OP_N, CUBLAS_OP_N,
            n, n, n, &alpha, dB, n, dA, n, &beta, dC, n);
cublasDestroy(handle);
// link with: nvcc main.cu -lcublas

Compare it against your kernel using the same GFLOPS formula, and also check the answers. Floating-point addition is not associative, so a different order of summation gives slightly different float results; never test for bitwise equality. The last example checks the result of a float32 tiled sum against a float64 reference and with different tile widths.

Python Checking a result with tolerances, not equality

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.

Every tile width passes with a relative error far below 1e-5, and the tile widths agree with each other within tolerance. Whether they agree bit for bit depends on the order of additions, which is why tests for GPU code should use allclose-style checks with a tolerance that fits the data, as in the error handling lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many floating-point operations does an n x n matrix multiply perform, counting an FMA as two?

    There are n^2 outputs, each needing n FMAs, so n^3 FMAs, which is 2 * n^3 FLOPs.
  2. 2. What is the main benefit of register blocking over plain shared-memory tiling?

    A thread computing an R x R patch loads R + R values for R x R FMAs, which cuts shared memory traffic per FMA by a factor of R.
  3. 3. A kernel has an arithmetic intensity of 4 FLOP/byte on a GPU with 900 GB/s bandwidth and 20,000 GFLOPS peak. What is its roofline ceiling?

    min(20,000, 4 x 900) = 3,600 GFLOPS: this kernel is memory bound.
  4. 4. How do you call cuBLAS SGEMM for row-major matrices without transposing them?

    The swap treats the row-major buffers as transposed column-major matrices, producing the correct row-major result in dC.
  5. 5. Why should GPU results be compared with a tolerance?

    Parallel and tiled versions add numbers in a different order than a reference. Both are valid, but they differ by rounding.

Summary

  • Matrix multiply does 2 * n^3 FLOPs; divide by the measured time to get GFLOPS and compare with the GPU's peak.
  • Naive kernels are memory bound; shared-memory tiling cuts global loads by the tile width; register blocking cuts shared-memory reads per FMA by the patch size.
  • The roofline min(peak, intensity x bandwidth) gives a ceiling for each version; real kernels fall below it.
  • Use cuBLAS in production (swap operands for row-major data) and keep your own kernel as a learning tool and a correctness check.
  • Validate with tolerances, not equality, and always warm up and average when you time.

Continue with Project: N-Body Simulation.