Threads, workgroups and memory.

Threads, workgroups and memory

Threads, workgroups and memory.

A graphics chip does not do one sum very fast. It does thousands of small sums at the same time. Tonight Pylon runs the cannery where that happens, and counts every trip to the warehouse.

One worker, one can

The job: add two lists of numbers, element by element, into a third. A list of 1,048,576 numbers.

On a graphics chip, each element gets its own worker, called a thread. Thread 40 reads number 40 from each list, adds them, and writes the sum to place 40. Every thread runs the same few lines of code.

Crews

Threads come in crews called workgroups. You choose the crew size; in WebGPU a crew may hold up to 256 threads by default.

A thread finds its element from its crew's number and its place in the crew: crew number times crew size, plus its place. With crews of 16, crew 2, place 8, is element 40.

Crews come in whole numbers. Add 1,000 numbers with crews of 64 and you need 16 crews, 1,024 threads. The last 24 have nothing to do, so the code must check that its element exists.

One past the end

Get that check wrong by one, and one idle thread writes one place past the end of the list. In a list of 40 numbers, numbered 0 to 39, element 40 has no place of its own.

If the check is off by one, does the program crash? (the film pauses here)

On a graphics chip that need not crash. The WGSL rules call it an error, but let it end quietly: the stray write may land anywhere in the same buffer, be dropped, or stop that one thread. So the output can look right while something else in the same buffer was spoiled.

Our checker compares every sum with a slow, careful one on the main processor, and plants guard values just past the end. Of 12 test cases, nine came from three kernels we broke on purpose, each run three ways. Together the two checks catch seven of the nine. The two they miss are stray writes the chip dropped, which leave every sum right. Only our emulator, which counts every write, sees those.

Trips to the warehouse

On NVIDIA chips, each crew is split into teams of 32 threads, called warps; other chips use other team sizes, from 4 to 128, and our counts use NVIDIA's 32. When a team reads from memory, the chip fetches whole blocks at a time; the current CUDA guide describes blocks of 32 bytes.

If the 32 threads read 32 neighbouring numbers, 4 bytes each, that is 128 bytes: 4 blocks. One team, a few trips.

Now spread the reads out, every eighth number. The same 32 reads now touch 32 blocks, one per thread.

Counting the trips

Count every trip for the whole job, reads and writes. With neighbouring reads: 393,216 blocks. With reads spread eight apart: 2,228,224. That is 5.67 times the trips, not 8, because the writes still go to neighbouring places. Most of each block fetched is thrown away.

Reads spread eight apart. How many times the trips? (the film pauses here)

Spreading them further changes nothing more in this model, because each thread already has a block of its own.

Your own chip

These are counts from a model of the chip, not times. Real chips have caches that hide some of the cost, and they differ from one another.

So the lab runs the real kernel on the chip in your own computer, if your browser allows it, and times it. If the time for spread-out reads is far from what the count predicts, then caches, a different team or block size, or the cost of starting the job are at work.

Goodnight

Thousands of small workers, in crews, fetching in blocks. Fast code keeps neighbouring workers on neighbouring numbers, and checks the edges.

Next in the cannery: multiplying whole tables, and carrying trays instead of single cans. Goodnight.