Retiming

Retiming is a transformation applied to synchronous digital circuits to relocate registers across combinational logic without altering the circuit’s overall function. By changing how registers are distributed along data paths, designers can improve clock frequency, reduce area or power, and balance pipeline depth.

Conceptually, a circuit is modeled as a directed graph where nodes are combinational blocks and edges carry data between registers. A legal retiming moves a register from one side of a node to the other, adjusting the counts of registers at adjacent blocks while preserving the circuit’s external behavior for all input sequences.

Retiming is commonly used in pipeline optimization and high-level synthesis. It can increase the maximum clock rate by shortening the critical path, or reduce the number of registers to lower area and power, or balance latency across different paths. The outcome depends on the chosen retiming that satisfies timing constraints and design goals.

Limitations and history: The technique was introduced by Leiserson and Saxe in the early 1980s. In general, finding an optimal retiming with respect to a given objective is computationally challenging, and practical tools rely on heuristics or restricted models. Retiming is often used alongside other transformations such as rescheduling and register-transfer-level optimization in modern electronic design automation toolchains.