CRUSH: A Credit-Based Approach for Functional Unit Sharing in Dynamically Scheduled HLS

Dynamically scheduled HLS turns C code into dataflow circuits whose parts run whenever their data is ready, which is fast but hardware-hungry — so you want to share one expensive floating-point unit among several operations, except naive sharing can deadlock the circuit and the prior fix forced every access into a rigid program order that both throttled performance and took a slow search to compute; this paper (ETH Zurich — Jiahui Xu and Lana Josipovic) presents CRUSH, which borrows credit-based flow control from interconnects to prevent deadlock while allowing out-of-order access to the shared unit, uses fast graph heuristics instead of an exhaustive solver, and cuts 12 percent of DSPs, 15 percent of flip-flops, and 90 percent of the optimization runtime versus that prior scheme.

The argument in one glance

Problem

Dataflow circuits are fast but expensive, so you must share their scarce units

A modern way to build FPGA hardware from C code is dynamically scheduled high-level synthesis: instead of fixing a rigid schedule at compile time, it produces a dataflow circuit whose compute units fire as soon as their input data is ready, coordinated by handshake signals. This lets the hardware sail through irregular control flow and unpredictable memory accesses that trip up conventional tools, which is why it can be much faster. But that speed is not free: dataflow circuits use a lot of hardware, and on an FPGA the most valuable building blocks — the DSP blocks that implement floating-point arithmetic — are scarce. To fit a real application, you have to let several operations take turns on one physical unit. That is resource sharing, and it is the only way to make these fast circuits practical at scale.
What people did

Share a unit naively, or force every access into program order

The obvious move is to wire several operations into one shared unit behind a small wrapper that selects whose turn it is. Naively done, this deadlocks: a pending result can block the shared unit while it waits for a downstream join that in turn waits for a token stuck behind the block, and the whole circuit freezes. The one prior method that fixes this (Josipovic et al.) makes every access happen strictly in control-flow order — operation of iteration one before iteration two, and so on — which provably avoids the cycle.
Why it fell short

Strict ordering throttles throughput and is slow to compute

Forcing a total order costs performance: whenever the natural schedule wants two operations to run out of order, the imposed order stalls one of them, inflating the initiation interval — the gap between loop iterations — so the circuit runs slower than it could. Worse, the newest, fastest dataflow HLS strategies deliberately drop the basic-block structure the ordering relies on, so it does not even apply. And to pick a good order, the prior method repeatedly solves a slow mixed-integer optimization to score each sharing decision, which does not scale to complex applications.
This paper's idea

Credit-based control for deadlock freedom, plus out-of-order access and fast heuristics

CRUSH borrows credit-based flow control from interconnect design: each operation holds a number of credits equal to free output-buffer slots, spends one to issue a computation, and gets it back when a result leaves, so the head of the line can never be blocked and the deadlock simply cannot form. Because correctness no longer needs a total order, CRUSH lets operations access the shared unit out of order, seizing sharing opportunities the rigid scheme missed, and an adaptive priority arbiter prevents a second kind of deadlock. Fast graph heuristics — not an exhaustive solver — choose the sharing groups and priorities, cutting 12 percent of DSPs, 15 percent of flip-flops, and 90 percent of the optimization runtime versus the prior method.

Why this problem is worth solving

The appeal of these circuits is exactly what makes sharing dangerous.

In standard high-level synthesis, a compiler fixes the schedule of a hardware design at compile time — it decides in advance which operation runs on which cycle, much like a VLIW processor that relies on the compiler to find all the parallelism. That works only when the code is regular and predictable. Dynamically scheduled HLS instead produces a dataflow circuit: a network of compute units (forks, joins, merges, muxes, branches, buffers, and arithmetic units) that pass data tokens over channels and fire as soon as their inputs are present, resolving order at runtime like an out-of-order superscalar processor. This runtime flexibility is what lets the circuit exploit parallelism through irregular control flow and unpredictable memory, giving it a real performance edge. But the same property is what makes sharing hard: because units fire opportunistically rather than on a fixed timetable, letting two operations take turns on one physical unit can create a dependency between things that were never meant to depend on each other, and in a system where everything is coupled through backpressure, that new dependency can close into a cycle. So the very dynamism that makes the circuit fast is what makes naive resource sharing unsafe.

Sharing is not a nice-to-have here; it is what decides whether a design fits on the chip at all.

