LLM & VLM courseBlog
126Track 5: LLM inference and serving · session 49 of 65

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.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 to 1.5 hours)Level: IntermediateBefore this: Sessions 82, 85 and 104 (the roofline; CUDA basics; weight-only quantization)

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

\[ Y = X W^\top, \qquad F = 2\,M N K \ \text{ FLOPs} \tag{126.1} \]

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

\[ Q = b_a M K + b_w N K + b_a M N, \qquad I = \frac{F}{Q} \;\overset{b = 2}{=}\; \frac{M N K}{M K + N K + M N} \;\approx\; M \quad (M \ll N, K) \tag{126.2} \]
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

\[ t = \max\!\left( \frac{F}{P},\ \frac{Q}{B} \right), \qquad \text{compute-bound when } I \gt I^\ast = \frac{P}{B} \tag{126.3} \]

\(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.

Worked example: the MLP gate + up layer on an H100

\(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]

BF16 weightsW8A16W4A16 (groups of 128)peak math speed
Figure 1. Roofline of one Llama 3.1 8B linear layer as a function of the number of tokens \(M\) (formulas 126.1 to 126.3, and 126.9 for the quantized formats). The curves show useful TFLOP/s; the dot is the selected format at the selected \(M\). The readout also gives the time of all linear layers of the model (32 blocks + LM head) for one step at this \(M\).
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.

Algorithm 1: one thread block of a tiled GEMM, \(Y = XW^\top\)
  1. input: tile position \((i, j)\); tile sizes \(B_M, B_N, B_K\)
  2. \(\text{acc} \leftarrow 0\) // \(B_M \times B_N\), FP32, in registers
  3. for \(k = 0, B_K, 2B_K, \dots, K - B_K\) do
  4.   load \(X[iB_M : (i{+}1)B_M,\ k : k{+}B_K]\) into shared memory // rows past M are padded with zeros
  5.   load \(W[jB_N : (j{+}1)B_N,\ k : k{+}B_K]\) into shared memory
  6.   \(\text{acc} \leftarrow \text{acc} + X_{\text{tile}} W_{\text{tile}}^\top\) // tensor-core instructions
  7. end for
  8. 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

\[ I_{\text{tile}} = \frac{2 B_M B_N B_K}{2 (B_M + B_N) B_K} = \frac{B_M B_N}{B_M + B_N} \tag{126.4} \]

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

\[ u = \frac{M}{B_M \lceil M / B_M \rceil} \tag{126.5} \]

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

\[ n_{\text{blk}} = \Big\lceil \frac{M}{B_M} \Big\rceil \Big\lceil \frac{N}{B_N} \Big\rceil S, \qquad w = \Big\lceil \frac{n_{\text{blk}}}{n_{\text{SM}}} \Big\rceil, \qquad \eta = \frac{n_{\text{blk}}}{w \, n_{\text{SM}}} \tag{126.6} \]
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:

\[ Y = \sum_{s=1}^{S} X_{[:,\,\mathcal{K}_s]}\, W_{[:,\,\mathcal{K}_s]}^\top, \qquad \Delta Q = 2 \cdot S\, M N \cdot 4 \ \text{bytes (FP32 partials written and read)} \tag{126.7} \]

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]

\(B_M\) \(B_N\) split-K \(S\)
real output rowspadding rows (zeros)busy SM in the last wave
Figure 2. How one linear layer is cut into thread blocks (formulas 126.5 to 126.7). Top: the output \(Y\) (\(M \times N\)) as a grid of \(B_M \times B_N\) tiles; the coloured part of each tile is real rows, the rest is padding. Bottom: the SMs of the GPU, with the ones that have a block in the last wave coloured. The readout compares the padded tensor-core time with the time to read the weights.
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]

Algorithm 2: GEMV kernel, \(y = Wx\), one warp per output row
  1. input: \(W \in \R^{N \times K}\) row-major in HBM, \(x \in \R^{K}\)
  2. copy \(x\) into shared memory once per block
  3. for each warp, in parallel: \(n \leftarrow\) its row
  4.   lane \(\ell \in \{0, \dots, 31\}\): \(\text{part} \leftarrow 0\)
  5.   for \(j = 8\ell, 8\ell + 256, 8\ell + 512, \dots\) do // 16-byte loads: 8 BF16 weights per lane
  6.     \(\text{part} \leftarrow \text{part} + \sum_{u=0}^{7} W[n, j{+}u]\, x[j{+}u]\) // FP32 accumulate
  7.   end for
  8.   \(\text{part} \leftarrow\) warp-shuffle sum over the 32 lanes // 5 shuffle steps
  9.   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:

