Flow Loss Analysis

Flow loss is the data-flow parallelism a program contains that a CPU has to serialize when it runs. Because a Clef program’s data-flow structure is carried directly in the graph, and the control-flow lowering to a CPU is one derived reading of it, the parallelism a control-flow architecture gives up relative to spatial hardware is a delta visible directly in the graph-native representation rather than one a profiler reconstructs after the fact. We have found no representative implementation of this comparison in the standing literature we have reviewed. A conventional control-flow language must first recover a data-flow graph from imperative code before the comparison is even possible.

The Program Semantic Graph (PSG) retains source dependencies and the premises that justify an admitted parallel execution regime. Composer’s backend realizes that settled structure for a target, including any permitted sequential, SIMD or concurrent execution. Flow loss compares justified parallel potential with the selected realization. Alex contributes passive portable witnessing, without discovering dependencies or scheduling target work.

The Delta Between Two Representations

CCS/Baker establish the effects, demand, dependencies and joint premises used to settle a region’s execution regime, as described in the DCont/Inet duality. Sequential regions carry continuation aggregates; admitted independent regions carry tensor structure or interaction-net rules according to their contracts. Confluence requires the applicable rule-system argument and does not follow from purity alone. Alex passively witnesses the published settlement; it neither classifies the region nor selects its semantic regime.

The proposed comparison relates the parallel potential justified on the PSG to Composer’s backend realization for a CPU. Alex supplies portable witnessing between those boundaries. The flow-loss metric and examples below describe the analysis design; they do not establish implemented analysis coverage or measured performance.

Two Axes: Compute and Memory Movement

Flow loss has two orthogonal axes. The first is the compute delta: the work W and the span S, the data-flow parallelism the control-flow lowering forgoes. This is the span-versus-work measure, and it is the territory of Brent’s 1974 bound, which relates the time on a finite number of processors to W and S. The second axis is memory movement: the cost of moving data that a control-flow target pays and a spatial substrate does not.

Brent’s bound counts compute alone: operations and dependency depth, with data movement priced at zero. The work-and-span axis on its own therefore cannot state the full cost a substrate imposes, because it has no term for where data lives or what it costs to feed the computation.

The two axes are separable, and a single example shows why. A discrete GPU and a unified-memory APU hold the same W and the same S: identical compute parallelism over the same operation count. They split only on what it costs to feed them. The discrete GPU pays a transfer cost to stage data across its own memory boundary. The unified-memory APU shares memory with the host and pays none. To the compute axis the two architectures are equal, and their difference shows up only on the memory axis. That is why memory movement is a separate axis rather than another compute metric.

The von Neumann model behaves as a gradient rather than a binary transition. A substrate does not sit inside or outside it; it sits somewhere along it, at a distance set by how far data lives from the unit that computes on it. Main memory behind a bus is the far end. A cache hierarchy sits closer, unified memory closer still, and tile-local memory on an NPU or CGRA closer again. An FPGA, where the computation is the circuit, is the near end, where the separation approaches zero. The two axes are the two faces of where a substrate sits on that gradient. The memory axis reads the separation directly, as the cost of feeding the computation. The compute axis reflects how much parallelism the substrate admits, set by how little separation it imposes. Flow loss measures position on that gradient from both sides.

Our coeffect system reads memory residency and access patterns off the same PSG the compute term is read from. Residency and access shape are properties the graph already carries, so the memory term is ours to compute alongside the work-and-span term on one graph rather than through a separate analysis. Escape classification is a working compiler pass and supplies the part of this that already exists; the broader coeffect-driven memory optimization is still in design. The formalization of escape classes and their allocation strategies is described in memory safety as coeffect algebra.

A full formal treatment of flow loss carries both axes, the compute delta and the memory term together, and reaches past Brent’s compute-only bound. Formalizing the two axes as one model is design-stage work the flow-loss pass would take on as the pass itself comes into place.

Metrics

The metrics below divide across the two axes. Parallelism ratio, critical path against total work, and serialization points read the compute axis. Memory movement overhead reads the memory axis. Substrate comparison estimates combine both.

Parallelism Ratio

How many operations could fire at once on a data-flow fabric against how many the CPU visits in sequence. A function with two hundred independent operations collapsed onto one thread reads very differently from a function whose work is a deep dependency chain. The ratio gives a direct sense of how much a region stands to gain from spatial hardware before any code is moved.

Critical Path Against Total Work

The longest dependency chain against the total operation count. This is the standard span-versus-work measure from parallel computing. A ratio near 1.0 means the computation is inherently sequential and little is lost to a CPU. A ratio near 0.01 means roughly ninety-nine percent of the work could run concurrently on a spatial architecture. The critical path length also sets the floor on a data-flow fabric: it is the minimum depth the computation cannot collapse, the longest chain of dependencies that has to resolve in order. A substrate-specific cycle estimate is derived from that floor.

Critical-path length comes from a walk of the PSG dependency edges, where the longest chain of dependent nodes is the path. That walk is the primary mechanism, and it rests only on structure the PSG already carries. A height-typed incremental DAG, a construct we are designing as part of the broader incremental-compilation direction, would give the same figure directly without re-walking, since its height counts that same longest chain. The walk is what flow loss reads today; the typed-height shortcut is an optimization from that direction.

