Algorithms

Tiled Matrix Multiplication (SGEMM)

Tiled Matrix Multiplication (SGEMM)

Matrix multiplication C = A × B (SGEMM — Single-precision General Matrix Multiply) is the most important compute-bound kernel in GPU programming. It is compute-bound: each element of C requires N multiply-add operations but is written only once.

The Roofline Problem

Naively, computing C[i][j] requires reading one full row of A and one full column of B — N floats each, for N² elements of C. Total reads: 2N³ floats. Without shared memory every thread independently fetches from global DRAM.

Arithmetic intensity: ops / bytes = N multiply-adds / (N reads + N reads) = N/2

For N=1024, each element of C requires 1024 multiply-adds and 2048 bytes loaded — we need to keep the data close to the compute units.

Tiled Algorithm

Decompose A and B into TILE×TILE sub-matrices. Each thread block computes one TILE×TILE tile of C, loading tiles of A and B into shared memory and reusing them across the K dimension:

For each k-tile (k = 0 to K/TILE): 1. Load A_tile[TILE][TILE] from global memory → shared memory (coalesced) 2. Load B_tile[TILE][TILE] from global memory → shared memory (coalesced) 3. __syncthreads() 4. Each thread computes its partial dot product using shared memory 5. __syncthreads()

Shared memory reuse: each element of the tile is reused TILE times (by TILE different threads). This multiplies the effective bandwidth by TILE.

For TILE=16: 16× bandwidth reduction. For TILE=32: 32× reduction.

Register Tiling for More Compute

The next level: each thread accumulates a small sub-tile (e.g. 4×4) of C in registers, loading 4 values of A and 4 values of B per step. This is how cuBLAS achieves >90% of theoretical FLOPs.

c
float c[4][4] = {};           // 16 registers for C sub-tile
float a[4], b[4];

for (int k = 0; k < K; k++) {
    // Load 4 values from A column and B row into registers
    for (int i = 0; i < 4; i++) a[i] = s_A[k][ty*4 + i];
    for (int j = 0; j < 4; j++) b[j] = s_B[k][tx*4 + j];
    // Outer product: 4×4 = 16 FMAs
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            c[i][j] += a[i] * b[j];
}

Performance Roofline

| Approach | Effective bandwidth | FLOPs | |---|---|---| | Naive global memory | Peak DRAM BW | Low (memory-bound) | | Shared-memory tiling (TILE=16) | 16× less DRAM | Moderate | | Register tiling (4×4 sub-tile) | 64× less DRAM | High (compute-bound) | | Tensor cores (WMMA) | Minimal loads | Near-peak TFLOPS |

When to Use cuBLAS

For production code, always use cuBLAS cublasSgemm — it implements register tiling, tensor core utilization, and architecture-specific tuning. Only write your own GEMM as a learning exercise or when you need non-standard operations.

// CODE EXAMPLE

example.cu
// Shared-memory tiled SGEMM: C = A * B (N×N matrices)
#define TILE 16

__global__ void tiledSgemm(
    const float *A, const float *B, float *C, int N)
{
    __shared__ float As[TILE][TILE];
    __shared__ float Bs[TILE][TILE];

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

    float sum = 0.f;

    // Sweep tiles along the K dimension
    for (int t = 0; t < (N + TILE - 1) / TILE; t++) {
        // Coalesced loads into shared memory
        int aCol = t * TILE + threadIdx.x;
        int bRow = t * TILE + threadIdx.y;

        As[threadIdx.y][threadIdx.x] = (row < N && aCol < N) ? A[row * N + aCol] : 0.f;
        Bs[threadIdx.y][threadIdx.x] = (bRow < N && col < N) ? B[bRow * N + col] : 0.f;
        __syncthreads();

        // Dot product over this tile — TILE FMAs per thread
        for (int k = 0; k < TILE; k++)
            sum += As[threadIdx.y][k] * Bs[k][threadIdx.x];
        __syncthreads();
    }

    if (row < N && col < N) C[row * N + col] = sum;
}

// TRY IT

GPU execution
main.cu
loading editor…