Linear operators: GEMM, GEMV and flat GEMM
Most of the bytes an LLM reads in decode belong to linear layers, and each one is a matrix product whose shape changes with the phase: a big GEMM in prefill, a thin GEMV or flat GEMM in decode. This session shows why one kernel cannot serve both, how tiling, padding, split-K and double buffering behave on thin shapes, how W4A16 kernels dequantize inside the kernel, and how MoE layers run as one grouped GEMM.
What you will learn
- Why prefill is a compute-bound GEMM and decode a memory-bound GEMV or flat GEMM, from the intensity formula I ≈ M
- How a tiled GEMM kernel works, and why tiling cannot create weight reuse at M = 1
- Padding waste, too few thread blocks, wave quantization, and how split-K and Stream-K fix them, with exact counts for Llama 3.1 8B layers on H100 and A100
- GEMV and flat-GEMM kernels, double buffering, and shape-based kernel dispatch (the heuristic dataflow of FlashDecoding++)
- W4A16 kernels: dequantize in registers, the 0x6400 trick, the 3.76× bound and why the gain fades with batch size
- MoE grouped GEMM: sort tokens by expert, one launch for all experts, and how many experts a decode batch touches
Why this matters
Generate one token with Llama 3.1 8B at batch size 1, and almost all of the 15 GB of weights that the GPU reads in that step belong to linear layers: the Q, K, V and output projections, the MLP, and the LM head. Each of them is a matrix product. How fast that product runs decides how fast the model talks.
A linear layer computes \(Y = X W^\top\). The weight matrix \(W\) is fixed and large (for example \(28{,}672 \times 4{,}096\)). The input \(X\) has one row per token that passes through the layer at the same time. Call that number \(M\). Everything in this session follows from one fact: \(M\) changes by a factor of thousands between the two phases of generation.
- Prefill (reading the prompt) sends all prompt tokens through at once. \(M\) is the batch size times the prompt length: thousands. The product is a full matrix–matrix multiplication, a GEMM (general matrix–matrix multiply).
- Decode (making one new token per step) sends one token per sequence. \(M\) is the batch size: 1, 8, maybe 64. At \(M = 1\) the product is a matrix–vector multiplication, a GEMV. For small \(M > 1\) it is a flat GEMM: a GEMM where one side is very thin.
Standard GEMM libraries (cuBLAS, CUTLASS) are tuned for big, square-ish shapes. On thin decode shapes they waste work on padding, leave most of the GPU idle, and miss the memory speed that decode needs. The efficient-inference survey of Zhou et al. (section 6.1.1, “linear operator optimization”) notes that many frameworks just call the cuBLAS GEMM API for decode, which is inefficient, and lists the fixes: dedicated GEMV kernels (as in TensorRT-LLM), the flat GEMM of FlashDecoding++, and special kernels for MoE layers (MegaBlocks, the fused MoE kernel of vLLM). [Certain] This session builds each of them from the roofline up.
In session 125 you saw the same problem for attention: decode has one query row, so there is not enough parallel work. Here we solve it for the other half of the model, which, at short and medium context, is the larger half. In session 127 we will then fuse these kernels with their neighbours.
The shape of a linear layer
Write the layer as \(Y = X W^\top\) with \(X \in \R^{M \times K}\) (the activations), \(W \in \R^{N \times K}\) (the weights, one row per output feature), and \(Y \in \R^{M \times N}\). Each output number is a dot product of length \(K\): \(K\) multiplications and \(K\) additions. So the work is
The kernel must also move data. It reads \(X\) and \(W\) from the GPU’s main memory (HBM, high-bandwidth memory) and writes \(Y\) back. With \(b_a\) bytes per activation and \(b_w\) bytes per weight, the minimum traffic and the arithmetic intensity (FLOPs per byte moved) are
- Read the symbols
- \(M\)
- tokens in this call: batch × prompt length in prefill, batch size in decode
- \(K, N\)
- input and output width of the layer, fixed by the model
- \(b_a, b_w\)
- bytes per activation and per weight: 2 for BF16, 0.5 for 4-bit weights (plus scales)
- \(Q\)
- bytes that must cross between HBM and the chip at least once
- \(I\)
- arithmetic intensity: how much math you get per byte you move
Why \(I \approx M\)? When \(M\) is small, the weight term \(NK\) dominates \(Q\). Every weight is loaded once and used \(M\) times, once per token, so each 2-byte weight gives \(2M\) FLOPs. The batch size is the reuse factor of the weights. [Certain]
The model we use is Llama 3.1 8B (hidden size 4,096, 32 query heads and 8 key–value heads of size 128, MLP width 14,336, vocabulary 128,256, 32 layers; from its config.json). Its linear layers per block, with the projections that are usually fused written as one matrix:
| Layer | \(N \times K\) | Weights (BF16) |
|---|---|---|
| QKV projection (fused) | \(6{,}144 \times 4{,}096\) (4,096 + 2 × 1,024 outputs) | 50.3 MB |
| Output projection | \(4{,}096 \times 4{,}096\) | 33.6 MB |
| MLP gate + up (fused) | \(28{,}672 \times 4{,}096\) | 234.9 MB |
| MLP down | \(4{,}096 \times 14{,}336\) | 117.4 MB |
| LM head (once, not per layer) | \(128{,}256 \times 4{,}096\) | 1,050.7 MB |
Per block that is 218.1 million weights; over 32 blocks plus the LM head, 7.50 billion weights, or 15.0 GB in BF16. [Certain] (The embedding table is a lookup, not a product, so it is not in this list.)
The roofline for one layer: from GEMV to GEMM
A GPU has a peak math speed \(P\) (FLOP/s) and a peak memory speed \(B\) (bytes/s). A kernel cannot be faster than either limit, so the best possible time is
\(I^\ast\) is the ridge point from session 82. For dense BF16 it is \(989 / 3.35 = 295\) FLOP/byte on an H100 SXM and \(312 / 2.039 = 153\) on an A100 80 GB. [Certain] Because \(I \approx M\), the rule of thumb is simple: a linear layer is memory-bound until \(M\) reaches a few hundred tokens. Prefill (thousands of tokens) is far above; decode at batch 1 is 295 times below.
\(N = 28{,}672\), \(K = 4{,}096\), BF16. At \(M = 1\): \(F = 0.235\) GFLOP and \(Q \approx 234.9\) MB, so \(I = 1.00\). Compute time \(0.24\) µs, memory time \(70.1\) µs. The layer takes 70.1 µs and reaches 3.35 TFLOP/s: 0.34% of the peak.
At \(M = 64\): memory time 71.4 µs, almost the same, but 64 times more useful work: 211 TFLOP/s. Extra tokens are nearly free while the layer is memory-bound.
At \(M = 2{,}048\) (a prefill): compute time 486 µs, memory time 110 µs. Now it is compute-bound and runs at the full 989 TFLOP/s. Solving \(F/P = Q/B\) exactly for this layer gives \(M \approx 322\), a bit above 295 because the activation terms of \(Q\) also grow with \(M\).
The whole model at batch 1: reading 15.0 GB at 3.35 TB/s takes at least 4.48 ms per token, so no kernel can go above about 223 tokens per second on one H100 at batch 1. [Certain]
How to read Figure 1
Left of the bend, every curve rises in a straight line on this log axis: the layer is memory-bound, so time is fixed by the weight bytes and work grows with \(M\) for free. Right of the bend, the curve is flat at the peak: compute-bound. Switch to W4A16: the curve is 3.76 times higher at small \(M\) (fewer bytes), but it reaches the peak at a smaller \(M\) (about 85 on the H100 for gate + up). That is why weight-only quantization helps decode and not prefill (session 104). This is an ideal model: real kernels lose some speed, more so on thin shapes, as the next sections explain.
How a GEMM kernel works: tiles
To get near the roofline, a GEMM kernel must load each number from HBM as few times as possible. It cuts the output \(Y\) into tiles of \(B_M \times B_N\) numbers. One thread block (a group of threads that runs on one streaming multiprocessor, SM, and shares its fast on-chip memory, see session 85) computes one tile. It walks along \(K\) in steps of \(B_K\): load a \(B_M \times B_K\) piece of \(X\) and a \(B_N \times B_K\) piece of \(W\) into shared memory, multiply them on the tensor cores, add to an accumulator in registers. At the end it writes the tile once.
- input: tile position \((i, j)\); tile sizes \(B_M, B_N, B_K\)
- \(\text{acc} \leftarrow 0\) // \(B_M \times B_N\), FP32, in registers
- for \(k = 0, B_K, 2B_K, \dots, K - B_K\) do
- load \(X[iB_M : (i{+}1)B_M,\ k : k{+}B_K]\) into shared memory // rows past M are padded with zeros
- load \(W[jB_N : (j{+}1)B_N,\ k : k{+}B_K]\) into shared memory
- \(\text{acc} \leftarrow \text{acc} + X_{\text{tile}} W_{\text{tile}}^\top\) // tensor-core instructions
- end for
- write the first \(\min(B_M, M - iB_M)\) rows of acc to \(Y\) // epilogue: bias, activation, cast to BF16 can be fused here
Inside the loop, each loaded number of \(X\) is used \(B_N\) times and each number of \(W\) is used \(B_M\) times. With 2-byte numbers, the intensity of the tile loop is
A \(128 \times 128\) tile gives 64 FLOP/byte from HBM (and the L2 cache adds more reuse across tiles). That is how big GEMMs reach the compute roof. But now put \(M = 1\) in: only 1 row of the tile is real, the reuse of each weight is 1, and \(I_{\text{tile}}\) of useful work is \(1 \cdot 128 / 129 = 0.99\). No tiling can create reuse that the problem does not have. For thin shapes, the goal changes: stop optimizing for reuse, start optimizing for streaming the weights at full memory speed.
Thin shapes 1: padding waste
Tensor cores work on small fixed shapes. For FP16 and BF16 the common warp-level instruction multiplies a \(16 \times 16\) piece by a \(16 \times 8\) piece (the PTX shape m16n8k16). [Certain] So \(M\) is padded at least to a multiple of 8 or 16, and library kernels use much larger \(B_M\). FlashDecoding++ reports that cuBLAS and CUTLASS tile \(M\) to 64, so a decode batch with \(M \lt 8\) is padded with zeros to 64. [Certain] The useful fraction of the tensor-core work is
At \(M = 1\): \(u = 1.6\%\) with \(B_M = 64\), \(6.25\%\) with \(B_M = 16\), \(12.5\%\) with \(B_M = 8\). At \(M = 33\) and \(B_M = 64\): \(51.6\%\), because one extra token beyond 32 costs a whole half-empty tile row. FlashDecoding++ pads \(M\) only to 8 instead of 64. [Certain] One common way to reach 8 is to swap the two operands, computing \(Y^\top = W X^\top\), so that the large \(N\) fills the 16-row side of the instruction and the small \(M\) the 8-column side. [Likely]
Does the wasted math matter if the layer is memory-bound anyway? Check it with numbers. On an H100 the padded work at \(M = 1\), \(B_M = 64\) for the output projection takes \(2 \cdot 64 \cdot 4096^2 / 989\,\text{T} = 2.17\) µs, while reading its weights takes 10.0 µs. So in BF16 the padded math is hidden behind the memory time (ratio 0.22). The waste becomes visible in two cases. First, on GPUs with a lower ridge: on an A100 the ratio is 0.42 with \(B_M = 64\) and 0.84 with \(B_M = 128\). Second, and more important, with quantized weights: 4-bit weights cut the memory time by 3.76 times but not the padded math. See the worked example in the W4A16 section.
Thin shapes 2: too few tiles, waves, and split-K
The second problem is parallelism. An H100 SXM has 132 SMs and an A100 has 108. [Certain] To pull weights from HBM at full speed, the GPU needs many memory requests in flight from most of its SMs at once. [Likely] But a thin GEMM has few output tiles. For the output projection at \(M = 1\) with \(B_N = 128\), there are only \(4096 / 128 = 32\) tiles: one thread block each, so 100 of the 132 SMs have nothing to do.
The general count, with a split-K factor \(S\) (explained below), is
- Read the symbols
- \(n_{\text{blk}}\)
- thread blocks launched (one per output tile, times \(S\))
- \(n_{\text{SM}}\)
- number of SMs on the GPU (assuming one block per SM at a time, as in big GEMM kernels)
- \(w\)
- waves: rounds of blocks the GPU runs one after another
- \(\eta\)
- wave efficiency: the share of SM time slots that do work
Too few blocks give \(\eta = 32/132 = 24\%\). Slightly too many also hurt: 133 blocks need 2 waves, and the second wave runs 1 block while 131 SMs wait, so \(\eta = 50.4\%\). This is called wave quantization. [Certain]
Split-K
When \(M\) and \(N\) give too few tiles, split the inner dimension \(K\) into \(S\) slices. Each slice is a separate thread block that computes a partial result for the same output tile; a final step adds the partials:
For the output projection at \(M = 1\): \(S = 4\) gives \(32 \times 4 = 128\) blocks, \(\eta = 97\%\). The extra traffic is \(2 \cdot 4 \cdot 4096 \cdot 4 = 131\) KB, which is \(0.39\%\) of the 33.6 MB of weights. [Certain] Split-K is cheap exactly when \(M\) is small, which is when it is needed. For a big prefill GEMM it would be wasteful: there are already thousands of tiles, and the partials would be huge. The partial sums can be added by a second small kernel, or with atomic adds into the output (which makes the summation order, and so the last bits of the result, non-deterministic). [Likely] Stream-K (Osama et al.) goes one step further: it gives every SM an equal share of all inner-loop iterations across all tiles, so the result does not depend on how the tile count divides by the SM count. [Certain]
How to read Figure 2
Start at \(M = 1\), \(B_M = 64\), \(S = 1\) on the output projection: 32 tiles, each with one real row out of 64, and only 32 of 132 SMs busy. Set \(S = 4\): 128 blocks fill 97% of the GPU at a cost of 0.39% extra bytes. Now move \(M\) up with \(B_M = 64\): the tile count does not change and the useful fraction grows as \(M/64\), until at \(M = 65\) a second tile row appears and the fraction drops to 50.8%. Try the gate + up layer: with 224 tiles it needs no split-K, but 224 on 132 SMs gives 2 waves at 85% efficiency.
GEMV and flat GEMM kernels
Since the decode shapes are memory-bound, a good decode kernel is judged by one number: what fraction of the HBM bandwidth it reaches while streaming \(W\). Tensor cores are not needed at \(M = 1\); the ordinary CUDA cores have more than enough speed for 1 FLOP per byte.
GEMV (\(M = 1\))
A typical GEMV kernel gives each warp (32 threads that run in lockstep) one or a few output rows. The 32 threads read one row of \(W\) together in wide, contiguous (coalesced) loads, each thread multiplies its part by the matching part of \(x\), and a warp-shuffle reduction adds the 32 partial sums. \(x\) is small (8 KB for \(K = 4096\)) and stays in shared memory or the cache. With \(N = 4096\) rows there are 4,096 warps: plenty of parallel work for the whole GPU, without any split-K. [Certain]
- input: \(W \in \R^{N \times K}\) row-major in HBM, \(x \in \R^{K}\)
- copy \(x\) into shared memory once per block
- for each warp, in parallel: \(n \leftarrow\) its row
- lane \(\ell \in \{0, \dots, 31\}\): \(\text{part} \leftarrow 0\)
- for \(j = 8\ell, 8\ell + 256, 8\ell + 512, \dots\) do // 16-byte loads: 8 BF16 weights per lane
- \(\text{part} \leftarrow \text{part} + \sum_{u=0}^{7} W[n, j{+}u]\, x[j{+}u]\) // FP32 accumulate
- end for
- \(\text{part} \leftarrow\) warp-shuffle sum over the 32 lanes // 5 shuffle steps
- lane 0 writes \(y[n] \leftarrow \text{part}\)
For small \(M \gt 1\), the same kernel can keep \(M\) accumulators per lane and reuse each loaded weight \(M\) times. This works up to a few tokens; then the CUDA cores become the limit and tensor cores pay off again. [Likely]
Flat GEMM (small M on tensor cores)
FlashDecoding++ calls the decode shape a flat GEMM and lists two problems with library kernels: low parallelism and memory-access bottlenecks. Its answers are fine-grained tiling (pad \(M\) only to 8; choose \(B_N\) so that \(N / B_N\) gives enough blocks for the SMs), and double buffering when \(N\) is large. [Certain] The paper also notes that \(K\) tiles run one after another inside a block, to avoid reductions across blocks. [Certain]
Double buffering means two shared-memory buffers: while the tensor cores work on tile \(k\) in one buffer, the memory system is already loading tile \(k + 1\) into the other. With \(n\) steps along \(K\), load time \(L\) and compute time \(C\) per step:
With \(n = 8\), \(L = 2\), \(C = 1\): 24 time units without overlap, 17 with it. In decode \(L \gg C\), so double buffering cannot beat \(nL\), the time to stream the weights; what it does is hide the compute and the latency of each load so the memory system never sits idle. Modern kernels use deeper pipelines (3 to 5 stages) for the same reason. [Likely]
How to read Figure 3
The memory lane is what matters in decode. In single-buffer mode it has gaps (the compute time). In double-buffer mode it is busy without gaps whenever \(L \ge C\), and the total time is close to \(nL\). Set \(C \gt L\) to see the compute-bound case (prefill): then the compute lane has no gaps and the loads are hidden instead.
Choosing the kernel by shape
No single kernel is best for every \(M\). FlashDecoding++ calls its answer heuristic dataflow: for every \([N, K]\) shape of the model, it profiles three implementations (a GEMV on CUDA cores, its flat GEMM, and a CUTLASS GEMM) while increasing \(M\), and records two switch points \(M_1\) and \(M_2\). At run time it picks by \(M\). [Certain] This works because the shapes of an LLM are fixed; only \(M\) changes. The paper reports that one static dataflow can lose up to 50.25% of performance on GEMMs of different shapes. [Certain]
- offline, for each layer shape \((N, K)\) of the model do
- time GEMV, flat GEMM and library GEMM for \(M = 1, 2, 4, \dots\)
- \(M_1 \leftarrow\) first \(M\) where flat GEMM beats GEMV; \(M_2 \leftarrow\) first \(M\) where GEMM beats flat GEMM
- also store the best \(B_N\) and split-K \(S\) for each range // formula (126.6)
- at run time: given \(M\) (tokens in this step)
- if \(M \lt M_1\): GEMV on CUDA cores
- else if \(M \lt M_2\): flat GEMM on tensor cores, \(M\) padded to 8, double buffering
- else: big-tile GEMM (prefill)
cuBLAS has its own heuristics that pick a kernel (and sometimes split-K) per shape, and serving engines often add tuned configurations per GPU and shape. [Likely] With continuous batching (session 135), one step can mix prefill chunks and decode tokens, so \(M\) changes every step and the dispatch runs every step too.
Quantized GEMM: dequantize inside the kernel (W4A16)
In W4A16 the weights are stored as 4-bit integers with one FP16 scale and zero point per group of \(g\) weights, and the math is done in FP16 (session 104, session 107). The key design rule: never write the dequantized weights back to HBM. A kernel that first expands \(W\) to FP16 in memory and then calls a normal GEMM reads and writes more bytes than plain FP16 would. Instead, the kernel loads the packed 4-bit tile, turns it into FP16 in registers, and feeds the tensor cores or CUDA cores directly. The bytes per weight become
The bound holds while the layer is memory-bound. W8A16 gives at most \(16 / 8.25 = 1.94\). [Certain] Because the weight bytes shrink 3.76 times but the FLOPs do not, the layer reaches the compute roof 3.76 times earlier: for gate + up on the H100, at \(M \approx 85\) instead of 322 (Figure 1). The roofline speed-up is 3.76× at \(M = 1\), 3.59× at \(M = 64\), and 2.39× at \(M = 128\). [Certain]
Making dequantization cheap
Dequantization costs instructions per weight: unpack, convert, subtract the zero, multiply by the scale. In a memory-bound kernel this is free only while it is hidden behind the loads. A classic trick avoids the slow integer-to-float conversion. The FP16 number with bit pattern 0x6400 is exactly 1024.0, and the spacing of FP16 numbers between 1024 and 2048 is exactly 1. So writing a 4-bit code \(q\) into the low mantissa bits gives the FP16 number \(1024 + q\), and one subtraction gives \(q\):
(Checked for all 16 codes in the code below.) Kernels of this kind do the bit operations on several packed codes at once with a single logic instruction. [Likely] Marlin (Frantar et al.) combines such tricks with asynchronous loads and careful pipelining, and reports close to the ideal 4× speed-up for 4-bit weights up to batch sizes of 16 to 32, with a slow decline at 64 to 128, and up to 2.8× end to end inside vLLM. [Certain] LUT-GEMM takes another route: it replaces dequantization by table lookups. [Certain]
Take a layer at \(M = 1\) and a tile with \(B_M = 64\). The padded tensor-core time divided by the weight-reading time is \(64 B / P\) in BF16. On an H100: \(64 \times 3.35 / 989 = 0.22\): hidden.
With 4-bit weights the memory time is 3.76 times shorter, so the same ratio becomes \(0.22 \times 3.76 = 0.82\) on the H100 and \(0.42 \times 3.76 = 1.58\) on the A100. On the A100 the padded math now takes longer than reading the weights: the kernel is compute-bound on zeros. With \(B_M = 128\) the H100 ratio is 1.63 as well. [Certain] That is why quantized decode kernels use \(M\)-tiles of 16 or less, or the operand swap, and why W4A16 speed-ups fall at large batch even before the true compute roof.
MoE layers: grouped GEMM
In a mixture-of-experts (MoE) layer (session 95), a router sends each token to \(k\) of \(E\) expert MLPs. So the MLP is not one GEMM but \(E\) small GEMMs, one per expert, each with a different and unpredictable number of tokens \(M_e\) (with \(\sum_e M_e = kT\) for \(T\) tokens). There are three ways to run them:
- Loop over experts: one GEMM launch per expert. Simple, but up to \(E\) kernel launches per layer, each too small to fill the GPU. For DeepSeek-V3 that would be up to 256 launches per MoE layer.
- Pad to a capacity: give every expert the same \(M_e = C\) and run one batched GEMM. Tokens beyond \(C\) are dropped, and slots below \(C\) are zeros. MegaBlocks describes this as the choice between dropping tokens and wasting compute and memory on padding. [Certain]
- Grouped GEMM: one kernel launch that receives a list of problems \((M_e, N, K, \text{pointers})\). A tile scheduler walks over the tiles of all problems as if they were one big grid. Only the last tile of each expert is partly padded, nothing is dropped, and empty experts cost nothing. MegaBlocks reaches the same goal with block-sparse kernels and never drops tokens; the vLLM repository has fused MoE kernels written in Triton. [Certain]
- input: tokens \(X \in \R^{T \times d}\), router top-\(k\) indices, expert weights \(W_1, \dots, W_E\)
- flatten the \(kT\) (token, expert) pairs; sort them by expert // a counting sort: one histogram and a prefix sum
- \(M_e \leftarrow\) count per expert; offsets \(o_e \leftarrow \sum_{e' \lt e} M_{e'}\)
- gather the rows of \(X\) in sorted order // often fused into the GEMM’s loads
- build the tile list: for each expert \(e\) with \(M_e \gt 0\), tiles \(\lceil M_e / B_M \rceil \times \lceil N / B_N \rceil\)
- launch ONE kernel over all tiles; tile \(\tau\) of expert \(e\) computes rows \(o_e + \dots\) with \(W_e\)
- scatter results back to token order, multiply by router weights, sum the \(k\) outputs per token
In decode, there is a second effect. Each expert sees only a few tokens, so each expert GEMM is a flat GEMM and must read all of that expert’s weights. If routing were uniform and independent, the expected number of distinct experts touched by \(T\) tokens is
- Read the symbols
- \(E, k\)
- routed experts and experts per token: 8 and 2 for Mixtral 8x7B; 256 and 8 for DeepSeek-V3 (from their config.json files)
- \(T\)
- tokens in this step (the decode batch size)
- \(1 - k/E\)
- chance that one token misses a given expert
For Mixtral: 2 experts at \(T = 1\), 5.47 at \(T = 4\), 7.20 at \(T = 8\): by batch 8 almost all expert weights are read every step. For DeepSeek-V3: 8 at \(T = 1\), 57.4 at \(T = 8\), 163.3 at \(T = 32\), 251.6 at \(T = 128\). At \(T = 32\) each expert gets only 1.0 token on average. [Certain, for the uniform model; real routers are not uniform.] So an MoE decode step reads a large and growing part of all expert weights while each expert does GEMV-sized work. This is why MoE decode needs large batches (often with expert parallelism over many GPUs) to become efficient. [Likely]
Mixtral, \(T = 256\) tokens, \(k = 2\): 512 rows go to 8 experts. Suppose the loads are 90, 50, 70, 60, 40, 80, 64, 58.
Pad to capacity (the largest load, 90): \(8 \times 90 = 720\) rows, 71.1% useful. Grouped GEMM with \(B_M = 64\): \(2+1+2+1+1+2+1+1 = 11\) tiles = 704 rows, 72.7% useful. With \(B_M = 16\): 35 tiles = 560 rows, 91.4% useful. With \(B_M = 128\): 8 tiles = 1,024 rows, 50.0% useful. [Certain] So the grouped GEMM still has tile padding, and its tile size should shrink when the per-expert loads are small.
How to read Figure 4
Small \(T\) (decode): few tokens per expert, so tile padding is large, but that hardly matters because the step is memory-bound; the number that matters is the weight bytes read, which grows with the touched experts. Large \(T\) (prefill): almost all experts are touched, and the grouped GEMM keeps more than 90% of the rows useful with \(B_M = 16\), while padding to the largest load wastes more as the loads become uneven. Change the seed to see another routing.
In code
The code below is deterministic and runs on a CPU. It checks the roofline numbers, the tiling counts, that split-K gives the same result, that the 0x6400 dequantization trick is exact, and that a sort-then-group MoE layer matches a per-token reference.
import math, torch torch.manual_seed(0) # 1) Llama 3.1 8B linear layers: FLOPs, bytes and intensity for M tokens (BF16 = 2 bytes) LAYERS = {"qkv": (6144, 4096), "o": (4096, 4096), "gate_up": (28672, 4096), "down": (4096, 14336)} P, B = 989e12, 3.35e12 # H100 SXM: dense BF16 FLOP/s, HBM bytes/s def roofline(M, N, K, wbits=16): F = 2 * M * N * K # formula (126.1) Q = 2 * M * K + wbits / 8 * N * K + 2 * M * N # formula (126.2) t = max(F / P, Q / B) # formula (126.3) return F / Q, t * 1e6, "compute" if F / P > Q / B else "memory" for M in (1, 16, 512, 4096): I, us, bound = roofline(M, *LAYERS["gate_up"]) print(f"gate_up M={M:5d} I={I:7.1f} FLOP/B t={us:7.1f} us {bound}-bound") # 2) padding and waves for one tiling choice, formulas (126.5) and (126.6) def tiling(M, N, BM, BN, S=1, sms=132): blocks = math.ceil(M / BM) * math.ceil(N / BN) * S waves = math.ceil(blocks / sms) return M / (BM * math.ceil(M / BM)), blocks, waves, blocks / (waves * sms) print("M=1, BM=64, BN=128, S=1:", tiling(1, 4096, 64, 128)) print("M=1, BM=64, BN=128, S=4:", tiling(1, 4096, 64, 128, S=4)) # 3) split-K, formula (126.7): S partial products over slices of K, then one sum X = torch.randn(4, 4096); W = torch.randn(4096, 4096) S = 4; ks = 4096 // S partials = torch.stack([X[:, s*ks:(s+1)*ks] @ W[:, s*ks:(s+1)*ks].T for s in range(S)]) # FP32 partials ref = X @ W.T print("split-K relative error:", ((partials.sum(0) - ref).norm() / ref.norm()).item()) # 4) W4A16 with groups of g = 128 along K, formula (126.8); dequantize with the 0x6400 trick N, K, g = 256, 1024, 128 Wf = torch.randn(N, K) Wg = Wf.view(N, K // g, g) lo, hi = Wg.amin(-1, keepdim=True), Wg.amax(-1, keepdim=True) s = (hi - lo) / 15; z = torch.round(-lo / s) q = torch.clamp(torch.round(Wg / s) + z, 0, 15).to(torch.int16) # 4-bit codes 0..15 packed = (q[..., 0::2] | (q[..., 1::2] << 4)).to(torch.uint8) # two codes per byte # inside the kernel: unpack, OR into the mantissa of 1024.0 (0x6400), subtract 1024 lo4 = (packed & 0xF).to(torch.int16); hi4 = (packed >> 4).to(torch.int16) codes = torch.stack([lo4, hi4], -1).flatten(-2) f16 = (codes | 0x6400).view(torch.float16).float() - 1024.0 # exact: 1024 + q assert torch.equal(f16, q.float()) W_hat = (s * (f16 - z)).view(N, K) # formula (104.1) x = torch.randn(1, K) print("bytes FP16 / W4 (with scales):", (N*K*2) / (packed.numel() + 2*2*s.numel())) y4, y = x @ W_hat.T, x @ Wf.T print("W4A16 GEMV relative error:", ((y4 - y).norm() / y.norm()).item()) # 5) MoE grouped GEMM, formula (126.9): sort tokens by expert, one GEMM per non-empty group E_, k_, d, f, T = 8, 2, 64, 128, 16 x = torch.randn(T, d); Wup = torch.randn(E_, f, d) / 8 topi = torch.topk(torch.randn(T, E_), k_, dim=-1).indices # stand-in router flat_e = topi.flatten(); tok = torch.arange(T).repeat_interleave(k_) order = torch.argsort(flat_e, stable=True) counts = torch.bincount(flat_e, minlength=E_) offs = torch.cat([torch.zeros(1, dtype=torch.long), counts.cumsum(0)]) xs = x[tok[order]] # tokens grouped by expert out = torch.empty(T * k_, f) for e in range(E_): # a grouped GEMM does this in ONE launch a, b = offs[e].item(), offs[e+1].item() if b > a: out[a:b] = xs[a:b] @ Wup[e].T ref = torch.stack([x[t] @ Wup[topi[t, j]].T for t in range(T) for j in range(k_)]) back = torch.empty_like(out); back[order] = out print("tokens per expert:", counts.tolist(), " touched:", int((counts > 0).sum())) print("grouped GEMM max error:", (back - ref).abs().max().item()) print("expected touched (uniform):", round(E_ * (1 - (1 - k_ / E_) ** T), 2))
Output (PyTorch 2.x on a CPU): gate + up times 70.1, 70.4, 121.6 and 972.8 µs; tiling (0.015625, 32, 1, 0.2424…) and (0.015625, 128, 1, 0.9697…); split-K relative error about \(10^{-6}\) (float rounding only); 3.76 times fewer bytes; W4A16 relative output error 0.10 on random Gaussian weights; tokens per expert [3, 5, 3, 6, 5, 4, 3, 3], all 8 touched against 7.92 expected; grouped GEMM error about \(10^{-6}\).
Where this is used
| Setting | Shape of the linear layers | What runs it |
|---|---|---|
| Chat decode at small batch | GEMV / flat GEMM, \(M\) = 1 to 64, memory-bound | GEMV or flat-GEMM kernels (TensorRT-LLM has a dedicated GEMV [Certain]); with 4-bit weights, Marlin-style kernels (in vLLM [Certain]) |
| Long-prompt prefill, RAG | GEMM, \(M\) in the thousands, compute-bound | cuBLAS / CUTLASS big-tile GEMM; FP8 or INT8 tensor cores to go faster (session 105) |
| VLM video question answering | Prefill of thousands of vision tokens (big GEMM), then short decode (GEMV) | The same model switches kernels by \(M\) between the two phases (Algorithm 3) |
| Video retrieval and frame embedding | Encoder over many frames at once: GEMM at large \(M\) | Compute-bound; batch frames to stay above the ridge |
| Live captioning, key-moment alerts on a broadcast | Decode at batch 1 to 8 under a latency target: GEMV | Memory-bound: W4A16 and good GEMV kernels give the latency win |
| MoE serving (Mixtral, DeepSeek-V3) | Many small, uneven per-expert GEMMs | Grouped GEMM or fused MoE kernels (Triton kernels in vLLM [Certain]); MegaBlocks block-sparse kernels for training [Certain] |
| Continuous batching with chunked prefill | \(M\) changes every step | Shape-aware dispatch per step; CUDA graphs captured per batch size (session 127) |
Common mistakes
- Judging a decode kernel by TFLOP/s. At \(M = 1\) the best possible value is 0.34% of peak for gate + up on an H100. Measure achieved memory bandwidth instead: bytes of weights divided by kernel time, against 3.35 TB/s.
- Calling the same GEMM for prefill and decode. A kernel tuned for \(M = 4096\) pads, under-fills the SMs and misses bandwidth at \(M = 1\). Dispatch by \(M\).
- Dequantizing weights to FP16 in HBM, then calling a normal GEMM. This adds a write and a read of the full FP16 weights and removes the whole benefit of W4. Dequantize in registers.
- Forgetting wave quantization when picking tile sizes. 133 blocks on 132 SMs run in 2 waves at 50% efficiency; a slightly larger \(B_N\) or a different split-K can be much faster.
- Using split-K for big GEMMs, or atomics when results must be reproducible. Split-K helps only when there are too few tiles; atomic adds change the summation order between runs.
- Benchmarking MoE kernels with perfectly balanced routing. Real loads are uneven; padding to capacity, the slowest expert and the touched-expert count all depend on it.
- Forgetting the LM head. At 1.05 GB it is 7% of the linear weights of Llama 3.1 8B and its \(N = 128{,}256\) is a shape of its own; it deserves its own tuned kernel and can be computed only for the last position in prefill.
Interview questions
Why is prefill a GEMM and decode a GEMV?basic
What is the arithmetic intensity of a linear layer with M tokens, and why is it about M?core
At what batch size does a decode linear layer become compute-bound on an H100?core
Why can a library GEMM be slow at \(M = 1\), even though the layer is memory-bound anyway?core
What is split-K, and when is it worth it?core
What is wave quantization, and how do Stream-K or tile choices address it?advanced
How does a W4A16 kernel work, and why must dequantization happen inside it?core
Marlin keeps nearly 4× up to batch 16 to 32, then the gain declines. Why?advanced
How would you run an MoE expert layer efficiently? Compare the options.advanced
Why is MoE decode expensive in memory traffic even though each token uses only k experts?advanced
How do you pick the right kernel for each linear layer at run time?core
Exercises
- For the down projection of Llama 3.1 8B (\(N = 4096\), \(K = 14{,}336\)) at \(M = 8\) in BF16, compute \(F\), \(Q\) and \(I\). Is it memory-bound on an A100?
- A GEMM kernel uses \(B_M = 64\). What fraction of its tensor-core work is useful at \(M = 5\), \(M = 64\) and \(M = 65\)?
- The QKV projection (\(N = 6144\)) runs at \(M = 1\) with \(B_N = 128\) on an H100. How many blocks? Which split-K factor among 1, 2, 4, 8 gives the best wave efficiency?
- Compute \(b_{\text{eff}}\) and the ideal memory-bound speed-up of W4A16 for group sizes 32 and 64.
- Using formula (126.11), how many distinct Mixtral experts does a decode batch of 2 touch on average? What fraction of expert weights is that?
- Double buffering: \(n = 10\), \(L = 3\), \(C = 1\). Compute both times. What is the lower limit for any number of buffers?
Answerscheck
Key takeaways
- A linear layer \(Y = XW^\top\) has intensity \(I \approx M\) (126.2): the number of tokens in the call is the reuse factor of the weights. Prefill is a compute-bound GEMM; decode is a memory-bound GEMV or flat GEMM, until \(M\) reaches about \(P/B\) (295 on an H100, 153 on an A100).
- Big-tile GEMM kernels lose on thin shapes through padding (126.5), too few blocks and wave quantization (126.6). Fixes: small \(M\)-tiles or operand swap, split-K (126.7) or Stream-K, double buffering (126.8), and dispatch by \(M\).
- W4A16 must dequantize in registers; it saves up to \(16/b_{\text{eff}} = 3.76\times\) (126.9) while memory-bound, and the gain fades as \(M\) grows. Padding hurts quantized kernels more.
- MoE layers need grouped GEMM: sort tokens by expert, one launch over all experts’ tiles. In decode, the touched experts (126.11) set the bytes read.
Key formulas
References for this session
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
- NVIDIA (docs). CUDA C++ Programming Guide
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
- NVIDIA (docs). CUDA C++ Programming Guide
- Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures
- Frantar, Castro, Chen, Hoefler, Alistarh (2024). MARLIN: Mixed-Precision Auto-Regressive Parallel Inference on Large Language Models
- Park et al. (2022). LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models
- Gale, Narayanan, Young, Zaharia (2022). MegaBlocks: Efficient Sparse Training with Mixture-of-Experts
- Osama, Merrill, Cecka, Garland, Owens (2023). Stream-K: Work-centric Parallel Decomposition for Dense Matrix-Matrix Multiplication on the GPU
- Lin et al. (2023). AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration
- Meta (mirrored by Unsloth on Hugging Face) (2024). Llama 3.1 8B Instruct: config.json
- Mistral AI (2023). Mixtral-8x7B-v0.1: config.json
- DeepSeek-AI (2024). DeepSeek-V3: config.json
- NVIDIA (docs). NVIDIA A100 Tensor Core GPU: product specifications
- NVIDIA (docs). NVIDIA H100 Tensor Core GPU: product specifications
- NVIDIA (docs). PTX ISA: warp-level matrix multiply-accumulate instructions (mma)
- vLLM project (docs). vLLM documentation