You already know: warps, blocks, barriers and shared memory (CUDA programming model); coalescing, reuse and bank conflicts (GPU memory hierarchy); Big-O and why work and depth both matter (D1 Data structures); matrix multiplication (D2 Linear algebra).
Why this matters for Atlas. A handful of parallel patterns cover most GPU kernels in deep learning: map (elementwise ops), reduce (sums, maxima: norms, softmax, loss), scan (prefix sums: top-p sampling, stream compaction, MoE token packing), histogram/scatter with atomics (counting tokens per expert), and tiled matrix multiplication. Each has a sequential algorithm that is wrong for a GPU and a parallel algorithm that is right. This lesson builds the parallel versions, measures their work (total operations) and depth (parallel steps), and shows the GPU-specific tricks (warp shuffles, privatization, tiling) that make them fast.
1. Work and depth
The question. Summing a million numbers takes a million steps sequentially. How many steps can it take in parallel?
Start from nothing. Two measures describe a parallel algorithm: