Parallel Sum Reduction (WebGPU)

Difficulty: Medium · Concept: GPU/AI Infrastructure — The CUDA Programming Model

Every other practice problem on this site runs Python. This one is different on purpose: you write a real WGSL compute shader — the browser-native equivalent of a CUDA kernel — and it runs on a real GPU (or a software fallback where no GPU is exposed to the browser), through WebGPU, a real, standards-based browser API. Same idea as every other problem here — real execution, real pass/fail, no simulation — just a genuinely different kind of "real" this time: parallel hardware instead of a single CPU core.

Why This Isn't Just "Add the Numbers"

Summing an array in Python is one line. Summing it on a GPU, where potentially hundreds of threads run at once, is a different problem entirely: if every thread just did output[0] += input[thread_id], multiple threads would read-modify-write output[0] at the same instant and silently lose updates — a real race condition, not a hypothetical one. The standard fix is shared memory (see the CUDA memory hierarchy — WGSL's var<workgroup> is the same concept, fast memory shared only within one thread block/workgroup) plus a tree reduction: every thread writes its own element into shared memory once, then threads repeatedly combine pairs in parallel, halving the number of active threads each round, until one value remains. workgroupBarrier() is what makes this safe — it forces every thread in the workgroup to reach that point before any of them proceeds, so no thread ever reads a shared-memory slot before another thread has finished writing to it.

Real constraint, stated honestly: this problem is scoped to a single workgroup — your array has at most 256 elements. That's not a simplification hiding a harder "real" version; it's the actual boundary of what one workgroup's shared memory can hold. Reducing an array larger than one workgroup for real needs either multiple dispatch passes or atomics across workgroups — a genuinely harder follow-up problem, not covered here.

Your task: complete the compute shader below so that after it runs, output[0] holds the sum of every element in input. The buffer bindings and workgroup size are already wired up — you're implementing the load-into-shared-memory step, the tree-reduction loop, and the final write.

Next: GPU/AI Infrastructure & Distributed Training for the full CUDA programming model this shader is a hands-on instance of.