High-Level Synthesis: Scheduling, Binding, and the Latency-Area Trade

High-level synthesis takes a program in C, C++, or a similar sequential language and produces RTL. The gap it has to bridge is large: the source has one instruction stream that executes in order, and the target has hardware units that can execute concurrently, are shared between operations, and are governed by a clock. Closing that gap requires three decisions: when each operation executes, which hardware unit executes it, and how the state of the computation is held between clock cycles. The quality of the output is almost entirely determined by how well those three decisions were made.

The first two decisions have names. Scheduling assigns each operation to a clock cycle or a control step. Binding assigns each operation and each value to a functional unit and a register. They are coupled: scheduling decides how many units are needed at each step, binding decides whether the units exist, and a schedule that assumes four multipliers is infeasible if the design can afford one.

The dependency graph is the boundary of what can move

Before any scheduling, the tool builds a data-flow graph from the source. Each operation is a node; each data dependency is an edge; the loop structure and the control flow become constraints on which nodes may execute in which order. The critical path through that graph, in units of operator delay, gives the shortest possible latency for one iteration with unlimited hardware. That number is the lower bound no schedule can beat, and it is usually much smaller than the latency the tool actually achieves.

The gap comes from resources. With one multiplier and a loop body containing four multiplications that are mutually independent, the four must be serialized onto the one unit, so the loop body takes at least four multiplication latencies regardless of the dependency graph’s depth. That is the resource constraint, and it is why the tool’s primary knob is the number of each operator type it is allowed to instantiate.

Two scheduling formulations follow from this. As-soon-as-possible scheduling places every node at the earliest cycle its predecessors allow, without regard to resource counts; the result is a schedule with minimum latency and maximum concurrency, and the resource requirement it implies is the number of operations of each type in the busiest cycle. As-late-as-possible scheduling places every node at the latest cycle its successors allow, which gives each operation the window between its earliest and latest possible cycle; the width of that window is its mobility, and it is what a resource-constrained scheduler uses to decide which operations can be moved without extending the schedule.

The practical formulation is neither: it is a resource-constrained schedule, usually obtained by list scheduling. Nodes are ordered by priority, typically by their position on the critical path, and each is placed at the earliest cycle where its predecessors have completed and a functional unit of its type is free. List scheduling is greedy and runs in time roughly proportional to the graph size times the schedule length. It carries no optimality guarantee: on the simplest version of the problem, identical units with equal delays and a precedence graph, its worst-case makespan is bounded by $2 - 1/m$ times the optimum for $m$ units. Its weakness is that the priority function is a heuristic: a node off the critical path can be scheduled early and occupy a unit that a critical node needs later.

Loop body, one multiply available, latency 2 cycles per multiply:

  a = b * c        cycle 0-1
  d = e * f        cycle 2-3
  g = h * i        cycle 4-5
  s1 = a + d       cycle 6
  y  = s1 + g      cycle 7

Critical path with unlimited units: multiply (2) + two adds (2) = 4 cycles.
With one multiplier: 6 cycles of multiply plus 2 of add = 8 cycles.

The example is the entire trade in miniature. Latency went from 4 to 8 cycles by reducing the multiplier count from three to one, and the area saved is two multipliers. Nothing in the source says which is better; the choice is a constraint the designer supplies.

Loop transformations decide more than scheduling does

A loop is the unit that HLS tools handle least transparently, and the decisions about it dominate the result.

A loop that is neither unrolled nor pipelined executes one iteration per pass through the datapath, so its throughput is one iteration per iteration latency. Unrolling by a factor $k$ replicates the body $k$ times, which allows $k$ iterations’ worth of independent operations to be scheduled concurrently and reduces the loop overhead. Whether it also buys throughput depends on the resource budget: if the tool may instantiate $k$ copies of each operator, area grows with the extra units; if the count is fixed, the replicated operations serialize onto the same units and the loop is no faster. Unrolling fully removes the loop entirely and turns the trip count into a static dependency graph, which gives the scheduler the most freedom and produces the largest design.

Pipelining a loop is different from unrolling it. A pipelined loop starts a new iteration every $II$ cycles, where the initiation interval is less than the iteration latency, so several iterations are in flight in different stages of the datapath. The limit on $II$ is the resource constraint (total operations of a type divided by units of that type) and the recurrence constraint: if iteration $i+1$ depends on a value computed in iteration $i$, the dependency chain through the loop body sets a floor on $II$ that no amount of hardware can lower. That floor is the same conservation law that limits retiming in register retiming and balancing: a feedback path with $k$ registers can hold at most $k$ iterations in flight, so the initiation interval cannot be smaller than the loop’s latency divided by $k$.

