Retiming

The idea

Registers are movable. Pushing a register backward through a gate (from its output to all its inputs) or forward likewise leaves every input-output behavior of the circuit unchanged, only the internal pipeline alignment shifts. Retiming asks: what assignment of register moves minimizes the clock period? Leiserson and Saxe formalized it on a graph whose edges carry register counts w(e) and whose nodes carry gate delays: a retiming assigns each node an integer lag r(v), and each edge's register count becomes

• w(e) registers originally on edge e
• w'(e) registers on edge e after retiming
• r(v) integer lag assigned to node v: how many registers moved across it

Legality plus a target period T translate into difference constraints, non-negative registers everywhere, and at least one register on any path whose combinational delay exceeds T. Difference-constraint systems are shortest-path feasibility (Bellman-Ford detects the negative cycle that means 'impossible'), so the minimum achievable T is found exactly by binary search over T with a feasibility solve at each step, with the classic W and D matrices organizing path delays.

Caveats

Function is preserved; everything else needs care: initial state must be recomputed and may not exist for a given move set, reset and scan logic constrain moves, verification tools must be told (sequential rather than combinational equivalence), and delays on real chips depend on the placement the retimer just changed. Hence its practical home: pipeline balancing during synthesis with conservative scopes, and FPGA (Field-Programmable Gate Array) flows, where the regular fabric keeps post-move delays predictable and architectures with many registers make moves cheap.

Where you meet it today

Synthesis options (retime), FPGA compilers doing it aggressively by default, and the theory course, where it is the standard example of a layout-adjacent problem solved exactly by graph algorithms.