Resource sharing is a classic hardware-synthesis optimization: instead of building one physical unit per operation, you build fewer units and let multiple operations use them at different times. It matters most for the expensive, scarce resources — on an FPGA, the DSP blocks that implement floating-point multiply and add, of which a chip has only so many. A dataflow circuit that instantiates a separate floating-point unit for every arithmetic operation in the source code can simply be too big to fit, so sharing is what makes large applications implementable at all. The catch specific to dataflow circuits is that a unit is only worth sharing if the operations using it are underutilized — if each leaves pipeline stages idle enough of the time that they can interleave without slowing the circuit down. Deciding which operations to group onto one unit, and in what priority they should take turns, so that the circuit stays both correct and fast, is precisely the problem CRUSH solves. Framing sharing as the gate to fitting real designs on real chips, rather than a minor tuning knob, is what makes getting it right worth a whole system.

What people did before, and where it broke

Naive sharing behind a wrapper. Route several operations into one shared unit with a merge, a mux, and a branch to send each result back to the right successor. Where it broke. Head-of-line blocking: a result waiting at the shared unit’s output can block the unit while a downstream join waits for a token stuck behind it, closing a dependency cycle that deadlocks the entire circuit.
Total-token-order sharing (the prior state of the art). Josipovic et al. avoid the deadlock by forcing every access to the shared unit to happen in strict control-flow order across iterations, which provably breaks the cycle. Where it broke. The imposed order stalls operations the natural schedule wanted to run out of order, inflating the initiation interval and lowering throughput, so correctness is bought with performance.
Exhaustive evaluation of sharing decisions. To choose which operations to share and in what order, the prior method repeatedly solves a mixed-integer linear program that scores the performance impact of each decision. Where it broke. Solving the optimization over and over is slow and does not scale to complex applications, making the optimization runtime itself a bottleneck.
Ordering that assumes basic-block structure. The total-order scheme regulates access using the program’s basic-block organization. Where it broke. The newest, highest-performance dataflow HLS strategies deliberately omit basic-block structure to extract more out-of-order parallelism, so a method that re-imposes basic-block order either does not apply or throws away the very parallelism those strategies exist to capture.
The gap. No sharing strategy for dataflow circuits was simultaneously deadlock-free without a total order, able to seize out-of-order sharing opportunities, agnostic to the circuit’s control-flow mechanism, and fast to compute with scalable heuristics rather than a slow exhaustive solver.

How CRUSH works

From a deadlock-prone shared unit to safe, out-of-order, fast-to-compute sharing

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

The idea

Let the circuit access the shared unit out of order, the way a dynamic circuit wants to. The whole point of dynamically scheduled HLS is that operations fire when their data is ready, not on a timetable fixed in advance. The prior sharing method fought that instinct: to stay deadlock-free it forced every access to the shared unit into strict program order, which meant that whenever the natural schedule wanted operation A of the next iteration to go before operation B of this one, the ordering stalled it and stretched the initiation interval. CRUSH removes the total order entirely — its deadlock freedom comes from credits, not from ordering — so operations can reach the shared unit out of order and the circuit reclaims the sharing opportunities the rigid scheme left on the table. Because the deadlock-avoidance is agnostic to the circuit’s control-flow mechanism, it also works with the newest strategies that drop basic-block structure to expose more parallelism. Insisting that the optimization respect the dynamic, reconfigurable nature of the underlying fabric rather than flatten it into a fixed order is the same instinct the heterogeneous CGRA-realization work covered elsewhere on this site is built on, mapping computation onto a flexible spatial substrate instead of forcing it through a rigid pipeline.

Steal deadlock freedom from interconnects: credits, not orderings. The key move is to recognize that the head-of-line deadlock in a shared dataflow unit is the same hazard that routers and on-chip networks have solved for decades with credit-based flow control. So CRUSH gives each sharing operation a small pool of credits equal to the free slots in its output buffer, charges one credit per computation issued, and refunds it only when a result actually leaves and frees a slot. The invariant this maintains — a token is only ever admitted to the shared unit when a landing spot is guaranteed to be waiting for it — is exactly what makes the head-of-line token unstallable, which is what makes the deadlock impossible. A second, adaptive priority arbiter handles the mirror-image hazard on the input side, where a fixed access order could let a missing request block everyone behind it. Borrowing a proven mechanism from a neighboring domain rather than inventing a bespoke, resource-heavy ordering scheme is the same make-acceleration-practical discipline the fast-FPGA-compilation work covered elsewhere on this site relies on, reusing established machinery so that reconfigurable hardware stays usable under real resource limits.

Decide sharing with scalable graph heuristics, not an exhaustive solver. Even once sharing is safe, you still have to choose which operations to group and in what priority, and doing that well is what preserves the initiation interval. The prior method answered this by repeatedly solving a mixed-integer program to score decisions, which is accurate but slow and does not scale. CRUSH replaces the solver with cheap, well-understood graph analysis: it finds the strongly connected components of each performance-critical subcircuit — computable in time linear in the circuit size — and uses simple rules over them to avoid grouping operations that must run simultaneously and to order accesses along the dataflow, guided by a cost function that weighs units saved against wrapper logic added. This is a heuristic, not a proof of optimality, but it captures the structure that matters and runs 90 percent faster. Trading an exhaustive search for a scalable, structure-aware compiler analysis is the same engineering bet the MLIR-based hardware-accelerator IR work covered elsewhere on this site makes, reasoning about hardware through analyzable graph representations so the compiler stays fast on large designs.