A recurrence that cannot be broken by pipelining can sometimes be broken by transformation. Associative reductions such as a sum over an array can be restructured into a tree, which shortens the dependency chain from $N$ additions to $\log_2 N$ levels. The transformation is legal only if the operation is genuinely associative in the arithmetic being used, which for fixed-point addition with wrapping is true and for floating-point addition is not. An HLS tool that reorders a floating-point reduction changes the result, and the change is not a rounding difference in the last bit; it can be larger.

Arrays, memories, and the mapping that decides feasibility

An array in the source becomes a memory in the datapath, and the number of ports on that memory is the constraint that most often makes a schedule infeasible. A single-port memory allows one access per cycle. A loop body that reads three different elements and writes one in the same cycle cannot use a single-port memory without serialization, so the scheduler either spreads the accesses over cycles or the tool must partition the array.

Partitioning splits an array into banks so that accesses in the same cycle go to different banks. A cyclic partition of factor $k$ places element $i$ in bank $i \bmod k$, which allows $k$ concurrent accesses if the indices are distinct modulo $k$ and degenerates to serialization if they are not. A block partition assigns contiguous ranges to banks, which suits accesses to a contiguous region. The choice depends on the access pattern, which the tool infers from the loop structure. An access pattern the tool cannot prove regular is treated as an arbitrary access requiring full serialization.

This is where the source’s shape matters most. A loop with a constant stride and static bounds gives the tool enough information to partition, unroll, and pipeline. A loop whose bounds are runtime values, or whose index is computed through a pointer, forces conservative assumptions: the tool must assume the worst case about aliasing and bounds, and the resulting hardware is a serialized datapath with multiplexers around the memory. The same algorithm written with static bounds lets the tool build parallel banks and a pipelined loop instead, and the difference in the generated structure is larger than any arithmetic change could account for.

Interfaces, handshakes, and the cost of a stall

An HLS-generated block is not a free-standing circuit; it is a component with a protocol. Tools generate a wrapper that implements one of a small number of standard interface styles: a simple valid-ready handshake on each port, a memory-mapped slave interface, or a streaming interface with its own flow control.

The interface style propagates into the datapath. A design with a valid-ready handshake on its inputs must be able to stall: if an input is not valid, the datapath cannot consume it, and every register in the pipeline has to hold. That requirement forces clock enables on all the pipeline registers, which costs area and, more importantly, forces the tool to reason about which operations can be stalled independently. A design with a guaranteed-valid input can omit the enables, which is cheaper and faster, at the cost of correctness if the assumption is ever violated.

Block-level handshaking has a further consequence for latency accounting. A block that takes a variable number of cycles depending on its input, because it contains a data-dependent loop, cannot be described by a single latency figure, and a system that assumed a fixed latency will break. The usual resolution is to make the block’s completion visible through the handshake rather than through a timer, which is the reason generated interfaces carry valid signals rather than cycle counts.

Where the generated hardware diverges from the source

Three divergences are routine and worth checking in the output rather than assuming.

Floating point is not free. A floating-point operation in the source becomes a floating-point unit or a call to one, and those units are large and multi-cycle. An algorithm written in float for convenience can synthesize to a design many times the area of the same algorithm in fixed point. The tool will do what the source says, and the source usually does not say what the designer meant.

Division and modulo are not single-cycle. Integer division in hardware is iterative, tens of cycles for a wide operand, and a modulo by a runtime value is the same operation. A loop body with a division in it has a latency floor that no scheduling can remove, and a division inside a recurrence makes the loop unpipelined. Division by a constant power of two is a right shift for unsigned operands; for signed operands it needs a bias correction, because an arithmetic shift rounds down while division truncates toward zero. The tool may or may not make that transformation.

Pointers and dynamic memory are usually unsupported. A source that allocates, or that indexes through a pointer the tool cannot resolve, has no hardware counterpart that preserves the semantics. Tools restrict the language for exactly this reason, and the restrictions are documented per tool rather than being properties of the language. Code that compiles is not necessarily code that synthesizes to something with the intended behaviour, and the difference is visible only in the generated RTL and its schedule report.

The reports are the part of the flow that deserves the most attention. A schedule report names the cycle each operation landed in, the units it was bound to, and the loop’s initiation interval. Reading it against the source is the only way to know whether the tool made the decisions that were intended, because the source language has no way to express them. The generated RTL then enters the ordinary gate-level flow, where the schedule is no longer visible and only the equivalence check against the source constrains it. That is the standing limitation of the approach: the abstraction that makes the design fast to write is the same abstraction that hides the hardware, and the synthesis report is where the hardware becomes visible again.