High-Level Synthesis: Scheduling, Binding, and Inferred Hardware

A procedural description of an algorithm has no notion of cycles. A loop over an array is a statement about values, not about how many clock edges elapse while the values are computed. High-level synthesis resolves that ambiguity by choosing a schedule, and the choice is where the hardware’s shape is decided: how many adders exist, whether a loop body’s iterations overlap, whether an array becomes a block RAM or a bank of registers, and how the resulting circuit is driven from outside.

The three subproblems

Synthesis from a procedural description decomposes into scheduling, allocation, and binding. Scheduling assigns each operation to a clock cycle subject to data dependencies and resource limits. Allocation chooses how many functional units of each kind exist. Binding maps operations onto units and variables onto storage. The three interact: a tighter schedule needs more units, and more units make binding easier at the cost of area.

The constraint that drives all three is the target clock period. Each operation has a delay, drawn from the delays of the library’s implementations at that period, and a chain of dependent operations cannot be packed into one cycle unless the sum of their delays plus the register overhead fits. High-level synthesis tools treat this as an estimate first and refine after scheduling, because the delay of an operation depends on how many logic levels the tool will need to implement it, which depends on the schedule. The iteration is why the reported timing after high-level synthesis is an estimate and the reported timing after implementation is the truth.

The essential distinction between the two extremes is easy to state. Area-constrained scheduling uses a fixed number of units and finds the shortest schedule. Latency-constrained scheduling uses a fixed schedule length and finds the fewest units. Tools present this as a small number of effort settings, but the underlying problem in both cases is an integer program with a relaxation-based heuristic, and the result is not guaranteed optimal.

Overlap: the difference between high-level and RTL design

A loop in the source is not a state machine. If the loop’s iterations are independent, the tool can schedule them overlapping in time, starting the next iteration’s operations before the current one finishes. This is what makes high-level synthesis productive: a pipeline described as a loop becomes a pipelined datapath, and the tool’s target initiation interval, the number of cycles between successive iterations entering the pipeline, becomes the dominant performance parameter.

An initiation interval of one means a new input enters every cycle, which requires enough independent resources to compute one iteration per cycle. The binding constraints that prevent it are resource limits, such as only one multiplier, or a recurrence, such as a variable that each iteration depends on the previous iteration’s value. A recurrence sets a hard lower bound on the interval regardless of how many units exist, and it is the most common reason a pipelined loop fails to reach the requested rate. The tool reports the limiting recurrence, and its location in the source is the only place the fix can be made.

// II=1 only if the accumulator recurrence is short enough:
// acc's feedback path must fit in one clock period.
void fir(int *y, const int *x, const int *c, int n) {
  static int acc = 0;                  // carried across iterations
  for (int i = 0; i < n; i++) {
    #pragma HLS PIPELINE II=1
    acc += x[i] * c[i];
    y[i] = acc;
  }
}

The recurrence bound is worth stating in arithmetic terms. If the accumulator’s feedback path is an adder of delay $d_a$ plus a register of delay $d_r$, then an interval of $n$ cycles admits a recurrence chain of $n \cdot T$ where $T$ is the period. For a 32-bit accumulation, a single adder’s delay is small relative to a fast period, so an interval of one is achievable. For a floating-point accumulation the chain is longer, and the tool either increases the interval or inserts a tree that changes the arithmetic, which changes the result.

Memory is where the abstraction leaks

An array in the source is a variable with a name. In hardware it can be registers, a distributed memory, or a block RAM, and the choice has consequences that are invisible at the source level. The default is usually inferred from the access pattern: an array with one read and one write per iteration and no more ports than a block offers maps to block RAM.

When a loop is pipelined with an interval of one, every iteration accesses the array in the same cycle, so the array must supply one element per cycle. A block RAM does supply one element per cycle, but only at one address per port. Two reads in one iteration need a memory with two read ports, which the block may or may not provide, or the array must be split into banks so that the two elements are in different banks. Bank design is a source-level decision: an array of size $N$ split into $P$ banks gives $P$ parallel accesses provided the access indices distribute across banks, and a loop that strides by a multiple of the bank count defeats the split entirely.

The same reasoning applies to writes. A pipelined loop that writes every iteration needs the memory to accept one write per cycle, which is usually fine, but a loop with a conditional write and a read in the same cycle may need a bypass to return the newly written value, which is the read-during-write issue described in block RAM primitives and memory inference.

Interfaces are inferred too

A function with pointer arguments becomes a module with a port per pointer, and the tool must decide how those ports are driven. The choice is a protocol, and the default may not be the one the rest of the system speaks.

The two common forms are a memory-mapped interface, where the module exposes registers that a bus master reads and writes, and a streaming interface, where data arrives on a handshake with a valid and ready signal. A third form is a block-level handshake in which a start signal begins an execution and a done signal indicates completion. The distinction matters because the memory-mapped form serializes access through the bus and is easy to integrate, while the streaming form can sustain one element per cycle but requires the surrounding logic to implement the handshake.

The correctness hazard is that the interface’s latency becomes part of the contract. A function that reads an input, computes for ten cycles, and writes an output has a ten-cycle latency from the input being available to the output being valid. If the interface asserts that the output is valid only when a done signal fires, the consumer must wait for it; if the consumer assumes a fixed latency, a change in the schedule from one tool run breaks the system. Pinning the schedule with an explicit latency constraint, or using a handshake protocol that does not depend on it, is the only durable choice.

Where high-level synthesis is the right tool

The productive case is a datapath with regular structure and a clean dataflow: filters, transform kernels, arithmetic over arrays, packing and unpacking, table lookup. In those cases the source’s loop structure maps onto the pipeline, the array mapping is predictable, and the designer’s effort goes into the algorithm and the bandwidth analysis rather than into hand-instantiating register arrays.

The unproductive case is control-dominated logic: a protocol state machine, an arbiter, a scheduler with priority rules. In those, the tool must infer a state machine from control flow, and the mapping from the source to the cycles is not something the source expresses. The result is a circuit whose cycle count and resource use are difficult to predict, and whose modification is difficult to reason about. Control logic written directly in an HDL is clearer and smaller.

The middle case, where the tool is used but the source is written for it, is the one that needs discipline. Loop bounds that are compile-time constants allow full unrolling; variable bounds force a counter and prevent unrolling; pointer aliasing prevents the tool from proving that two arrays are distinct, which blocks parallel access and is why the tool’s pragmas exist to assert non-aliasing. The source is not portable C in the sense the compiler assumes; it is C written to describe hardware, and the constraint is that the description must carry the information the scheduler needs.

The generated RTL then enters the same implementation flow as hand-written logic, and it meets the same limits. Its schedule may be optimal at the estimated delays and poor after placement, its array banking may concentrate accesses on one memory block, and its control may create a wide fanout. Reading the implementation reports, not the synthesis estimates, is what tells whether the abstraction held, and the arithmetic they report is in static timing analysis.