Retiming, Pipelining, and Register Balancing in the Fabric

When a path fails timing, there are three honest responses: shorten the logic, give the path more time, or make the path’s endpoints closer together physically. Retiming attacks the second by moving a register from one side of a block of logic to the other, which changes the delay on each of the two resulting paths without changing the circuit’s external behaviour, provided the register is one of a set that can be shifted collectively.

The transformation and its invariant

Consider a register feeding a piece of combinational logic that feeds another register. Moving the register from the input side to the output side shifts the boundary between clock cycles: the logic now executes in a different cycle, and the register holds its result. For a feed-forward path with only one path between the two endpoints, the move is safe and the overall latency from input to output is unchanged, because the same number of registers remains in series.

The difficulty appears when the register’s output fans out to more than one destination. Moving the register forward requires moving a register on every fanout path, or the paths that did not get a register now see data one cycle earlier than before, which corrupts the pipeline’s alignment. This is why the textbook formulation of retiming treats the problem as a global one: assign a non-negative integer label to each vertex of the netlist representing a number of registers, and require that the number of registers on every cycle of the graph is invariant. Leiserson and Saxe showed that the problem can be solved as a minimum-cost flow or linear program over those labels, minimizing the maximum weighted delay of any path.

In a fabric where registers are already present at every cell, retiming has an unusual character. The registers are not free-standing objects to be inserted; they are the flip-flops inside the logic cells, and moving one across a lookup table is a matter of rewriting the cell’s function and rewiring the table beside it. That is exactly what tools called register balancing do: they pull a register through a layer of logic, duplicating it across a fanout if the function permits, and the netlist’s LUT count and register count stay roughly constant.

Why the fabric is unusually friendly to the idea

An ASIC retiming changes the placement of the register, and the register’s physical location must then be re-placed and its clock tree reconnected, which can invalidate the timing that motivated the move. In an FPGA the register is inside the cell, the cell is where the LUT already was, and the clock network reaches every cell equally. Moving a register across a LUT therefore changes nothing about the clock’s reach and only changes the routing between the LUT and the neighbouring cells. The transformation is close to free at the implementation level, which is why synthesis tools apply it aggressively and why a substantial amount of the frequency improvement available on a fabric comes from register movement rather than from logic restructuring.

There is a second, characteristically FPGA-specific form of the same idea: moving a register into a hardened block. A memory, a multiplier, or a digital signal processing slice has input and output registers that the tool can enable to absorb the surrounding register. Pushing a register into the block shortens the path into the block and removes a route, and pulling one out can balance the paths on either side. Because the internal registers of these blocks have much shorter paths to the block’s own logic than any external route, this class of movement is often worth more than several LUT-level retimings.

# Ask synthesis to balance registers rather than only map them.
# Vendor option names differ; the equivalent is a synthesis setting,
# not a place-and-route directive.
set_property -name {STEPS.SYNTH_DESIGN.ARGS.RETIMING} \
             -value true -objects [get_runs synth_1]

The transformation has limits that come from the fabric’s structure rather than from the algorithm. A register cannot be moved across a block RAM that is read and written in the same cycle, because the block’s internal behaviour is not a simple pipeline stage. It cannot be moved through a cell whose output has a defined power-up state that the design depends on. And it cannot be moved across a boundary marked as a keep, because the boundary was marked precisely to prevent it.

Pipelining as a deliberate act

Automatic retiming balances existing registers. Pipelining adds new ones, which changes the design’s latency and therefore cannot be done without the designer’s consent. The distinction matters because most failures in a design at a target frequency require more than balancing: they require inserting stages into a path that has none.

The arithmetic of a pipeline stage is straightforward. Splitting a combinational path of delay $d$ into two stages of $d_1$ and $d_2$ reduces the critical path to $\max(d_1, d_2)$, so a balanced split roughly halves it. The overhead is the register’s own clock-to-out plus setup, which in a fabric is a fraction of a nanosecond but not negligible, and any routing the split introduces. The gain is therefore sublinear in the number of stages: each split adds a fixed cost, and splitting a path into $n$ stages yields a critical path of about $d/n$ plus the register cost, which stops improving once $d/n$ approaches that cost.

For a path that crosses a wide combinational function, the natural split points are where the logic already has a boundary: the output of an adder before the comparison that consumes it, the reduction tree of a multiplier before the final add, the address calculation before the memory access. Splitting at arbitrary points forces the tool to break a lookup table’s function across cells, which adds routing and can add a logic level.

The cases where it does not help

Retiming cannot improve a loop. A feedback path with no register inside it, such as a comparator whose output feeds back into its own input through a multiplexer, has a critical path that retiming cannot shorten, because there is nowhere to place a register that is not itself inside the cycle. The remedy is a structural change: break the loop by inserting a register and accepting the additional cycle of latency, or restructure the computation so the feedback path is shorter, or run the loop at a lower rate with an enable.

The same applies to a path between two hard blocks that both must be accessed in the same cycle, such as a memory write whose address is computed by the logic that also produced the data. Retiming can move registers within the address computation but cannot insert one before the memory without delaying the write.

Retiming also changes power behaviour and simulation correlation. A retimed design simulates with different intermediate values than the pre-synthesis source, which makes waveform comparison between RTL and gate-level simulation harder, and it can move registers into positions where the tool’s own timing constraints assume a specific structure. Designs that use dont_touch markers or that rely on a specific register-to-register relationship across a module boundary can therefore retime differently than intended.

The interaction with placement

Because the fabric’s delays are dominated by routing, a retiming that balances the logic perfectly can fail if the balanced stages are far apart. The placer then has two short paths instead of one long one, but the long one may now run between regions, and the crossing’s delay is unpredictable before placement. This is why retiming after placement is a different and riskier operation than retiming before it: moving registers post-placement invalidates the placement’s assumptions and requires re-placement of the affected cells.

The practical sequencing is to let synthesis retime and balance, then constrain, then place, then examine the post-route worst paths and pipeline deliberately where the report shows structure rather than routing as the cause. The diagnostic distinction between the two causes is the first thing to make in the report, and it is described in static timing analysis. When the report shows routing as the cause, no amount of register movement substitutes for a floorplan that puts the communicating logic near each other, which is the subject of placement, routing, and congestion.

A last consideration is that latency added by pipelining propagates into the design’s protocol. A pipelined arithmetic unit that now takes four cycles instead of two changes the handshake timing, the depth of the buffer that feeds it, and any assumption in the surrounding control logic about when its result is valid. The register insertion is cheap; the protocol change it forces is the expensive part, and it is the reason pipelining decisions belong to the architecture rather than to the final timing-closure pass.