Retiming and Balancing the Stages of a Datapath

A pipeline’s clock period is set by its slowest stage. If the five stages of a datapath take 150, 100, 300, 250, and 100 ps, the machine runs at the rate of the 300 ps stage and the other stages idle for part of every cycle. Fixing that is not a matter of splitting the slow stage: the boundary between stages is a register, and moving logic across a register is a transformation with legality conditions. The transformation is called retiming, and it is the reason a synthesized pipeline’s stage boundaries rarely correspond to the conceptual stages a textbook describes.

Retiming is register motion, not logic duplication

The operation is simple to state: move a register from the output of a block of logic to its input, or the reverse, without changing the function computed at the outputs. In a synchronous circuit, a register on every path into a logic block can be pushed back to every path out of it, provided every path is covered. If some path into the block has no register, pushing back would remove the register from that path and create a combinational path from an earlier register, which changes the circuit’s timing behaviour but not its function.

The legality condition is therefore about path coverage, not about logic. A retiming that moves a register across a gate must add a register to every fanout of that gate and remove one from every fanin. If any fanin lacks a register, the move is illegal because it would shorten that path’s latency without compensation.

/* A combinational node in a timing graph, with the number of registers on each
   incoming edge. Retiming forward across `n` requires at least one register on
   every incoming edge and adds one register to every outgoing edge. */
struct node {
    int  delay;                 /* combinational delay of this node's logic */
    int  n_in, n_out;
    int *in_regs;               /* registers on each incoming edge */
    int *out_regs;              /* registers on each outgoing edge */
};

int can_retime_forward(const struct node *n)
{
    for (int i = 0; i < n->n_in; i++)
        if (n->in_regs[i] == 0)
            return 0;           /* an unregistered input would lose its path */
    return 1;
}

This local view is the primitive. The global problem is to choose a register count for every edge in the circuit such that no cycle’s register count goes negative and the longest register-to-register path is minimized. Leiserson and Saxe formulated it as a minimum-cost flow problem, which is what makes retiming tractable rather than combinatorial: the constraint that every cycle retain its total register count is a circulation constraint, and the objective is a piecewise-linear function of the edge labels.

Why the naive partition does not converge

The obvious approach is to split the slowest stage in half and repeat. It fails for two reasons.

First, splitting a stage adds a register, and the register’s own delay is part of the new clock period. If the slow stage is 300 ps and the register costs 25 ps, splitting it into two 150 ps halves gives a period of 175 ps, not 150 ps. Splitting again gives 100 ps of logic plus 25 ps of register, which is 125 ps, and again gives 75 plus 25, which is 100 ps. The series converges to the register delay plus the smallest splittable logic block, and each step yields a smaller improvement than the last. The arithmetic from deep pipelines and diminishing returns applies to a single stage exactly as it applies to the whole pipeline.

Second, splitting is constrained by the logic’s structure. A 32-bit adder cannot be split at an arbitrary point without changing its carry propagation; a split that puts the carry chain across a register either breaks the function or requires the carry to be computed twice. The legal split points are where the logic has a natural register boundary, such as between the multiplier’s partial-product generation and its reduction tree, or between the reduction tree and the final adder. A stage with no legal split point cannot be shortened by retiming at all; it can only be made faster by changing the logic, which is a different activity.

Balancing against a fixed clock

The realistic problem is not “minimize the period given a stage count” but “fit every stage into a given period.” The two are duals, and the second is the one that arises when a clock frequency has been chosen for other reasons, such as an interface the chip must meet.

In that formulation, each stage has a slack: the period minus its delay minus the register overhead. Positive slack means the stage could absorb more logic; negative slack means it cannot meet the clock and must be split or its logic restructured. Balancing is the process of moving logic from stages with negative slack to stages with positive slack, subject to retiming legality.

The process is iterative because moving logic changes the delays on both sides. A block moved from a critical stage into a stage with slack reduces the critical path but increases the receiving stage’s delay, which may create a new critical path. The fixed point is reached when no legal move reduces the maximum stage delay, which is a local optimum rather than a global one. The gap between the local and global optima is why retiming is usually run with several starting partitions and the best result kept.

