Week 7 · Lesson 5
Kernels and outlining: rendering a thread loop
A thread loop can't stay a for loop in C. Its body has to become a function that a thread can call. Moving a block of code into its own function is called outlining, and the hard part is everything the block uses from outside it.
Kernels
A kernel is a loop nest that runs as one unit: the code between one materialization and the next. Week 4's rangeify already produces them: each stage, each store of a whole value, becomes its own loop nest at the top of the C function. Fusing ops puts more work in one kernel. Materializing splits it.
On a CPU, kernels run one after another. Threads split one kernel's outer loop across cores. On a GPU, which the course reaches next week, each kernel is a separate launch. The thread loop you render this week is the same idea at a smaller scale: hand one loop's iterations to many workers.
Outlining
To run iteration r of a thread loop on another thread, the body becomes a function body(r, ctx). The harness provides one function that runs it:
void uir_parallel_for(int32_t n, void (*body)(int32_t, void *), void *ctx);It calls body(r, ctx) once for every r in 0 .. n-1, spread across threads, and returns when all are done. ctx is whatever pointer you pass: your way of getting values into the function.
What does the body need from outside? The names it uses but doesn't define: buffer pointers, values computed before the loop, and the counters of enclosing loops. Finding them is closure conversion: collect every name the body uses, remove the ones it defines and the loop variable itself, and what's left goes in a struct. Private allocs aren't in the struct. They're declared inside the function, so each call gets its own zeros.
Here is the reference compiler's C for the threaded row sum from the tests, out[r] = sum of row r:
void uir_parallel_for(int32_t n, void (*body)(int32_t, void *), void *ctx);
typedef struct { int32_t *b0; int32_t *b1; } thread0_ctx;
static void thread0(int32_t r5, void *ctx) {
thread0_ctx *k_ = ctx;
int32_t *restrict b0 = k_->b0;
int32_t *restrict b1 = k_->b1;
b1[r5] = 0;
int32_t v10 = (int32_t)((uint32_t)r5 * (uint32_t)3);
for (int32_t r11 = 0; r11 < 3; r11++) {
int32_t v12 = b1[r5];
int32_t v13 = (int32_t)((uint32_t)v10 + (uint32_t)r11);
int32_t v15 = b0[v13];
int32_t v16 = (int32_t)((uint32_t)v12 + (uint32_t)v15);
b1[r5] = v16;
}
}
void kernel(int32_t *restrict b0, int32_t *restrict b1) {
{ thread0_ctx k_ = { b0, b1 }; uir_parallel_for(4, thread0, &k_); }
}The loop variable r5 is the function's argument. The two buffers it uses travel in thread0_ctx. Everything the body defines (v10 to v16, the inner loop) stays inside. In the GEMM, the struct holds just the three buffers: the tile's accumulators are a private alloc, declared in the function.
restrict
Buffers never alias in .uir, but C doesn't know that. When a kernel writes through one pointer and reads through another, the C compiler must assume the write might change what the read sees, so it reloads after every store. Declaring the pointers restrict promises they don't overlap. The compiler can then keep loaded values in registers across stores, and that matters in tight loops. The harness's prototype for kernel doesn't say restrict, and that's fine: qualifiers on parameters don't change a function's type.
What the thread body needs
Given a body as a list of (name, uses) statements, return the names it uses but doesn't define (other than its loop variable): the fields of the context struct.
Render the body into a separate list of lines with your normal emitter, record the names it declares as it goes, then scan the lines for the names they reference. Uses minus declarations minus the loop variable is the struct. Keep a map from every name you emit to its C type, so you can declare the struct's fields.
Check yourself
Which of these goes in the thread body's context struct?
Which names does the body use without defining?
Values from before the loop (and buffer pointers, and enclosing loop counters) come from outside. Private allocs are declared inside the function so each call gets fresh zeros.
A thread loop sits inside a plain loop over p, and its body uses p. How does the body get p?
The function's argument is the thread loop's own counter.
The outer counter is a free variable of the body. The struct is filled just before each uir_parallel_for call, so every pass of the outer loop passes its own p. The test r_thread_captures_values does exactly this.
What does restrict on the kernel's buffer pointers let the C compiler do?
What must the compiler assume about two pointers without it?
Without it, any store might alias any load, so the compiler reloads values after every store. .uir buffers never overlap, so the promise is true.
Starting threads costs tens of microseconds. Which loop should you thread?
How many times would an inner thread loop start its threads?
A thread loop inside other loops starts its threads once per outer iteration. Threading the outermost allowed loop pays that cost once, for the most work.