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.
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.
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.
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.
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];
}
| 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 |
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
// 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