Retiming is the technique of moving the structural location of latches or registers in a digital circuit to improve its performance, area, and/or power characteristics in such a way that preserves its functional behavior at its outputs.
Retiming was first described by Charles E. Leiserson and James B. Saxe in 1983.
[1] The technique uses a directed graph where the vertices represent asynchronous combinational blocks and the directed edges represent a series of registers or latches (the number of registers or latches can be zero).
Each vertex has a value corresponding to the delay through the combinational circuit it represents.
In all cases, if the rules are followed, the circuit will have the same functional behavior as it did before retiming.
The initial formulation of the retiming problem as described by Leiserson and Saxe is as follows.
whose vertices represent logic gates or combinational delay elements in a circuit, assume there is a directed edge
The goal in retiming is to compute an integer lag value
[2] The most common use of retiming is to minimize the clock period.
can be expressed as a mixed-integer linear program (MILP).
A solution will exist and a valid lag function
The initial paper includes extensions that allow the consideration of fan-out sharing and a more general delay model.
[4] Retiming has found industrial use, albeit sporadic.
Its primary drawback is that the state encoding of the circuit is destroyed, making debugging, testing, and verification substantially more difficult.
Finally, the changes in the circuit's topology have consequences in other logical and physical synthesis steps that make design closure difficult.
Clock skew scheduling is a related technique for optimizing sequential circuits.
Whereas retiming relocates the structural position of the registers, clock skew scheduling moves their temporal position by scheduling the arrival time of the clock signals.
The lower bound of the achievable minimum clock period of both techniques is the maximum mean cycle time (i.e. the total combinational delay along any path divided by the number of registers along it).