Serialization Points

Source locations where the lowering introduced an ordering the data-flow graph does not require. Each one can be annotated with the count of independent operations that were placed in sequence, which gives a concrete target for anyone restructuring a hot region for spatial hardware. These are informational, not errors. A serialization point on a CPU build is the expected outcome of running data-flow work on a control-flow machine.

Memory Movement Overhead

Data that would stay local to a processing element on a spatial architecture but has to traverse the cache hierarchy on a CPU. The dimensional types are what would make this quantifiable: memory space and access pattern are explicit, so a streaming access that would be a zero-cost channel on a CGRA can be distinguished from a cache-dependent load on a CPU at the type level. Our coeffect system already tracks these access patterns at compile time, and the escape classification it rests on is a working compiler pass, so this metric reuses information the pipeline computes for other reasons rather than introducing a new analysis. The formalization of escape classes and their allocation strategies is described in memory safety as coeffect algebra.

Substrate Comparison Estimates

Given an admitted target cost model, the delta can be expressed in estimated units rather than ratios. Vendor timing data can inform that model. The comparison must relate the settled graph and Composer’s backend realizations; Alex does not perform cost inference or target scheduling.

  flowchart LR
    subgraph compare["Two readings of: sensors |> Array.map calibrate"]
        psg["PSG region<br/>App(Array.map, Lambda(calibrate))"]

        subgraph readings["Same computation, two readings"]
            ideal["Interaction net (ideal)<br/>128 independent reduce nodes<br/>critical path: 1 step"]
            actual["Composer backend CPU realization<br/>128 sequential iterations<br/>critical path: 128 steps"]
        end

        delta["Flow loss: 127 of 128 operations serialized<br/>(substrate estimate depends on the vendor cost model)"]

        psg --> readings --> delta
    end

The reading labelled ideal is the admitted interaction-net potential the PSG exposes. The reading labelled serial is Composer’s backend CPU realization.

Where the Inputs Come From

Flow loss rests on infrastructure that partly exists and is partly designed. Each input below is marked as operational today or design-stage.

• Our PSG supplies the data-flow graph: node count, edge structure, and the dependency chains the ratios are computed over. This is real and is what Alex witnesses today.
• The interaction-net representation supplies the ideal parallel reading for pure regions. The representation is real for that lane; confluence is what makes the all-at-once reading sound.
• The PSG dependency edges supply critical-path length: the longest chain through them is the path, and the walk needs nothing the graph does not already carry. A height-typed incremental DAG would supply the same figure without re-walking, but that construct is part of the incremental-compilation direction still in design, so the walk is the mechanism flow loss reads today.
• Escape analysis and our coeffect system supply the memory-movement information. Escape classification is a working pass; the broader coeffect-driven memory optimizations are still in design.
• Composer’s backend CPU output supplies the realized instruction sequence for the comparison.

The flow loss computation compares the interaction net’s reduction potential against the CPU’s instruction stream. Both readings live inside the same compilation pipeline, so the comparison runs as a pipeline operation rather than a separate tool that has to rebuild the graph from machine code.

What the Analysis Points At

The spatial hardware where the serialized parallelism would be recovered is real for two targets. Our compiler lowers natively to the FPGA through CIRCT and to the NPU through MLIR-AIE, shown in HelloArty and HelloNappy; the FPGA path is covered end to end in FPGA and hardware inference, down to bit-width reduction and post-route timing. On those targets the operations a CPU sequences run in parallel across the fabric, which is the gain flow loss quantifies.

Other architectures are prospective targets the analysis is designed to inform rather than results we show. A RISC-V mesh such as Tenstorrent’s Wormhole, a runtime-reconfigurable dataflow part such as NextSilicon’s Maverick, and wafer-scale spatial designs such as Cerebras each exploit data-flow parallelism that a CPU serializes, and the target-architectures compilation strategy sets out how their cost models would slot into the comparison. The CPU is not deficient here. It is a control-flow architecture, and the serialization cost flow loss reports is the price of running data-flow work on a machine built to step through one instruction at a time.

None of this requires the CPU to be the wrong choice. A region with a parallelism ratio near 1.0 is inherently sequential, and flow loss confirms that the CPU lowering gives up nothing. The metric is as useful for ruling spatial hardware out of a region as for arguing it in.

A Note on Surfacing

These numbers are meant to be read where code is written. Our Atelier workshop is the environment that would render flow loss over the PSG view and inline at serialization points, which is its own subject; the analysis described here is the compiler capability meant to produce the numbers, independent of how any editor draws them.

The direction we are building toward is a compiler that holds the ideal parallel form and the serial lowering side by side and tells you the distance between them, so that the cost a control-flow target imposes is a figure you can read off the graph rather than a property you infer from a benchmark after the run. That comparison reads straight off the graph-native representation, and extending it from the pure interaction-net lane across the rest of the lowering paths is the work we will continue as the rest of the Composer compiler is built.