\[ t_{\text{single}} = n\,(L + C), \qquad t_{\text{double}} = L + (n - 1)\max(L, C) + C \tag{126.8} \]

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]

load tile \(k\) from HBMmultiply tile \(k\)
Figure 3. One thread block walking along \(K\) (formula 126.8). With a single buffer, the block must wait for each load before it computes, then wait for the compute before it loads again. With two buffers the next load overlaps the current compute.
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]

Algorithm 3: shape-aware dispatch for one linear layer (heuristic dataflow)
  1. offline, for each layer shape \((N, K)\) of the model do
  2.   time GEMV, flat GEMM and library GEMM for \(M = 1, 2, 4, \dots\)
  3.   \(M_1 \leftarrow\) first \(M\) where flat GEMM beats GEMV; \(M_2 \leftarrow\) first \(M\) where GEMM beats flat GEMM
  4.   also store the best \(B_N\) and split-K \(S\) for each range // formula (126.6)
  5. at run time: given \(M\) (tokens in this step)
  6.   if \(M \lt M_1\): GEMV on CUDA cores
  7.   else if \(M \lt M_2\): flat GEMM on tensor cores, \(M\) padded to 8, double buffering
  8.   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

\[ b_{\text{eff}} = 4 + \frac{16 + 16}{g} \ \text{bits}, \qquad \frac{t_{\text{BF16}}}{t_{\text{W4}}} \;\le\; \frac{16}{b_{\text{eff}}} = 3.76 \quad (g = 128) \tag{126.9} \]

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\):

\[ \text{fp16}(\texttt{0x6400} \;|\; q) - 1024 = q, \qquad q \in \{0, \dots, 15\} \tag{126.10} \]

(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]

Worked example: why W4A16 decode kernels need small \(B_M\)

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:

  1. 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.
  2. 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]
  3. 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]
Algorithm 4: one MoE expert layer with a grouped GEMM
  1. input: tokens \(X \in \R^{T \times d}\), router top-\(k\) indices, expert weights \(W_1, \dots, W_E\)
  2. flatten the \(kT\) (token, expert) pairs; sort them by expert // a counting sort: one histogram and a prefix sum
  3. \(M_e \leftarrow\) count per expert; offsets \(o_e \leftarrow \sum_{e' \lt e} M_{e'}\)
  4. gather the rows of \(X\) in sorted order // often fused into the GEMM’s loads
  5. 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\)
  6. launch ONE kernel over all tiles; tile \(\tau\) of expert \(e\) computes rows \(o_e + \dots\) with \(W_e\)
  7. 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

\[ \E[\text{experts touched}] = E \left( 1 - \left(1 - \frac{k}{E}\right)^{T} \right) \tag{126.11} \]
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]

Worked example: padding a prefill MoE step

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.

\(B_M\)
tokens sent to each expertcapacity padding (to the largest load)
Figure 4. One MoE layer for one step, with seeded uniform random routing (each token picks \(k\) different experts). Bars: tokens per expert. The readout counts touched experts (against formula 126.11), the expert-weight bytes that must be read, and the useful share of rows for padding-to-capacity and for a grouped GEMM.
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