Following a shared unit through CRUSH

Sharing one floating-point unit between two operations without deadlock or slowdown

A trace, drawn from the paper's worked examples, of how CRUSH shares a unit that a naive scheme would deadlock and a total-order scheme would slow down.

Step 1 of 5

Two underutilized operations want the same unit

Two floating-point operations of the same type each leave pipeline stages idle enough of the time that, in principle, one physical unit could serve both while the circuit still starts an iteration every two cycles. Sharing them would free a scarce DSP-backed unit, but only if it neither deadlocks nor stretches the initiation interval.

An operation is a good sharing candidate precisely when its token occupancy — its latency divided by the initiation interval — leaves the unit underused.

Why it works

Credits make the head-of-line deadlock structurally impossible. A token can only reach the shared unit when a downstream slot is guaranteed free → but then the head-of-line token always has somewhere to go and can never be stalled → so the dependency cycle that causes deadlock simply cannot close, with no ordering rule needed.
Priority arbitration beats fixed order on the input side. A fixed access order lets an absent request block everyone queued behind it → but a priority arbiter lets a lower-priority operation run when the higher-priority one is not ready → so no dependency is created between the predecessors of shared operations, closing the second deadlock route.
Dropping the total order recovers lost throughput. A strict program order stalls operations the dynamic schedule wanted to run out of order → but credit-based safety allows out-of-order access to the shared unit → so CRUSH seizes sharing opportunities the prior scheme missed, holding the initiation interval within about 1 percent while sharing more.
Control-flow-agnostic safety fits modern dataflow HLS. The prior method needed basic-block structure that the fastest strategies now discard → but credits and priority depend on buffers and readiness, not on program structure → so CRUSH applies even to circuits built to maximize out-of-order execution, where the old method could not.
Graph heuristics scale where a solver stalls. Scoring every sharing decision with a mixed-integer program is accurate but slow → but strongly-connected-component analysis runs in time linear in circuit size and captures the dependencies that matter → so CRUSH computes its sharing 90 percent faster and stays usable on complex applications.

What it costs (trade-offs and scope)

The heuristics are not proven optimal. CRUSH deliberately swaps an exhaustive mixed-integer solver for fast graph rules, so it can leave some sharing on the table or occasionally group less aggressively than an optimal search would; the paper’s grouping rule, for instance, conservatively refuses to share operations in the same strongly connected component even when doing so would not actually hurt the initiation interval.
The wrapper adds area and timing overhead. Credit counters, the priority arbiter, muxes, and condition buffers all cost logic, so sharing pays off only when the saved units outweigh the wrapper; CRUSH uses an explicit cost function to judge this, and on some benchmarks its critical-path delay is slightly worse than the prior method, which the paper attributes to Dynamatic’s timing optimization rather than the strategy itself.
Credits must be sized to keep the pipeline full. Deadlock freedom needs only that credits not exceed output-buffer slots, but holding the initiation interval needs enough credits and buffering that the shared unit is not starved; getting too few credits would preserve correctness while quietly lowering throughput, so buffer and credit allocation is a real part of the design.
Evaluated on floating-point sharing in linear-algebra kernels. The results come from sharing floating-point arithmetic units on PolyBench kernels plus two irregular kernels (gsum and gsumif), all with initiation intervals above one; how the gains carry to other resource types, other operation mixes, or fully compute-bound kernels is not the focus, though the mechanism is presented as general.
The performance edge over the prior method is modest per kernel. Against the total-order scheme the average savings are 12 percent DSPs and 15 percent flip-flops with about 4 percent faster execution; the dramatic number is the 90 percent optimization-runtime reduction, so the headline benefit is as much about making sharing fast to compute and applicable to modern circuits as about shrinking any single design.

The evaluation

Sharing floating-point units in dynamically scheduled dataflow circuits

Property	Naive sharing	In-order (prior work)	CRUSH
Deadlock-free
Access order to the shared unit
Works without basic-block structure
How sharing decisions are computed
Reported result vs In-order

