Threads: iterations at the same time

axis=thread

%ib = range 192 axis=thread

Iterations of a thread loop may run in any order, at the same time. run still executes them in order, one after another. The program must be written so that the order doesn't matter, and the spec checks that statically.

What goes wrong: a race

Suppose two iterations both do o[0] = o[0] + 1 at the same time. Each loads o[0], say 5, adds 1, and stores 6. One increment is lost, and which one depends on timing. This is a race. Its result can change from run to run, and the bit-exact grader would catch it only sometimes. So the spec forbids it outright.

The slice rule

Each iteration r gets its own slice of memory: elements r·S to r·S + S - 1. Every store in the loop, and every load of memory the loop also stores into, must be at a flat offset of the form

r * S + e        S a literal (a bare r means S = 1), r in exactly one term,
                 e doesn't depend on r, and 0 <= e, e + size <= S

Your week 1 bounds analysis proves the part about e. Every access to one buffer in the loop uses the same S. Memory the loop only reads, like the A and B of a GEMM, may be read anywhere: two threads reading the same float is no problem.

The check looks at the shape of the offset, not its value. (r·2)·4 equals r·8 but isn't in the form, so it's rejected. Write offsets expanded: in the GEMM, C's offset (4ib + wi)·N + 8jb + wj is written as ib·(4N) + wi·N + jb·8 + wj, with e = wi·N + jb·8 + wj in [0, 4N - 1].

Private allocs

The GEMM's 32 accumulators are an alloc used only inside the thread loop. Shared between threads, they'd race. So the spec makes them private: an alloc whose every load and store is inside one thread loop gets a fresh copy, all zeros, at the start of every iteration. In C that's simply an array declared inside the thread's function.

That's a real semantic difference, and run implements it too. In a plain loop an alloc keeps its contents from one iteration to the next, so an accumulator keeps a running total. In a thread loop each iteration starts from zero. The tests loop_alloc_carries_over and thread_private_alloc_fresh run the same program both ways and get different answers.

How the iterations are split

The harness gives each hardware thread one contiguous chunk of iterations: with 192 iterations on 8 threads, thread 0 runs 0 to 23, thread 1 runs 24 to 47, and so on. Contiguous chunks mean each thread writes one block of memory, so two threads rarely touch the same cache line. When they do, the line bounces between cores, which is slow even without a race. That's called false sharing.

What to thread, and what it's worth

Thread the outermost loop that the slice rule allows: each thread then gets plenty of work per iteration. Starting threads costs tens of microseconds, so a thread loop around a tiny body is slower than a plain loop. Only one level may be threaded. A thread loop inside another is invalid, but a thread loop inside a plain loop is fine.

On the 768×768 GEMM with 24 hardware threads, threading the 192 row blocks gave about 8× on its own (98 ms to 12 ms with clang), and about 15 to 30× together with upcast. It's not 24×, because threads share the memory bus and the L3 cache, and some cores are slower than others. The speed tests with thread loops ask for half the reference's speed. A renderer that runs thread loops one iteration at a time lands around 0.13 and fails.