SettingShape of the linear layersWhat runs it
Chat decode at small batchGEMV / flat GEMM, \(M\) = 1 to 64, memory-boundGEMV or flat-GEMM kernels (TensorRT-LLM has a dedicated GEMV [Certain]); with 4-bit weights, Marlin-style kernels (in vLLM [Certain])
Long-prompt prefill, RAGGEMM, \(M\) in the thousands, compute-boundcuBLAS / CUTLASS big-tile GEMM; FP8 or INT8 tensor cores to go faster (session 105)
VLM video question answeringPrefill 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 embeddingEncoder 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 broadcastDecode at batch 1 to 8 under a latency target: GEMVMemory-bound: W4A16 and good GEMV kernels give the latency win
MoE serving (Mixtral, DeepSeek-V3)Many small, uneven per-expert GEMMsGrouped 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 stepShape-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
A linear layer multiplies an \(M \times K\) activation matrix by a fixed weight matrix. In prefill all prompt tokens go through together, so \(M\) is batch × prompt length (thousands): a matrix–matrix product. In decode each sequence contributes one new token per step, so \(M\) is the batch size; at batch 1 the activation is one vector and the product is matrix–vector. Small batches give a "flat" GEMM in between.
What is the arithmetic intensity of a linear layer with M tokens, and why is it about M?core
\(F = 2MNK\) FLOPs and \(Q \approx 2(MK + NK + MN)\) bytes in BF16, so \(I = MNK/(MK + NK + MN)\). For \(M \ll N, K\) the weight term dominates, giving \(I \approx M\): each weight is loaded once and used once per token. So batch size is the weight reuse factor, and decode at batch 1 has \(I \approx 1\) FLOP/byte.
At what batch size does a decode linear layer become compute-bound on an H100?core
When \(I \approx M\) exceeds the ridge \(P/B = 989/3.35 = 295\) FLOP/byte in dense BF16. Solving exactly for the Llama 3.1 8B layers gives about 320 to 345 because activation traffic also grows with \(M\). With W4A16 weights the ridge is reached about 3.76 times earlier (around 85 for gate + up). In practice attention and KV-cache reads keep decode memory-bound even longer.
Why can a library GEMM be slow at \(M = 1\), even though the layer is memory-bound anyway?core
Three reasons. (1) Padding: tiles with \(B_M = 64\) make 98% of the tensor-core work zeros; in BF16 on an H100 this is hidden, but with 4-bit weights or on lower-ridge GPUs the padded math can exceed the memory time. (2) Parallelism: few output tiles (32 for a 4096-wide layer with \(B_N = 128\)) leave most SMs idle, so HBM bandwidth is not reached. (3) The pipeline and tile shapes are tuned for reuse, not for streaming one matrix at full bandwidth. FlashDecoding++ reports over 50% under-utilization from padding in such designs.
What is split-K, and when is it worth it?core
Split the inner dimension \(K\) into \(S\) slices, compute partial products for the same output tile in different blocks, then add them. It multiplies the block count by \(S\), which fixes low parallelism when \(M\) and \(N\) give too few tiles. The cost is \(2SMN \times 4\) bytes of FP32 partials plus a reduction step: tiny when \(M\) is small (0.39% of weight bytes for \(S = 4\) on a 4096 × 4096 layer at \(M = 1\)), large for big GEMMs, where it is not needed. Atomic reductions make results non-deterministic.
What is wave quantization, and how do Stream-K or tile choices address it?advanced
Blocks run in waves of \(n_{\text{SM}}\). If the block count is just above a multiple of the SM count (133 on 132 SMs), the last wave is nearly empty and efficiency drops toward 50%. Fixes: choose \(B_M, B_N, S\) so the count divides well, or use Stream-K, which gives each SM an equal share of the total inner-loop iterations across tiles, so efficiency no longer depends on the tile count.
How does a W4A16 kernel work, and why must dequantization happen inside it?core
The kernel loads packed 4-bit codes plus per-group scales and zeros, converts them to FP16 in registers (for example with the 0x6400 mantissa trick and one fused multiply-add for scale and zero), and runs an FP16 multiply with FP32 accumulation. Only the 4.25 bits per weight (for \(g = 128\)) cross HBM, giving up to 3.76× less traffic. Expanding to FP16 in memory first would add a full FP16 write and read and make it slower than plain FP16.
Marlin keeps nearly 4× up to batch 16 to 32, then the gain declines. Why?advanced
The speed-up comes only from fewer weight bytes, so it holds while the layer is memory-bound. With 3.76× fewer bytes the layer reaches the compute roof at about \(M = P/(3.76\,B)\) (around 80 on an H100 for big layers), and dequantization instructions plus any tile padding add compute before that. Past that point both FP16 and W4A16 are bound by the same FP16 tensor-core math, so the ratio falls toward 1.
How would you run an MoE expert layer efficiently? Compare the options.advanced
Looping over experts launches up to \(E\) small GEMMs that each under-fill the GPU. Padding every expert to a fixed capacity allows one batched GEMM but drops overflow tokens and computes zeros. A grouped GEMM sorts tokens by expert (histogram + prefix sum), then launches one kernel over the tiles of all experts with their own \(M_e\): no dropping, padding only in each expert’s last tile, empty experts free. Block-sparse formulations (MegaBlocks) and fused Triton MoE kernels (vLLM) are variants of this idea. Tune \(B_M\) to the typical per-expert load.
Why is MoE decode expensive in memory traffic even though each token uses only k experts?advanced
Different tokens in the batch pick different experts. With uniform routing the touched experts are \(E(1 - (1 - k/E)^T)\): for DeepSeek-V3 about 163 of 256 at batch 32, each with about one token. Each touched expert’s weights must be streamed in full for GEMV-sized work, so bytes per useful FLOP are high. Larger batches, expert parallelism across GPUs and weight quantization help.
How do you pick the right kernel for each linear layer at run time?core
The \([N, K]\) shapes of an LLM are fixed, only \(M\) varies. So profile offline per shape and GPU: GEMV, flat GEMM and big-tile GEMM over a range of \(M\), with their tile sizes and split-K. Record the switch points (FlashDecoding++ calls them \(M_1\) and \(M_2\)) and dispatch by \(M\) at run time. cuBLAS heuristics and engine autotuning do the same in a more general way.

