Building an LLM from scratchPart 7 of 15

Build note

Batching the window: 547 ms to 2 ms

The same arithmetic, launched in a different shape, ran a training step in about 2 milliseconds instead of 547. Nothing about the mathematics changed. The loss curve is identical to the one-token-at-a-time path.

The analogy is a filing office. If one clerk walks each form across the room separately, the walk dominates the work. Put every form on one trolley and make one trip, and the walking stops being the job.

What “batching the window” means

A training window is a sequence of tokens, here 256 of them. In the previous phase the trainer walked that window one position at a time: forward for token 1, backward for token 1, forward for token 2, and so on. Each position was a small matrix-vector product.

But the positions are independent in the forward pass. Token 5 does not need token 6 to compute its own hidden state; it only needs the tokens before it, and those are already in the input. So all 256 positions can be processed together as one matrix-matrix product instead of 256 matrix-vector products.

That single observation is the phase. GHEDI_TRAIN_BATCHED, on by default, processes all positions together.

The operations that had to change

The batch dimension is new, so every operation needed a batched variant.

d_matmul_batched(out[N,M], w[M,K], x[N,K]) is the core one. The CPU backend loops the existing scalar primitive, which makes it the bit-exact oracle. The CUDA backend uses a 16x16 register-tiled kernel that produces 64 to 256 blocks for the default shapes, instead of the single block the old path launched.

Row-wise operations got their own versions: d_rmsnorm_batched, d_softmax_batched and d_embedding_batched. Each row is independent, so each gets one block or one thread per element. The elementwise operations needed no variant because they already worked on a flattened buffer.

Causal attention needed real work. The forward pass now materialises the score matrix as [H*N, N] with attn_scores_kernel, one thread per (head, query, key) triple, which is H*N*N threads. A row softmax follows, then attn_av_kernel multiplies by the values. That replaces a one-block, n_heads-thread walk with something that fills the card.

The backward pass mirrors all of it: batched matmul, RMSNorm, softmax and embedding backward, plus the score-softmax-value attention backward that computes dA, dS, dQ, dK and dV. Every one is verified per operation and again through make gradcheck-gpu.

Cutting the overhead

Making the arithmetic wide was only half the job. The other half was removing the launches that were not arithmetic at all.

Device cross-entropy replaced a per-step round trip of the probability and gradient buffers between host and device. The gradient resets collapsed from 34 to 10, by arranging the scratch buffers layer-major so each one can be cleared with a single contiguous reset, and by making the whole backward pass clear once instead of per layer. Q, K and V are fused into one launch.

The totals tell the story:

Measurement Per-position Batched
Milliseconds per step ~547 ~2.0
Kernel launches per step ~32,600 ~196
Gradient resets per step ~7,700 11

The loss and validation curves are identical. The Phase 5 per-position path stays available behind GHEDI_TRAIN_BATCHED=0, which is what makes the comparison possible: there is still a reference to check against.

At about 2 ms/step the GPU trainer also beats the CPU, which runs the same config at roughly 209 ms/step.

What the new profile said

The old profile put 78.5% of API time in launches. The new one puts ~1.78 ms of kernel execution inside a ~2.0 ms step, so the card is now doing work for most of the step.

The top bottleneck moved. It is now matmul_backward_w_batched_kernel, the weight-gradient reduction, which is starved of parallelism for a different reason: the reduction over positions collapses to a small output. That is a real and recordable next target, not a mystery.

I also deferred cudaGraph capture, and wrote down why. The step still contains blocking copies for the token and target uploads, the loss scalar, and the Adam gradient-norm partials, plus a cudaFree inside weight invalidation. A clean capture needs device-resident token buffers first. The profile bounded the payoff at about 90% GPU-busy already, so the exit criterion was met without it. Deferring with a recorded blocker is different from dropping it.

What it taught me

Occupancy is the whole game. The card has 82 SMs, and a kernel that launches one block uses one of them. The fix was not a faster kernel; it was a kernel shape that gives the hardware something to run in parallel.

The second lesson is that “identical results, much faster” is the best kind of optimisation, because you can prove it. The per-position path stayed in the code precisely so that claim could be checked.

How this was made

  • Written by: Rupesh, from the ghedi-c repository (src/train_device.c, src/device_cuda.cu, docs/18-gpu-training.md, docs/19-gpu-kernel-reference.md, ROADMAP.md Phase 6), with AI drafting and editing.
  • Numbers: the before/after table, launch counts, gradient resets and the kernel-execution share come from the nsys profiles recorded in docs/18-gpu-training.md.
  • AI-assisted sections: structure, explanations and copy editing.