A Data-Driven Dynamic Execution Orchestration Architecture

Zhenyu Bai, Pranav Dangi, Rohan Juneja, Zhaoying Li, Zhanglu Yan, Huiying Lan and 1 other

A chip can orchestrate its datapath — decide when each unit computes and how data moves — at one of two times, and each choice has a fatal weakness. A domain-specific accelerator wires the datapath at fabrication time for peak efficiency on one workload but collapses (below a third of its speed) on a new or irregular kernel, while programmable fabrics like FPGAs, CGRAs, and GPUs fix their schedule at compile time and are flexible but slow on irregular or sparse data; this paper (National University of Singapore — Zhenyu Bai, Tulika Mitra, and colleagues) presents Canon, a spatial array that adds a third option — runtime, data-driven orchestration — using per-element programmable state machines that turn incoming data metadata into the right instructions, plus a time-lapsed execution model that staggers one instruction down a row of processing elements, so it matches specialized accelerators on their own kernels while staying general enough for irregular and sparse ones.

The argument in one glance

Problem

When you decide how data flows through a chip forces a choice between speed and flexibility

Every accelerator must orchestrate its datapath: decide when each compute unit runs, and how data moves between units and memory. There are two moments to make those decisions, and each has a weakness. A domain-specific accelerator (a chip built for one job, like a tensor unit for matrix multiply) fixes the datapath at fabrication time, hardwiring it to match that one workload. This is extremely efficient because there is almost no control or memory overhead. But it is fragile: give it a new kernel or irregular, data-dependent input and performance can collapse, dropping below a third of its peak. The other choice is a programmable architecture — a field-programmable gate array (FPGA), a coarse-grained reconfigurable array (CGRA), or a graphics processing unit (GPU) — which decides the datapath at compile time so it can run many programs. This is flexible, but a schedule frozen at compile time cannot adapt to data whose shape is only known while the program runs, so it is inefficient on irregular or sparse data. The efficiency of the specialized chip and the agility of the programmable one seemed to be a trade-off you could not escape.
What people did

Pick a point on the spectrum: hardwire for one workload, or compile for many

Designers chose a side. For maximum efficiency they built domain-specific accelerators with datapaths hardwired at fabrication time, accepting that each chip does one thing well. For flexibility they used programmable fabrics — FPGAs, CGRAs, GPUs — whose datapaths are configured by a compiler ahead of time, accepting lower efficiency in return for running a broad range of applications.
Why it fell short

Both are blind to the data, so neither handles irregular, sparse workloads well

The deeper problem is that both fabrication-time and compile-time orchestration commit to a plan before the data is seen. That is fine for regular, dense workloads whose behavior is predictable, but modern workloads are increasingly irregular and sparse — think a sparse matrix where most entries are zero and the number of nonzeros per row varies wildly. A hardwired accelerator built for dense data wastes almost all its work on the zeros, and a compile-time schedule cannot know in advance which entries exist or how the work is distributed, so it suffers load imbalance and idle units. The information needed to orchestrate the datapath well — where the nonzeros are, how many, in what order — only exists at run time, as the data arrives. What is missing is an architecture that can commit to the regular structure at compile time yet still adapt the fine details to the actual data as it flows, without paying the control overhead that usually makes programmable hardware slow.
This paper's idea

Orchestrate at run time from the data, on a spatial array of small state machines

Canon is a spatial architecture — a two-dimensional mesh of processing elements (small compute units, or PEs) — that adds a third kind of orchestration: runtime, data-driven. It uses a two-tier approach. First, at compile time, it captures the regular structure of a workload — its data-level parallelism (many identical operations on different data) and instruction-level parallelism (independent operations that can overlap) — to lay down a high-level dataflow. Second, it confines dynamic decision-making to only the irregular parts, so the cost of runtime control is paid only where it is actually needed. Two mechanisms make this work. Each processing element carries a programmable finite state machine (FSM) — a tiny controller programmed at compile time to encode the dataflow, one behavior per state — that at run time reads incoming meta-information (for example, sparse-matrix metadata saying which elements are nonzero) and translates it into the right instruction for that state. This produces a continuously evolving dataflow that adapts to the data. The second mechanism is time-lapsed execution: instead of every unit in a row doing the same operation on the same cycle, an instruction is issued across the row one processing element per cycle, creating a staggered pipeline. All the units still execute the same sequence of operations on their own data, just offset in time, which amortizes the control overhead across the whole row and lets the instruction stream change dynamically without breaking the pipeline. Together these let Canon match specialized accelerators on their own kernels while staying general enough for irregular and sparse ones, at a small area cost.

