I keep thinking of a combine harvester. Material goes in, passes through several operations and comes out processed. Keep feeding it and let it get on with the job.
Then I imagine stopping between every stage. Empty everything into a barn, fetch it again, feed it through the next bit.... We've separated the jobs very neatly, but now we're spending our time carrying the crop around. Why would I want to build that?
And then there's a rock. Stop the machine, fish it out, get everything moving again. I've no idea whether a real combine needs to stop for this.
Mine does, apparently. That would be a long day.
That's how I picture Floatyboat, the array language I'm building. Keep the calculation fed. I'm getting quite attached to this harvester, which is making me suspicious of anything that wants to stop it.
The Cray-1 keeps coming to mind
The Cray-1 intrigues me too. It was a 1970s supercomputer with vector registers, which held sequences of numbers. A vector operation fed successive elements through a pipelined arithmetic unit, so more elements could enter the unit while the ones ahead of them were still being processed.
Its chaining mechanism let another vector operation consume results as they arrived. It could pass values through successive operations without a trip to main memory between them or waiting for the preceding vector operation to produce all its results.
I like thinking about the organisation of that work. Once the calculation is going, how do we keep the next operation fed?
Could I build a language around that instinct for an ordinary desktop? Giving the compiler the whole calculation could let it arrange that work before execution.
How much fits in the harvester?
The width of my harvester is how much data it can work on side by side in one step. That's one strip. I picture a tile as the length of crop moving through the machine, a chunk containing several strips. A scalar operation handles one value. One blade of grain for this whole combine. While one tile is finishing I can start feeding another, reusing workspace as earlier values stop being needed. If I can read the input in segments and write the output as I go, I don't need the entire dataset in RAM. Keeping the tiles small enough can also let the working data stay in the CPU's cache, its small, fast memory.
Count the bytes in both arrangements
Suppose each stage reads one array and writes another, with one arithmetic operation per element. Ignore caches and other overhead for this first model.
A million eight-byte elements make an 8 MB array. One stage reads 8 MB and writes 8 MB. That's 16 MB of traffic. Storing each result in an array is called materialisation. Do it at all three stages and I have 48 MB of traffic.
Combining the stages into a single loop is called fusion. The loop reads one input element, performs all three operations while keeping their intermediate values local, and writes the final element. Across the array, that is one 8 MB read and one 8 MB write:
| Three stages, one million elements | Arithmetic operations | Array bytes moved |
|---|---|---|
| Materialise each stage | 3 million | 48 MB |
| Fuse the stages | 3 million | 16 MB |
Both arrangements still do three million arithmetic operations. How much work per byte? One operation per sixteen bytes becomes three operations per sixteen bytes. Those are 0.0625 and 0.1875 operations per byte. That ratio is called arithmetic intensity.
Another materialised stage adds arithmetic and traffic together, leaving the ratio unchanged in this model. Keeping its intermediate in the loop saves unloading a million answers only to pick them up again. The arithmetic is still there, but I've stopped carrying quite so much crop around.
Real caches can retain intermediate arrays, so only a measurement can say whether this traffic actually reaches physical memory.
Those missing array transfers are what I'd look for in the generated loop before reaching for the stopwatch.
Keep the stages, change their storage
The input and final output can still be full arrays in memory. I'm trying to avoid a full intermediate array for every stage. A later operation that needs all the intermediate values would undo that arrangement halfway through.
That's the instinct behind Floatyboat's dataflow code. Named stages help me read the calculation. Giving every name an array that is written and immediately read back is a steep price for that readability.
Suppose the readings arrive in Fahrenheit and I want Celsius. First remove the 32-degree offset, then scale the result:
shifted = readings - 32.0
celsius = shifted * 5.0 / 9.0
Because each stage works on one element at a time, a compiler can turn the chain into one loop while keeping the intermediate values local. The shifted array then needs no separate storage if nothing else observes it.
Who else wants the shifted readings? If another consumer needs all the shifted readings later, I have to preserve that use, duplicate work the language permits, or choose another schedule. This is where the readers in the graph matter. They tell me whether that array really is mine to remove.
shifted tells me we've removed the offset, even without an array behind the name. Hand-combining everything into one long expression would save the compiler a job and leave me squinting at the source. Finding a safe one-pass calculation is the compiler's work.
Getting the stages fused is only the beginning. Suppose I put a conditional between them and the compiler can only generate whole-array code for it, which means collecting every tile's values before that operation can run.
The preceding stage now writes the values from all its tiles into a full intermediate array, which the conditional reads before later stages can start processing tiles again. All the intermediate values are back in memory. Fused work can remain on either side, but the continuous route between them is gone. There's my rock.
I'm back to unloading the machine because one part can't accept what's coming through.
What happens when the work wants different paths?
So does every choice mean unloading the machine? A conditional can also stay inside a vectorised loop, keeping its work with the tile. That's the route I'm interested in finding.
A desktop CPU can predict a branch and start work early, discarding it if the guess was wrong, without requiring an array to be materialised. SIMD lets one instruction work on several values. Each has a position, called a lane. Mixed choices need a way to handle different work within that group.
NVIDIA GPUs have a related problem called control-flow divergence. Threads run in groups called warps, and if they choose different paths those paths can run in turn with only the relevant threads active. Either way, choosing different work can leave some of the machine waiting.
What if I do extra arithmetic? Suppose I want to double a non-negative input, otherwise add one. The condition gives each position a yes or no, which we can collect into a mask:
| Input | Keep 2*x? | 2*x | x+1 | Result |
|---|---|---|---|---|
| -2 | No | -4 | -1 | -1 |
| 3 | Yes | 6 | 4 | 6 |
| -1 | No | -2 | 0 | 0 |
| 4 | Yes | 8 | 5 | 8 |
Calculate both, then choose. We do the same operations for all four inputs and throw away some of the answers. Keeping the candidates and mask local to the tile lets a later stage use the selected values without collecting a full array. Hardware masking can instead control which lanes an instruction updates without always calculating both candidates, though removing the branch has costs either way because extra arithmetic and dependencies can lose to a well-predicted branch. I find this slightly irritating. Carefully avoiding a multiply sounds sensible, until choosing what to avoid becomes the expensive part and I'd happily spend a few cheap calculations to keep useful work moving.
Then I start weighing up the extra arithmetic and the dependencies and the branch prediction. A long calculation in each arm would give me a different bill.
Some stages change the schedule
A sum combines its input values. That is a reduction. If a later stage needs the result, it may have to wait for the reduction to finish before it can process its own elements. Filtering changes the number of output elements. Both ask more of the schedule than a chain of independent elementwise operations.
Floating-point arithmetic also gives the compiler an ordering obligation. Keeping the per-element calculation intact is different from regrouping a reduction. Changing the grouping can change the answer, so the language has to define which transformations it permits.
Floatyboat's restrictions are meant to give the compiler enough information to arrange this before execution, while preserving the calculation's answer. Following the readers can reveal an unnecessary array, and knowing which choices apply to a whole group can reveal work that stays together.
Coming back to the source, I can still read where the offset comes out and the units change. Those names can stay. It's the unloading between them I'm trying to avoid, including the rock halfway through that would put all those intermediate values back into memory.