Week 4 · Lesson 5
Rendering vectors
After rangeify, your renderer is printing a week 3 program, so most of this lesson is about what the output should look like and how to check it. The short version: one loop per rank-1 store, one per reduce, scalars computed once between them, and the whole kernel around a kilobyte no matter how long the vectors are.
Why unrolling fails
Week 2's renderer handled a rank-1 value by keeping it as a C array and spelling out every element: {b0[0 + 0], b0[0 + 1], ...}. For four elements that's fine. Week 4's render tests use vectors of 4096 floats, and the grader rejects any rendered C over 20,000 bytes, before it even tries to compile it.
Count it out for x / sum(x) on 4096 floats. The store alone, unrolled, is one line per element, about 30 bytes each: roughly 125,000 bytes, six times the limit, before the reduce or any loads. The rangeified version is about 800 bytes in total (801 with the current oracle), headers and helper included. Make the vectors a million long and it's the same size plus a few more digits in the loop bounds.
The shape of the output
Three rules cover almost every week 4 kernel:
- Every rank-1 store is a loop over the vector's length. Its body computes the element at the loop index, all the way down through the elementwise ops, and stores it.
- Every reduce is an accumulator loop: seed with the element at 0, fold in elements 1 to n-1. If two reduces read the same vector, that's two loops (lesson 4.4).
- Scalars live between loops. The reduce's result, its reciprocal, anything computed from scalars alone, has no open range, so week 3's placement puts it in the outer block, once. In the kernel above,
1.0f / v23runs one time, not 4096 times.
An expand leaves no trace in the C at all: its element at any index is the scalar, so the store loop just uses v24 directly.
You don't need a separate pass to hoist the reciprocal out of the store loop. It never had the store loop's range in the first place: rangeify asked the expand for its element at i, and the answer was a node with no ranges at all. Placement by open ranges does the rest.
The normalize loop pair
Write void normalize(const float *x, float *y, int n) (n ≥ 1) so that it computes exactly what the oracle's kernel computes for store %y (mul %v (expand (recip (reduce %v op=add)))): fold the sum left to right from x[0], compute the reciprocal once as 1.0f / sum, then multiply each element by it. Results are compared bit for bit.
Check your output size
The grader measures your render output in bytes, as UTF-8, and checks the limit before anything else. Measure it yourself on the big tests:
C:/path/to/your.exe render tests/week4/render/normalize_4096.uir | wc -c(That's Git Bash, and wc -c counts bytes.) If the number grows when you double the vector length, something is still unrolled. The usual culprits are a rank-1 value that reaches the printer without going through rangeify, and a vector constant built element by element instead of with expand.
A renderer that unrolls passes every test with four-element vectors, and the bits come out right. Only the large render tests hit the 20,000-byte limit. Run them early, not just before you submit.
Will it fit in 20,000 bytes?
Write int fits(int n, int per_elem, int fixed): 1 if n * per_elem + fixed <= 20000, else 0. All three are non-negative ints, but the product may not fit in an int.
Check yourself
Roughly how big is the oracle's rendered C for x / sum(x) on 4096 floats, headers included?
It's in the lesson, and it doesn't depend on 4096.
About 800 bytes (801 with the current oracle). Two loops and a few scalar lines. The vector length only appears as the loop bounds 4095 and 4096. 125,000 bytes is what the unrolled store alone would cost.
In that kernel, how many times does 1.0f / v23 run?
Which ranges does the reciprocal depend on?
None. It's computed from the reduce's result, a scalar, so placement puts it in the outer block, after the reduce loop and before the store loop.
How many iterations does that kernel's store loop run?
Unlike the reduce, the store has no seed element.
4096: one iteration per element of y. The reduce loop runs 4095, because element 0 seeds the accumulator.
Your renderer still unrolls rank-1 values. What does the grader report on a 4096-element render test?
Which check runs first?
The size check runs right after render exits, before the loop check and before compiling. Unrolled code may well be correct, but it's too big.
What does an expand turn into in the rendered C?
What is the element at i of a broadcast?
Its element at any index is the scalar itself, so rangeify replaces the expand with the scalar node and nothing is materialized.
You double every vector in a program from 4096 to 8192 elements. How does a correctly rangeified kernel's size change?
Where does n appear in the C?
n appears only as loop bounds (and buffer sizes the harness owns), so the kernel stays the same length give or take a digit. That's what the size limit checks for.