A useful diagnostic at each iteration is the ratio of the critical stage’s delay to the period. A design whose critical stage is at 95 percent of the period and whose fastest stage is at 40 percent has a large balancing opportunity; one whose stages are all within 10 percent of each other has none, and further effort should go into the logic rather than the partition.

Clock skew as a deliberate imbalance

There is a second way to shift time between adjacent stages, and it operates on the clock rather than on the logic. If the clock arrives at stage k+1’s registers later than at stage k’s, the path from k to k+1 has more time and the path from k+1 to k+2 has less. Deliberately skewing the clock this way is called useful skew, and it is mathematically a retiming: it moves time across a register boundary without moving logic.

The constraint is that skew cannot be negative, and the amount available is bounded by the clock distribution’s ability to deliver different arrival times without violating the flop’s hold requirement. A flop that receives its clock too early relative to its data can capture the previous cycle’s value, which is a hold violation, and hold violations cannot be fixed by slowing the clock. Useful skew therefore trades setup margin on one path for hold margin on the adjacent one, and the trade is bounded on both sides.

The practical consequence is that a pipeline’s stage boundaries are not simply a partition of the logic. They are a partition plus a skew assignment, and the two are optimized together. A design that balances the logic perfectly and ignores skew leaves performance on the table; a design that skews aggressively without checking hold margins produces a chip that fails at low temperature or high voltage, which is the worst kind of failure to diagnose.

Latency, throughput, and the cost of an unbalanced stage

An unbalanced pipeline has a specific signature in performance counters: the machine’s throughput is lower than its issue width suggests, and the gap is not explained by hazards. If one stage takes twice the period of the others, the whole pipeline runs at half rate and every instruction pays for it, even though the average stage utilisation is low.

The fix has a cost that is easy to state and hard to accept. Splitting the slow stage into two halves adds a pipeline stage, which adds one cycle of latency to every instruction and increases the branch penalty by one, per the argument in control hazards and branch penalties. The throughput gain must exceed the resulting CPI increase for the split to be worth it, which means a stage that is 20 percent slower than its neighbours is usually not worth splitting, while one that is 50 percent slower usually is.

Retiming without splitting has no such cost: it moves logic between existing boundaries and leaves the stage count and the latency unchanged. That is why retiming is preferred whenever it is legal, and why the legality conditions are worth the effort of checking. The transformations that move logic across a register are the only ones that improve timing without changing the architectural contract.

Where the abstraction breaks

Two assumptions underlie the treatment above, and both fail on real designs.

The first is that a stage’s delay is a single number. It is not: the delay depends on which inputs change, on the values being propagated, and on the parasitic capacitance of the wires connecting the logic. A stage whose critical path runs through a 32-bit carry chain has a different delay for different operand values, and the number used for balancing is the worst case over all of them. Static timing analysis computes that worst case over the paths it can enumerate, and the paths it cannot enumerate are the source of post-silicon surprises.

The second is that registers are free to place anywhere. In practice a register inserted at an arbitrary point in a datapath creates a wire crossing that may be longer than the logic it separates, and the wire delay can exceed the logic delay it was meant to split. On modern processes the wire delay between distant blocks is frequently the dominant term in a stage’s delay, which means the useful retimings are the ones that move logic toward its data sources rather than the ones that minimize the logic per stage. Floorplanning and retiming are therefore coupled: a partition that is optimal on paper can be infeasible once the blocks are placed, and the placement can be adjusted to make it feasible.

The last limitation is verification. Retiming preserves the function of a combinational circuit but changes the number of cycles between input and output on every path. A design whose external interface assumes a specific latency cannot be retimed across that interface, and a design whose internal protocol assumes a fixed number of cycles between two events cannot be retimed across those events either. This is why retiming is applied inside a pipeline stage’s logic and rarely across the architectural boundary: the boundary is where latency is part of the contract, and the contract is what the software was written against.