A comparison drawn from the paper. CRUSH is evaluated in the Dynamatic HLS compiler on PolyBench and two irregular kernels; it also shares successfully on a newer out-of-order dataflow strategy (Fast token) where the In-order method's basic-block ordering does not apply.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The full paper text was available (the authors’ own copy from the ETH Dynamo group site), so this account of the mechanism — the two deadlock types, credit-based head-of-line avoidance, priority arbitration, the strongly-connected-component grouping and priority heuristics, the cost function, and credit and buffer sizing — reflects the paper’s own description. The headline numbers are the paper’s reported averages against the prior In-order method: 12 percent fewer DSPs, 15 percent fewer flip-flops, and 90 percent less optimization runtime, at roughly 1 percent initiation-interval cost and about 4 percent faster execution. Those are averages over a specific benchmark set (PolyBench kernels plus gsum and gsumif), sharing floating-point units, all with initiation intervals above one; per-kernel results vary, and a few kernels show a slightly worse critical path. The exact per-benchmark tables, the algorithms’ pseudocode, and the cost-function details should be read from the paper itself.

Background

Why turning C into hardware is where this all starts

It helps to remember where dataflow circuits come from. The premise of high-level synthesis is that a designer should be able to write ordinary software — C or C++ — and have a tool compile it into a working hardware circuit, rather than hand-writing register-transfer-level descriptions. Standard HLS does this by fixing a schedule at compile time, which works only for regular, predictable code; dynamically scheduled HLS instead emits a dataflow circuit that decides order at runtime, which is what buys its performance on irregular programs but also what makes it hardware-hungry and, therefore, what makes sharing necessary. So CRUSH sits at the tail end of a long pipeline whose first job is simply to get from a high-level language to hardware at all. That translation from C code into a synthesizable heterogeneous hardware design is the same starting point the automated HLS-from-C work covered elsewhere on this site takes on, turning software into hardware descriptions that later optimization passes like CRUSH then have to make small enough to fit. Seen this way, resource sharing is not an afterthought but the step that decides whether the hardware a compiler generates from your program can actually be built.

If you remember only three things

1. Dynamically scheduled HLS compiles C into dataflow circuits that fire units as data arrives, which is fast on irregular code but hardware-expensive, so sharing scarce units (like floating-point DSP blocks) among operations is essential — yet naive sharing can deadlock the circuit through head-of-line blocking, and the prior deadlock-safe method forced a strict control-flow access order that throttled throughput, could not apply to the newest basic-block-free strategies, and required a slow mixed-integer solve per decision.
2. CRUSH borrows credit-based flow control from interconnects: each operation holds credits equal to its free output-buffer slots, spends one to issue a computation, and regains it only when a result leaves, guaranteeing every admitted token a landing slot so the head-of-line deadlock cannot form — with no ordering constraint, which lets operations access the shared unit out of order; a priority arbiter closes a second deadlock route on the input side, and linear-time strongly-connected-component heuristics choose groups and priorities instead of an exhaustive solver.
3. Integrated into the Dynamatic HLS compiler, CRUSH cuts an average 12 percent of DSPs, 15 percent of flip-flops, and 90 percent of the optimization runtime versus the prior In-order method, at about 1 percent initiation-interval cost, and it shares successfully even on newer out-of-order dataflow circuits where the prior basic-block ordering does not apply. Results are averages over floating-point sharing on PolyBench plus two irregular kernels; the heuristics are scalable rather than provably optimal.

Check yourself

Check your understanding

1. Why is resource sharing both necessary and dangerous in a dynamically scheduled dataflow circuit?
2. What did the prior total-order (In-order) sharing method do, and what were its costs?
3. How does CRUSH prevent the head-of-line deadlock without imposing a total order?
4. What are the main results of CRUSH and how are they best summarized?

Sources

The paper is “CRUSH: A Credit-Based Approach for Functional Unit Sharing in Dynamically Scheduled HLS” by Jiahui Xu and Lana Josipovic (ETH Zurich), published at ASPLOS 2025, DOI 10.1145/3669940.3707273. It is licensed CC BY.

This explainer is based on the paper’s full text, obtained from the authors’ own copy hosted by the ETH Zurich Dynamo research group (dynamo.ethz.ch). The account of the mechanism — dynamically scheduled dataflow circuits and their units, the two sharing-induced deadlock types (head-of-line blocking and fixed access order), the credit-based control that eliminates head-of-line blocking, the priority-based arbitration that eliminates the fixed-order deadlock, the strongly-connected-component-based sharing-group and access-priority heuristics, the resource cost function, and the credit and buffer sizing — follows the paper’s own description. The reported results cited here are the paper’s own averages against the prior In-order (total-token-order) method: 12 percent fewer DSPs, 15 percent fewer flip-flops, and 90 percent less optimization runtime, at roughly 1 percent initiation-interval cost and about 4 percent faster execution, measured with the Dynamatic HLS compiler on a set of PolyBench kernels plus gsum and gsumif. CRUSH has been integrated into Dynamatic (github.com/EPFL-LAP/dynamatic). Exact per-benchmark numbers, the pseudocode of the grouping and priority algorithms, and the full cost-function derivation should be read from the paper itself.