Why this problem is worth solving

The end of easy performance scaling pushed the field toward specialized hardware, but specialization has a hidden brittleness that is now biting.

As general-purpose processors stopped getting much faster each year, designers turned to specialized accelerators, and there has been an explosion of them — tensor units in graphics processors, tensor processing units, and many custom chips for artificial intelligence, media, and sparse computation. Each gets its efficiency the same way: it hardwires the datapath at fabrication time to mirror one application’s intrinsic data flow, which slashes the cost of control and memory movement relative to the computation. That is wonderful when your workload exactly matches the chip. The catch is that workloads change faster than chips can be fabricated, and real inputs are messy. A chip built to stream dense matrices efficiently has no good way to handle a kernel it was not designed for, or input that is irregular or sparse, and its performance can fall below a third of its peak in those cases. So the very design decision that makes an accelerator fast also makes it fragile, and a data center full of specialized accelerators can find that a shift in workload strands its expensive silicon. This is why the ability to be both efficient and adaptable, in one architecture, has become so valuable.

The reason it is genuinely hard is that good orchestration needs information that does not exist until the program runs.

Orchestrating a datapath means deciding, for every step, which unit computes what and how operands and results move. To do this well you need to know the shape of the work. For a dense, regular kernel the shape is known ahead of time, so a compiler can lay out a good schedule. But for a sparse or irregular kernel — say multiplying two sparse matrices where most entries are zero — the essential facts are data-dependent: which entries are nonzero, how many nonzeros each row has, and therefore which units have work and which sit idle. A compile-time schedule has to guess or assume a worst case, so it ends up with load imbalance (some units overloaded, others idle), wasted work on zeros, and dependencies it cannot resolve efficiently. A hardwired accelerator has even less freedom. The fundamental issue is timing: the information required to orchestrate well only becomes available at run time, as the data streams in, yet both traditional approaches lock in their plan before that. The naive fix — make every decision dynamically at run time, like a general-purpose processor — brings back exactly the control and instruction overhead that made programmable hardware inefficient in the first place. The challenge is to adapt to the data at run time while keeping that overhead almost as low as a hardwired chip’s.

What people did before, and where it broke

Fabrication-time orchestration (domain-specific accelerators). Hardwire the datapath to one workload’s data flow, minimizing control and memory overhead. Where it broke. It is fragile: on a new kernel or irregular, data-dependent input, performance can collapse to below a third of its peak, because the fixed datapath cannot adapt.
Compile-time orchestration (FPGAs, CGRAs, GPUs). Let a compiler configure a programmable fabric ahead of time so it can run many applications. Where it broke. A schedule frozen before run time cannot react to data whose shape is only known while running, so it is inefficient on irregular or sparse data, suffering load imbalance and idle units.
Fully dynamic, general-purpose execution. Decide everything at run time, as a CPU or GPU thread does, to handle any data. Where it broke. Making every control decision dynamically reintroduces heavy instruction and control overhead, which is exactly what makes general-purpose hardware inefficient for these kernels compared with a hardwired accelerator.
The gap. No architecture committed to a workload’s regular structure at compile time while still adapting the irregular details to the actual data at run time, and did so with control overhead low enough to rival a specialized accelerator.

How Canon works

