Fixed or moving I/O order?

A design note on how data should enter a submission: which dataflow class the current model already belongs to, what a stream interface would add, and what fixing the I/O order costs and buys in relevance to hardware that can be built today. Companion to the spatial-model analysis and the benchmark report. September 3, 2026.

1. The question

Submissions to the simplified Dally model are currently straight-line programs over 8-bit cells: no loops, no branches, no data-dependent addressing. The grader writes the instance's inputs into cells whose addresses the submission declares on line 1, and energy is the program's static read cost — every operand read of address a costs ⌈√a⌉.

Two things are missing from that picture, and they turn out to be the same question asked twice:

1. How does data enter at scale? Declaring 594 input cells works for an 18×32 parity instance. It does not work for a 47 MB training set, and the scheduled-language RFC (#48) explicitly excludes I/O, leaving data representation as an open fork.
2. Should a submission be allowed to decide what to read next based on what it has already read? Today it may not. The question is whether that restriction should be kept, relaxed, or made a division of the competition.

This note argues that the restriction should be kept as the default, that it is better motivated than it looks, and that the honest way to buy back the relevance it costs is a second, separately-scored division rather than a weakening of the core model.

2. Where the model already sits

A natural interface for streaming data in: the program declares an order of bytes to read and an order of bytes to write; each recv makes the next input byte appear, each send appends to the output; the order is fixed in advance but the timing of each operation is free.

This is frequently described as a Kahn Process Network (KPN) [1]. It is not, and the difference matters. A Kahn process may choose what to read next based on what it has just read. Fixing the order in advance removes exactly that freedom, which places the model one rung lower — and in a strictly more tractable place:

The restriction is load-bearing rather than merely convenient. Buck [6] showed that adding data-dependent routing makes dataflow Turing-complete, and with it boundedness and deadlock become undecidable. Undecidable boundedness means a submission's memory footprint — and therefore its cost — cannot in general be computed without running it. Closed-form scoring, the property that lets the judge cost an 8192³ program in microseconds, is precisely what is lost on the other side of that line.

3. What determinacy buys, and the one prohibition

Kahn's theorem [1] states that the output history of such a network depends only on the input histories, never on the schedule. For an energy benchmark this is the enabling result: a scheduler may reorder work arbitrarily to reduce energy and cannot change the answer. It is what makes "score energy, ignore time" a principled choice rather than an arbitrary one.

Determinacy survives only under one condition, which must be written into the instruction set as a prohibition rather than left as a convention:

4. The interface: two instructions

recv d        # the next byte of the input stream appears in cell d
send s        # the byte in cell s is appended to the output stream

Costs, staying inside the existing "reads are charged" discipline:

• recv d — charge a fixed constant E_in, the off-chip crossing. Deliberately not ⌈√d⌉: physically the price of a fresh sample is the crossing, not the destination.
• send s — charge ⌈√s⌉ as an ordinary operand read, plus a constant E_out.

Four consequences:

• The input declaration line disappears. Submissions are straight-line, so the textual order of recv and send is the declared order. No new syntax is required to specify it.
• Epochs become explicitly priced. To use a sample twice a program must either recv it twice (paying E_in again) or retain it (paying ⌈√a⌉ on every read). Both roads are charged; neither is free; the search chooses. The current model prices neither.
• Static scoring is untouched. The I/O word is fixed, so the added cost is n_recv·E_in + n_send·E_out + Σ⌈√s⌉ — still closed-form, still cross-validatable against the reference evaluator.
• Train/test needs no new concept. The harness owns the stream contents; test labels are simply never in it. Predictions are the sends at positions where labels were withheld.

5. What it changes: the working set stops being free

Under the current rules a submission chooses where its inputs land, so they land near the origin where reads are cheap; all of them are co-present for the whole program; and they may be re-read without limit. Under a stream, a byte arrives once, at a port, and retaining it is priced by the address it is retained at.

That turns a property of the cost function into a binding constraint. Since a read of address a costs ⌈√a⌉, the cells reachable at per-read cost ≤ c are exactly those with a ≤ c²:

No memory hierarchy was assumed; the address-cost function derives one, with an exponent. This also shows where a stream interface does and does not bite:

Holding the MNIST training set resident costs (2/3)(4.70×10⁷)^3/2 ≈ 2.2×10¹¹ cost units per sweep, purely to read it. Re-streaming it each epoch costs 4.70×10⁷·E_in. Resident storage therefore wins if and only if E_in ≳ 4.6×10³. Anchoring E_in in published DRAM-vs-SRAM energy ratios [19][20] rather than choosing it by taste makes the caching question something the benchmark answers instead of assumes.

An aside on feasibility

A recurring objection to a full training task is that writing out its instruction list is prohibitive — a fully-connected MNIST network expands to a trace far beyond what can be stored. That is a statement about the trace, not the algorithm. Two facts follow:

• SGD is oblivious. Its control flow and its addresses are data-independent; only its values depend on data. An SGD training loop is therefore expressible in a straight-line, no-data-dependent-addressing IR, using select for anything branch-like. Training does not require leaving the static class.
• The trace blow-up is what hierarchical schedules remove, by submitting an affine loop nest rather than an unrolled trace.

A scheduled language says how a program is written; a stream says how data enters. They are complementary halves of the same extension.

6. Hardware relevance: the case for a fixed order

If the target is a model that says something true about chips that can be built now, the fixed order is not a simplifying concession — it is the closer match.

• Contemporary GPUs are statically ordered where the energy is. Since Kepler, NVIDIA moved instruction scheduling into the compiler, with control information embedded in the instruction stream; there is no out-of-order execution engine inside a warp. What remains dynamic is which ready warp issues next — interleaving, not reordering. Per-thread instruction order is fixed and execution timing is free, which is exactly the order-fixed/latency-insensitive pair.
• Structured sparsity is the industry's own admission. 2:4 structured sparsity exists because unstructured sparsity's dynamism cannot be made efficient in hardware; the shipped feature is the one that restores static structure.
• The static extreme is buildable and built. TPU-class designs use compiler-managed scratchpads in place of caches [20]; at least one commercial inference architecture is fully deterministic and statically scheduled, and markets that as the differentiator rather than the compromise.
• The software stack is moving toward static, not away. Captured execution graphs, compiled schedule languages in the Halide [17] lineage, and ahead-of-time fused kernels all replace runtime decisions with compile-time ones.
• It matches the cost model's own thesis. The argument for movement-dominated cost models [19] is that fetch, decode and scheduling overhead dwarfs the arithmetic. A benchmark that permits dynamic ordering permits precisely the overhead the cost model exists to indict.

Against the workloads that consume the most accelerator-hours today:

7. The case against, stated honestly

The four rows marked no are where a large share of current deployment energy is actually spent. A fixed-order model has nothing to say about them, and that should be conceded rather than argued around.

The sharper objection is internal to the research question. The largest available energy win in learning may itself be data-dependent. A learner that adapts what it looks at next — active learning, curricula, importance sampling, conditional computation — can reduce sample count by a factor that no amount of locality optimisation will match, and sample count is multiplied by E_in in the cost model above. Locality is a static property and fixing the order does not cap that win; sample-adaptivity is not, and fixing the order does cap it. A benchmark that forbids adaptivity risks returning a confident answer to "what is the most energy-efficient way to learn this task" that is wrong in the direction that matters most.

8. The scoring cliff

The choice is not binary. There are six rungs, and the property that matters — whether cost can be computed without executing the submission on data — breaks at one specific place:

Rungs (a) through (d) all preserve O(1) judging. Rung (d) is already enough to express mixture-of-experts routing with a capacity factor, which is the most commercially relevant data-dependent behaviour there is. The cliff is between (d) and (e), not between "static" and "dynamic".

9. Recommendation

1. Keep the order fixed in the main competition, and state the reason as decidability rather than simplicity.
2. Adopt a closed/open division split. A closed division with fixed order, closed-form scoring, comparable numbers and no execution of submitted code; an open division where order may move, scored by simulation at small scale, explicitly labelled as not comparable and expensive to judge. This is the established resolution of exactly this tension in machine-learning benchmarking, it costs one paragraph of rules, and it removes the need to litigate each new dynamic strategy as it appears.
3. Reserve syntax for rung (d) now, implement it later. A mode or guard construct that is specified but unimplemented means adding conditional computation later is an extension rather than a redesign.
4. Let the harness permute the stream. Real training shuffles each epoch; a harness-chosen permutation is not adaptivity, costs nothing to allow, and defends against submissions that index by position and memorise a fixed order.

A useful side effect of pricing rather than prohibiting: retention and re-reading move from policy to price. A priced strategy is not a reward hack, which shrinks the subjective surface of adjudication without changing rules mid-competition.

10. Open questions

1. Port-fixed or program-named arrival address? Letting the program name the destination is friendlier; a fixed port cell is physically honest and forces an explicit, chargeable copy. The latter is the difference between modelling a pad and modelling a wish.
2. Online or transductive? Because the submission declares the order, it may recv every test input before emitting any label. That is legitimate transduction but a different problem. Requiring the label send for example i before the recv of example i+1 makes it online, and brings regret bounds in as a second source of provable limits.
3. What is E_in? Section 5 shows it decides the winning strategy; it should be derived from published memory-energy figures at a stated process node.
4. Nothing rewards parallelism. Order-fixed, time-free, energy-only scoring never penalises an arbitrarily serial submission — an odd property for a benchmark about a spatial machine. A static schedule yields the critical path for free; reporting makespan as an unscored second axis is the cheap fix.
5. Lower bounds as the normaliser. Scores are more legible against a proven floor than in isolation: red-blue pebbling [11] for the I/O complexity of dense linear algebra, and memory-versus-samples bounds for streaming parity learning [13][14]. The constants in the sparse-k regime differ from the dense case and should be checked before being quoted.

11. References

1. G. Kahn, "The semantics of a simple language for parallel programming," IFIP Congress, 1974.
2. G. Kahn and D. MacQueen, "Coroutines and networks of parallel processes," IFIP, 1977.
3. J. B. Dennis, "First version of a data flow procedure language," Symposium on Programming, 1974.
4. E. A. Lee and D. G. Messerschmitt, "Synchronous data flow," Proc. IEEE 75(9), 1987.
5. G. Bilsen, M. Engels, R. Lauwereins, J. Peperstraete, "Cyclo-static dataflow," IEEE Trans. Signal Processing, 1996.
6. J. T. Buck, "Scheduling dynamic dataflow graphs with bounded memory using the token flow model," PhD thesis, UC Berkeley, 1993.
7. E. A. Lee and T. M. Parks, "Dataflow process networks," Proc. IEEE 83(5), 1995.
8. T. M. Parks, "Bounded scheduling of process networks," PhD thesis, UC Berkeley, 1995.
9. J. D. Brock and W. B. Ackerman, "Scenarios: a model of non-determinate computation," Formalization of Programming Concepts, 1981.
10. L. Carloni, K. McMillan, A. Sangiovanni-Vincentelli, "Theory of latency-insensitive design," IEEE TCAD 20(9), 2001.
11. J.-W. Hong and H. T. Kung, "I/O complexity: the red-blue pebble game," STOC, 1981.
12. H. T. Kung and C. E. Leiserson, "Systolic arrays for VLSI," 1978/79.
13. R. Raz, "Fast learning requires good memory: a time-space lower bound for parity learning," FOCS, 2016.
14. G. Kol, R. Raz, A. Tal, "Time-space hardness of learning sparse parities," STOC, 2017.
15. S. Garg, R. Raz, A. Tal, "Extractor-based time-space lower bounds for learning," STOC, 2018.
16. W. Thies, M. Karczmarek, S. Amarasinghe, "StreamIt: a language for streaming applications," CC, 2002.
17. J. Ragan-Kelley et al., "Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines," PLDI, 2013.
18. D. Koeplinger et al., "Spatial: a language and compiler for application accelerators," PLDI, 2018.
19. W. J. Dally, "On the model of computation: point," Communications of the ACM 65(9), 2022.
20. N. Jouppi et al., "Ten lessons from three generations that shaped Google's TPUv4i," ISCA, 2021.
21. Ptolemy II, UC Berkeley — reference implementations of the models of computation above, side by side.