Global and local loops

Two more axes

%b = range 3 axis=global      # one iteration per block
%t = range 32 axis=local      # one iteration per thread of the block
%m = mul %b 32
%i = add %m %t                # element 32b + t
...
%et = end %s %t
%eb = end %et %b

A global loop is the grid: each iteration is a block, and blocks may run in any order, at the same time. A local loop is a block's threads, so its bound is the block size: a literal from 1 to 1024. Like week 7's axes, neither changes a single bit. Run as plain loops, the program means what it always did.

A few rules keep the program shaped like a kernel:

• A local loop sits inside a global loop, possibly inside plain loops in its body, and never inside another local loop.
• Every local loop of one global loop has the same bound, because a kernel has one block size.
• No thread, global or local loop inside a global loop's body, other than its own local loops.
• Every store inside a global loop is inside a local loop. A store outside one would run once on every thread.

Why week 7's slice rule isn't enough

Week 7's rule gave each thread-loop iteration a slice r·S to r·S + S - 1, with one parallel index. Now there are two at once, the block and the thread, and real kernels mix them up. The 512×512 GEMM in the speed test writes element

(16·by + ty)·512 + 16·bx + tx        by = g div 32, bx = g mod 32,  ty = t div 16, tx = t mod 16

Thread t of block g isn't writing one contiguous slice: block g owns a 16×16 square, spread across 16 rows. We need a rule that sees that.

The mixed-radix rule

Write the offset as a sum of terms. A term is a digit when it's a loop index, or that index's div or mod by a literal, times a positive literal coefficient. Every digit has a largest value: n - 1 for a loop of n, (n - 1) div k for a div, and k - 1 for a mod (or n - 1, if that's smaller). The GEMM's offset expands to four digits:

Now sort by coefficient, and check that each one is greater than the most all the smaller digits can add up to: 8192 is more than 7680 + 496 + 15 = 8191, 512 is more than 511, 16 is more than 15. Then the offset is a mixed-radix number, like a time written as hours, minutes and seconds. Two different combinations of digits always give different offsets, for the same reason 2:59 and 3:00 are different times. So no two threads, of the same block or of different blocks, ever write the same element.

The rule is checked twice, on two pieces of code. Once per local loop, with t as the parallel index and the block fixed: do the block's threads collide? And once over the whole global loop body, with g as the parallel index: do the blocks collide? Loops inside the piece being checked count as digits too, since one thread runs all their iterations.

Four more parts complete the rule:

• Terms that don't involve a loop of the code being checked are the same for every thread, so they're ignored: a constant, a loop outside the kernel, and for one phase also the block index and plain loops around the phase.
• A vector access of k elements is a digit too: coefficient 1, largest value k - 1.
• Coefficients are positive. 7 - t walks backwards through memory, which is perfectly safe, but the rule doesn't try to prove it.
• The offset has to contain the parallel index. o[0] written by every block is the plainest race there is.

It applies to every store, and every load of memory the same code also stores into. Memory that's only read can be read anywhere: the GEMM's A and B are read by many blocks at once, which is fine.

The same expression, every time

One more rule: within the code being checked, every access to one buffer must use the same offset expression, the very same nodes, not just the same digits. sh[t] and sh[t + 1] have the same digits, but if thread t stores to sh[t] and loads sh[t + 1], it reads its neighbor's slot while the neighbor may be writing it. Requiring the identical expression rules that out without any arithmetic. Your hash-consing from week 2 makes the check a pointer comparison.

The next lesson explains why reading a neighbor's slot is fine one phase later.