A spatial array that decides the fine details from the data at run time

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Adapt the dataflow to the data instead of fixing it in advance. The defining move in Canon is to make orchestration data-driven at run time: the finite state machine in each processing element reads the metadata of the incoming data and produces the matching instruction, so the datapath reshapes itself to what the data actually is — which nonzeros exist, how the work is distributed — rather than following a plan frozen before the data was seen. Building an accelerator whose execution flexibly conforms to the irregular structure of sparse data, rather than forcing sparse data through a fixed dense datapath, is the same principle the work on a multi-dataflow accelerator for sparse-sparse matrix multiplication covered elsewhere on this site is built on, choosing the data movement to fit the workload. Canon generalizes that idea into a per-element state machine driven by the data at run time, so the adaptation happens continuously and automatically.

Amortize control across a spatial fabric so flexibility stays cheap. The reason general-purpose flexibility is usually slow is control overhead — every unit fetching and decoding its own instructions. Canon answers this with time-lapsed execution on its mesh of processing elements: an instruction propagates down a row one element per cycle, so a single orchestrator drives many elements and the control cost is shared, while the array still behaves like many units doing the same work on different data. Arranging computation as a spatial array of reconfigurable processing elements to get parallelism without a heavy instruction pipeline is the same foundation the work on a systematic framework for heterogeneous coarse-grained reconfigurable array realization covered elsewhere on this site rests on, spreading work across a fabric of elements. Canon adds the staggered, time-lapsed issue so that this fabric can also change its instructions dynamically without stalling.

Spend dynamism only where the workload is irregular. Canon’s two-tier design is deliberate: it uses cheap compile-time analysis to lock in the parts of a kernel that are regular — its data-level and instruction-level parallelism — and reserves expensive runtime decision-making for the genuinely irregular parts, like arbitrating which sparse elements to process. Extracting a program’s inherent regular parallel structure and using it to drive an accelerator, so the hardware is not paying to rediscover structure at run time, is the same insight the work on accelerating task-parallel workloads by recovering program structure covered elsewhere on this site relies on, turning known structure into efficient execution. Canon combines that with data-driven runtime control, so it captures regularity for free and pays for dynamism only when the data demands it.

Following a sparse matrix multiply through Canon

Multiplying two sparse matrices where most entries are zero

A trace, drawn from the paper's case study, of how Canon adapts to the data while a fixed design cannot.

Step 1 of 5

The kernel is regular in structure but irregular in data

Sparse matrix multiplication has a predictable overall shape — multiply and accumulate products — but which products are nonzero, and how many per row, is data-dependent and unknown until run time. A fabrication-time or compile-time design must commit before seeing this.

The regular part can be planned ahead; the irregular part cannot.

Why it works

Data-driven orchestration matches the datapath to the actual data. A frozen schedule cannot know a kernel’s data-dependent shape → but a per-element state machine reads the metadata at run time and emits the fitting instruction → so the dataflow adapts to the real nonzeros instead of wasting work on a wrong assumption.
Confining dynamism to irregular parts keeps overhead low. Deciding everything at run time is expensive → but Canon fixes the regular structure at compile time and only arbitrates the irregular parts dynamically → so it pays runtime control cost only where the workload is genuinely unpredictable.
Time-lapsed execution amortizes control across a row. Per-unit instruction fetch is what makes flexible hardware slow → but one orchestrator issues an instruction that propagates down the row one element per cycle → so many elements share one control stream, keeping overhead near a hardwired design’s.
Staggering allows dynamic change without stalling. A rigid lockstep pipeline cannot change instructions mid-flow → but the staggered, continuously evolving issue lets the instruction stream shift as data changes → so the array adapts on the fly while the pipeline keeps flowing.
Exploiting compile-time regularity recovers specialist efficiency. Rediscovering a kernel’s structure at run time wastes energy → but capturing its data-level and instruction-level parallelism ahead of time sets the skeleton for free → so Canon reaches efficiency comparable to accelerators built only for that kernel.

What it costs (trade-offs and scope)