Exercises

  1. 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?
  2. A GEMM kernel uses \(B_M = 64\). What fraction of its tensor-core work is useful at \(M = 5\), \(M = 64\) and \(M = 65\)?
  3. 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?
  4. Compute \(b_{\text{eff}}\) and the ideal memory-bound speed-up of W4A16 for group sizes 32 and 64.
  5. 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?
  6. Double buffering: \(n = 10\), \(L = 3\), \(C = 1\). Compute both times. What is the lower limit for any number of buffers?
Answerscheck
1. \(F = 2 \cdot 8 \cdot 4096 \cdot 14336 = 0.940\) GFLOP; \(Q = 2(8 \cdot 14336 + 4096 \cdot 14336 + 8 \cdot 4096) = 117.7\) MB; \(I = 7.98\). Far below the A100 ridge of 153: memory-bound. 2. \(5/64 = 7.8\%\); \(64/64 = 100\%\); \(65/128 = 50.8\%\). 3. \(6144/128 = 48\) blocks; \(S = 1\): 36.4%; \(S = 2\): 96 blocks, 72.7%; \(S = 4\): 192 blocks, 2 waves, 72.7%; \(S = 8\): 384 blocks, 3 waves, 97.0%. Best is \(S = 8\) (\(S = 2\) is close behind with half the partials). 4. \(g = 32\): 5.0 bits, \(16/5 = 3.2\times\); \(g = 64\): 4.5 bits, \(3.56\times\). 5. \(8(1 - 0.75^2) = 3.5\) experts, 43.75% of the expert weights (against 25% at batch 1). 6. Single: \(10 \times 4 = 40\); double: \(3 + 9 \times 3 + 1 = 31\). Any pipeline still needs \(nL = 30\) to stream the data, plus the last compute: 31 is already at that limit.

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

\[ I = \frac{MNK}{MK + NK + MN} \approx M, \quad t = \max\!\Big(\frac{F}{P}, \frac{Q}{B}\Big), \quad u = \frac{M}{B_M\lceil M/B_M\rceil}, \quad \eta = \frac{n_{\text{blk}}}{\lceil n_{\text{blk}}/n_{\text{SM}}\rceil n_{\text{SM}}} \]
\[ b_{\text{eff}} = 4 + \frac{32}{g}, \qquad \E[\text{touched}] = E\Big(1 - \big(1 - \tfrac{k}{E}\big)^T\Big) \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
  3. NVIDIA (docs). CUDA C++ Programming Guide
  4. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  5. Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
  6. NVIDIA (docs). CUDA C++ Programming Guide
  7. Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures
  8. Frantar, Castro, Chen, Hoefler, Alistarh (2024). MARLIN: Mixed-Precision Auto-Regressive Parallel Inference on Large Language Models
  9. Park et al. (2022). LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models
  10. Gale, Narayanan, Young, Zaharia (2022). MegaBlocks: Efficient Sparse Training with Mixture-of-Experts
  11. Osama, Merrill, Cecka, Garland, Owens (2023). Stream-K: Work-centric Parallel Decomposition for Dense Matrix-Matrix Multiplication on the GPU
  12. Lin et al. (2023). AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration
  13. Meta (mirrored by Unsloth on Hugging Face) (2024). Llama 3.1 8B Instruct: config.json
  14. Mistral AI (2023). Mixtral-8x7B-v0.1: config.json
  15. DeepSeek-AI (2024). DeepSeek-V3: config.json
  16. NVIDIA (docs). NVIDIA A100 Tensor Core GPU: product specifications
  17. NVIDIA (docs). NVIDIA H100 Tensor Core GPU: product specifications
  18. NVIDIA (docs). PTX ISA: warp-level matrix multiply-accumulate instructions (mma)
  19. vLLM project (docs). vLLM documentation