Retiming
Encyclopedia
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.
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. After doing this, one can attempt to optimize the circuit by pushing registers from output to input and vice versa - much like bubble pushing. Two operations can be used - deleting a register from each input of a vertex while adding a register to all outputs, and conversely adding a register to each input of vertex and deleting a register from all outputs. In all cases, if the rules are followed, the circuit will have the same functional behavior as it did before retiming.
whose vertices represent logic gates or combinational delay elements in a circuit, assume there is a directed edge 
between two elements that are connected directly or through one or more registers. Let the weight of each edge 
be the number of registers present along edge 
in the initial circuit. Let 
be the propagation delay
through vertex
. The goal in retiming is to compute an integer lag value 
for each vertex such that the retimed weight 
of every edge is non-negative. There is a proof that this preserves the output functionality.
The feasibility of a clock period
can be checked in one of several ways. The linear program below is feasible if and only if 
is a feasible clock period. Let 
be the minimum number of registers along any path from 
to 
(if such a path exists), and 
is the maximum delay along any path from 
to 
with W(u,v) registers. The dual of this program is a minimum cost circulation problem, which can be solved efficiently as a network problem. The limitations of this approach arise from the enumeration and size of the 
and 
matrices.
can be expressed as a mixed-integer linear program (MILP). A solution will exist and a valid lag function 
will be returned if and only if the period is feasible.
difficult.
A Safe and Complete Gate-Level Register Retiming Algorithm
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
to improve its performance, area, and/or power
Power optimization (EDA)
Power optimization is the use of electronic design automation tools to optimize the power consumption of a digital design, such as that of an integrated circuit, while preserving the functionality.-Introduction and history:...
characteristics in such a way that preserves its functional behavior at its outputs. Retiming was first described by Charles E. Leiserson
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language...
and James B. Saxe in 1983.
The technique uses a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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. After doing this, one can attempt to optimize the circuit by pushing registers from output to input and vice versa - much like bubble pushing. Two operations can be used - deleting a register from each input of a vertex while adding a register to all outputs, and conversely adding a register to each input of vertex and deleting a register from all outputs. In all cases, if the rules are followed, the circuit will have the same functional behavior as it did before retiming.
Formal description
The initial formulation of the retiming problem as described by Leiserson and Saxe is as follows. Given a directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
whose vertices represent logic gates or combinational delay elements in a circuit, assume there is a directed edge between two elements that are connected directly or through one or more registers. Let the weight of each edge be the number of registers present along edge in the initial circuit. Let be the propagation delayPropagation delay
Propagation delay is a technical term that can have a different meaning depending on the context. It can relate to networking, electronics or physics...
through vertex
. The goal in retiming is to compute an integer lag value for each vertex such that the retimed weight of every edge is non-negative. There is a proof that this preserves the output functionality.Minimizing the clock period with network flow
The most common use of retiming is to minimize the clock period. A simple technique to optimize the clock period is to search for the minimum feasible period (e.g. using binary search).The feasibility of a clock period
can be checked in one of several ways. The linear program below is feasible if and only if is a feasible clock period. Let be the minimum number of registers along any path from to (if such a path exists), and is the maximum delay along any path from to with W(u,v) registers. The dual of this program is a minimum cost circulation problem, which can be solved efficiently as a network problem. The limitations of this approach arise from the enumeration and size of the and matrices.| Given |  and a target clock period  |
|
| Find |  |
|
| Such that | ||
 |
 |
|
 |
 if  |
|
Minimizing the clock period with MILP
Alternatively, feasibility of a clock period can be expressed as a mixed-integer linear program (MILP). A solution will exist and a valid lag function will be returned if and only if the period is feasible.| Given |  and a target clock period  |
|
| Find |  and  |
|
| Such that | ||
 |
 |
|
 |
 |
|
 |
 |
|
 |
 |
|
Other formulations and extensions
Alternate formulations allow the minimization of the register count and the minimization of the register count under a delay constraint. The initial paper includes extensions that allow the consideration of fan-out sharing and a more general delay model. Subsequent work has addressed the inclusion of register delays, load-dependent delay models, and hold constraints.Problems
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. Some retimings may also require complicated initialization logic to have the circuit start in an identical initial state. Finally, the changes in the circuit's topology have consequences in other logical and physical synthesis steps that make design closureDesign closure
Design closure is the process by which a VLSI design is modified from its initial description to meet a growing list of design constraints and objectives....
difficult.
Alternatives
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).External links
A Safe and Complete Gate-Level Register Retiming Algorithm