It adds area for its reconfiguration and control machinery. The programmable state machines, orchestrators, and flexible scratchpad are not free: Canon carries about a 12 percent area overhead compared with a dedicated sparse accelerator (though its time-lapsed orchestration also lets it save about 7 percent of area versus a plain SIMD design), so it trades some silicon for adaptability.
A pure specialist still wins on its own single kernel. Canon aims to be on par with specialized accelerators, not to beat them at their one target; a chip hardwired for exactly one dense kernel can still edge it out there, and Canon’s advantage appears across diverse and irregular workloads, not on any single fixed one.
The benefit depends on there being regularity to exploit. The two-tier approach works because most kernels have a regular skeleton plus irregular details; a workload that is irregular through and through, with little compile-time structure, gives Canon less to lock in cheaply and more to handle dynamically.
Compile-time mapping and finite-state-machine programming are required. Each kernel must be analyzed and mapped, and the per-element state machines programmed; this is a compiler and toolchain effort, and kernels whose loops are not supported by the mapping cannot run on the fabric.
The gains are shown on specific kernels and baselines. The evaluation covers dense and sparse tensor kernels and benchmark suites against baselines like a tensor-processing-unit-style systolic array, a structured-sparse array, a coarse-grained reconfigurable array, and a sparse accelerator; results are strongest for the mix of dense and sparse, data-driven kernels studied, and other workloads may behave differently.

The evaluation

Efficiency versus flexibility across orchestration styles

Property	Domain-specific accelerator (fabrication-time)	Programmable fabric (compile-time)	Canon (runtime, data-driven)
Efficiency on its target kernel
Performance on new or irregular kernels
Handles sparse, data-dependent work
Flexibility across applications
Area

A qualitative comparison of orchestration styles. Canon integrates compile-time and runtime, data-driven orchestration to reach efficiency on par with specialized accelerators across dense and sparse kernels while staying general, at about a 12 percent area overhead versus a dedicated sparse accelerator; specialized accelerators fall below a third of their peak on off-target or irregular data.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (arXiv:2602.17119). The mechanism described is the paper’s: Canon is a two-dimensional-mesh spatial architecture of processing elements that integrates compile-time and runtime orchestration. It uses a two-tier approach, exploiting inherent workload regularities (data-level and instruction-level parallelism) at compile time to establish a high-level dataflow, and confining dynamic, data-driven decisions to the irregular parts. Its first mechanism is a dynamic data-driven orchestration using programmable finite state machines, programmed at compile time to encode the dataflow with one behavior per state and translating incoming meta-information (for example, sparse metadata) into instructions at run time. Its second mechanism is a time-lapsed SIMD execution model in which instructions are issued across a row of processing elements over several cycles, creating a staggered pipeline that amortizes control overhead and allows dynamic instruction changes while constructing a continuously evolving dataflow. The paper maps dense and sparse kernels (such as sparse matrix multiplication and sampled dense-dense matrix multiplication), tackling irregular access patterns, reduction-induced dependencies, and workload imbalance while preserving fine-grained parallelism. It evaluates against baselines of varying specialization (a tensor-processing-unit-style systolic array, a structured-sparse array, a coarse-grained reconfigurable array, and a sparse accelerator), reporting performance on par with specialized accelerators in their own domains with minimal efficiency loss, an area overhead of about 12 percent versus a dedicated sparse accelerator, and about 7 percent area savings versus a SIMD design, while specialized accelerators drop below a third of their peak on off-target or irregular data. Exact per-kernel results, the compiler details, and the full methodology should be read from the paper.

Background

Why architecture keeps searching for the middle between specialized and general

It helps to see Canon as an attempt to resolve a tension that has driven computer architecture for years: the pull between specialization, which is efficient but rigid, and generality, which is flexible but wasteful. The slowdown of general-purpose scaling triggered a wave of domain-specific accelerators, and they delivered enormous efficiency by hardwiring a datapath to one job. But the field quickly rediscovered the cost of that rigidity — a chip that is perfect for one kernel is stranded by the next, and real data is irregular in ways fixed hardware handles badly. So a recurring research goal has been to build hardware that is programmable enough to be reused yet efficient enough to rival a specialist, especially for the sparse and irregular workloads that dominate modern machine learning and graph processing. The effort to specialize a processor for sparse computation while keeping it programmable, rather than hardwiring a single sparse datapath, is the same balance the work on a stream instruction set and processor specialization for sparse computation covered elsewhere on this site strikes, aiming for efficiency without giving up programmability. Canon pushes further by moving key orchestration decisions to run time and driving them from the data itself, arguing that the way out of the efficiency-versus-flexibility trap is to decide how to compute at the last possible moment, when the data finally reveals what is needed.

