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 [1]. In electronics, a latch is data storage device used to store information in asynchronous sequential logic systems. ... Digital circuits are electric circuits based on a number of discrete voltage levels. ... Power optimization refers to the use of electronic design automation tools to optimize (reduce) the power consumption of a digital design, while preserving the functionality. ... Charles E. 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. ...

General Formulation

The initial formulation of the retiming problem as described by Leiserson and Saxe is as follows. Given a directed graph G: = (V,E) whose vertices represent logic gates or combinational delay elements in a circuit, assume there is a directed edge e: = (u,v) between two elements that are connected directly or through one or more registers. Let the weight of each edge w(e) be the number of registers present along edge e in the initial circuit. Let d(v) be the propagation delay through vertex v. The goal in retiming is to compute an integer lag value r(v) for each vertex such that the retimed weight w_r(e): = w(e) + r(v) − r(u) of every edge is non-negative. The proof that this preserves the output functionality is present in [1]. This article just presents the basic definitions. ... A logic gate is an arrangement of electronically-controlled switches used to calculate operations in Boolean algebra. ... In computer science, the propogation delay is the amount of time starting from when the input to a logic gate becomes stable and valid to the time that the output of that logic gate is stable and valid. ...

Minimizing the Clock Period with MILP

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). One of several possible methods to test for the feasibility of a clock period is to formulate the retiming program as a mixed-integer linear program (MILP). A solution will exist and a valid lag function r(v) will be returned if and only if the period if feasible. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...

Given	w(e),d(v) and a target clock period T
Find	and
Such that	r(v) − R(V)
	R(v) − r(v)
	r(u) − r(v)
	R(u) − R(v)

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 [2], load-dependent delay models [2], and hold constraints [3].

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 circuits topology has consequences in other logical and physical synthesis steps that make design closure difficult. 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. ...

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).

References

[1] C. E. Leiserson, J. B. Saxe, "Retiming Synchronous Circuitry," Algorithmica, Vol. 6, No. 1, pp. 5-35, 1991.

[2] K. N. Lalgudi, M. C. Papaefthymiou, "Retiming edge-triggered circuits under general delay models," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.16, no.12, pp.1393-1408, Dec. 1997.

[3] M. C. Papaefthymiou, "Asymptotically efficient retiming under setup and hold constraints," IEEE/ACM International Conference on Computer-Aided Design, 1998.

See Also

• Logic Synthesis
• Electronic Design Automation