Week 7 study guide

Week 7 is about speed on a CPU. A range can say how its loop runs: as a plain loop, unrolled into registers, or spread across threads. None of it changes a bit of any result, and from this week some tests time your kernels against the reference's. This page recaps the week, collects the rules worth memorizing, and walks the lab one step at a time.

The week in one page

7.1 Measuring speed

Speed is FLOPs per second. A kernel is limited by compute or by memory, depending on its arithmetic intensity, FLOPs per byte moved. That's the roofline. Time the kernel alone, take the best of several runs, and compare on the same machine.

7.2 Caches and tiling

Memory moves in 64-byte lines through several levels of cache. A 4×8 tile of a GEMM loads 12 values per k for 32 multiply-adds, instead of 64. Each output keeps its own sum in its own order, so tiling never changes bits. Start each tile from its first product, so the start depends on the tile indices and runs once per tile.

7.3 Upcast

axis=upcast unrolls a loop in the rendered C. Its bound is a literal from 1 to 32. With literal indices, a small alloc becomes plain variables in registers, and adjacent outputs can share SIMD instructions without changing any rounding.

7.4 Threads

axis=thread lets iterations run at once. No nesting. Every store, and every load of memory the loop writes, must be at r·S + e with 0 ≤ e, e + size ≤ S, one S per buffer. Read-only memory is free. An alloc used only inside the loop is private and starts at zero in every iteration.

7.5 Kernels and outlining

A thread loop's body becomes a function called through uir_parallel_for. Its free names (buffers, earlier values, outer counters) go in a context struct, which is closure conversion. Private allocs are declared inside it. restrict lets the C compiler keep values in registers.

7.6 Lab

The suite has 41 tests, three of them speed tests on a 768×768 GEMM, which need 0.5 or 0.65 of the reference's speed. Weeks 1 to 6 must stay green.

Cheat sheet

Mistakes people make

Each of these is a bug that was planted in the reference compiler to prove the suite catches it. The week 7 test guide lists every test with the bugs known to fail it.

1. Rendering thread loops as plain loops. Correct, and far too slow. Caught by s_gemm_768_threads and s_gemm_768_threads_and_upcast.
2. Rendering upcast loops as plain loops. The accumulators stay in memory. Caught by s_gemm_768_upcast and s_gemm_768_threads_and_upcast.
3. Unrolling one copy short. Caught by r_upcast_sum_order and the r_gemm_tiled_* tests.
4. Forgetting that private allocs start at zero. In run, caught by thread_private_alloc_fresh. In render, a shared array is caught by r_thread_private_alloc and the threaded speed tests.
5. Checking a slice without the access size. A vector store can spill into the next slice. Caught by err_thread_vector_store_overflows.
6. Checking only stores. A load of a neighbor's element races too. Caught by err_thread_load_neighbor.
7. Allowing nested thread loops, or two strides on one buffer. Caught by err_thread_nested and err_thread_mixed_strides.
8. Accepting any upcast bound. Caught by err_upcast_not_literal, err_upcast_too_big and err_upcast_zero.

Stuck on the lab?

Build in this order, and don't move on until the check passes.

1. Axes as plain loops. Parse and validate axis=, then ignore it. Every week 7 render test except r_thread_private_alloc already passes with correct bits. The speed tests, the thread rules and the private-alloc tests fail.
2. The slice rule. Flatten the offset's adds into terms, find the one term with the thread range, and bound the others. Done when every err_thread_* test exits 2 and thread_store_own_slice runs.
3. Private allocs in run. Done when this program's buffer is 0 1 2 3 (and 0 1 3 6 without axis=thread):

   %o = buffer 4 dtype=i32 slot=0
   %acc = alloc 1 dtype=i32
   %r = range 4 axis=thread
   %a = shrink %acc 0 shape=[]
   %cur = load %a
   %n = add %cur %r
   %st = store %a %n
   %acc1 = after %acc %st
   %a1 = shrink %acc1 0 shape=[]
   %got = load %a1
   %ov = shrink %o %r shape=[]
   %so = store %ov %got
   %e = end %st %so %r
   %o1 = after %o %e

4. Upcast in the renderer. Copy the body per value. Done when s_gemm_768_upcast passes.
5. Outlining. Done when r_thread_captures_values passes, then the threaded speed tests.

Check yourself