If you remember only three things

1. An accelerator must orchestrate its datapath — decide when each unit computes and how data moves — and there are two traditional moments to do it, each flawed. Fabrication-time orchestration (domain-specific accelerators) hardwires the datapath for one workload, giving peak efficiency but fragile performance that collapses below a third of peak on new or irregular kernels. Compile-time orchestration (FPGAs, coarse-grained reconfigurable arrays, GPUs) is flexible but cannot adapt to data whose shape is only known at run time, so it is inefficient on irregular or sparse workloads.
2. Canon is a two-dimensional spatial array of processing elements that adds a third option: runtime, data-driven orchestration. It uses a two-tier approach — capture a workload's regular structure (data-level and instruction-level parallelism) at compile time, and confine dynamic decisions to the irregular parts. Each processing element has a programmable finite state machine that turns incoming data metadata (such as which matrix entries are nonzero) into the right instruction at run time, and a time-lapsed execution model staggers one instruction down a row of elements so control overhead is amortized and the instruction stream can change without stalling.
3. By fixing the regular skeleton cheaply and paying for dynamism only where the data is irregular, Canon reaches efficiency on par with specialized accelerators across dense and sparse kernels while remaining a general-purpose fabric, at about a 12 percent area overhead versus a dedicated sparse accelerator (and about 7 percent area savings versus a SIMD design). It does not aim to beat a pure specialist on that specialist's single kernel, it needs a compile-time mapping and state-machine programming per kernel, and its benefit depends on there being regular structure to exploit.

Check yourself

Check your understanding

1. Why do both domain-specific accelerators and compile-time programmable fabrics struggle with irregular, sparse workloads?
2. What is Canon's core idea for combining efficiency with flexibility?
3. What is time-lapsed execution, and why does it matter?
4. Predict: you run a brand-new irregular kernel that a fixed sparse accelerator was not designed for. How do the fixed accelerator and Canon each behave, and why?

Sources

The paper is “A Data-Driven Dynamic Execution Orchestration Architecture” by Zhenyu Bai, Pranav Dangi, Rohan Juneja, Zhaoying Li, Zhanglu Yan, Huiying Lan, and Tulika Mitra (National University of Singapore), published at ASPLOS 2026, DOI 10.1145/3760250.3762226. It is licensed CC BY.

This explainer is written from the paper’s full text (arXiv:2602.17119). The paper presents Canon, a spatial architecture (a two-dimensional mesh of processing elements) that integrates compile-time and runtime orchestration to overcome the performance fragility of specialized accelerators and the inefficiency of compile-time-orchestrated programmable fabrics on irregular or sparse data. Canon uses a two-tier approach: it exploits inherent workload regularities (data-level and instruction-level parallelism) at compile time to establish a high-level dataflow, and confines dynamic, data-driven orchestration to the irregular parts. It introduces a dynamic data-driven orchestration mechanism using programmable finite state machines, programmed at compile time to encode the dataflow (one behavior per state) and translating incoming meta-information (such as sparse metadata) into instructions at run time, together with a time-lapsed SIMD execution model in which instructions are issued across a row of processing elements over several cycles, creating a staggered pipeline that amortizes control overhead and permits dynamic instruction changes while constructing a continuously evolving dataflow. Canon is evaluated on dense and sparse kernels against baselines of varying specialization, achieving performance on par with specialized accelerators in their own domains with minimal efficiency loss while remaining general, at about a 12 percent area overhead versus a dedicated sparse accelerator and about 7 percent area savings versus a SIMD design, whereas specialized accelerators can drop below a third of their peak on off-target or irregular data. No numbers beyond the paper’s own have been introduced; exact per-kernel results, the compiler details, and the full methodology should be confirmed in the paper.