Retiming

Last updated January 01, 2025

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. 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 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. There is a proof that this preserves the output functionality.^[2]

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 $T$ can be checked in one of several ways. The linear program below is feasible if and only if $T$ is a feasible clock period. Let $W(u,v)$ be the minimum number of registers along any path from $u$ to $v$ (if such a path exists), and $D(u,v)$ is the maximum delay along any path from $u$ to $v$ 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 $W$ and $D$ matrices.

Given	$w(e),W(u,v),D(u,v)$ and a target clock period $T$
Find	$r(v):V\to \mathbb {Z}$
Such that
	$r(u)-r(v)$	$\leq w(e)$
	$r(u)-r(v)$	$\leq W(u,v)-1$ if $D(u,v)>T$

Minimizing the clock period with MILP

Alternatively, feasibility of a clock period $T$ can be expressed 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 is feasible.

Given	$w(e),d(v)$ and a target clock period $T$
Find	$r(v):V\to \mathbb {Z}$ and $R(v):V\to {\mathcal {R}}$
Such that
	$r(v)-R(V)$	$\leq -d(v)/T$
	$R(v)-r(v)$	$\leq 1$
	$r(u)-r(v)$	$\leq w(e)$
	$R(u)-R(v)$	$\leq w(e)-d(v)/T$

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

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

Notes

↑ Charles E. Leiserson, Flavio M. Rose, JamesB. Saxe (1983). "Optimizing Synchronous Circuitry by Retiming". Third Caltech Conference on Very Large Scale Integration. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Charles E. LeisersonJames B. Saxe (June 1991). "Retiming synchronous circuitry". Algorithmica. 6 (1). Springer: 5–35. doi:10.1007/BF01759032. S2CID 18674287.
1 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.
↑ M. C. Papaefthymiou, Asymptotically efficient retiming under setup and hold constraints , IEEE/ACM International Conference on Computer-Aided Design, 1998.

Related Research Articles

<span class="mw-page-title-main">Digital electronics</span> Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics which work primarily with analog signals. Despite the name, digital electronics designs includes important analog design considerations.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Algorithm for finding shortest paths

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history. This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

In electronics and especially synchronous digital circuits, a clock signal is an electronic logic signal which oscillates between a high and a low state at a constant frequency and is used like a metronome to synchronize actions of digital circuits. In a synchronous logic circuit, the most common type of digital circuit, the clock signal is applied to all storage devices, flip-flops and latches, and causes them all to change state simultaneously, preventing race conditions.

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel, but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in time. The algorithm was first published by Yefim Dinitz in 1970, and independently published by Jack Edmonds and Richard Karp in 1972. Dinitz's algorithm includes additional techniques that reduce the running time to $.$

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

In electronic instrumentation and signal processing, a time-to-digital converter (TDC) is a device for recognizing events and providing a digital representation of the time they occurred. For example, a TDC might output the time of arrival for each incoming pulse. Some applications wish to measure the time interval between two events rather than some notion of an absolute time.

In digital circuit design, register-transfer level (RTL) is a design abstraction which models a synchronous digital circuit in terms of the flow of digital signals (data) between hardware registers, and the logical operations performed on those signals.

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.

In digital electronics, a synchronous circuit is a digital circuit in which the changes in the state of memory elements are synchronized by a clock signal. In a sequential digital logic circuit, data is stored in memory devices called flip-flops or latches. The output of a flip-flop is constant until a pulse is applied to its "clock" input, upon which the input of the flip-flop is latched into its output. In a synchronous logic circuit, an electronic oscillator called the clock generates a string (sequence) of pulses, the "clock signal". This clock signal is applied to every storage element, so in an ideal synchronous circuit, every change in the logical levels of its storage components is simultaneous. Ideally, the input to each storage element has reached its final value before the next clock occurs, so the behaviour of the whole circuit can be predicted exactly. Practically, some delay is required for each logical operation, resulting in a maximum speed limitations at which each synchronous system can run.

Asynchronous circuit is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit which indicates a completion of a set of instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

Clock skew is a phenomenon in synchronous digital circuit systems in which the same sourced clock signal arrives at different components at different times due to gate or, in more advanced semiconductor technology, wire signal propagation delay. The instantaneous difference between the readings of any two clocks is called their skew.

Static timing analysis (STA) is a simulation method of computing the expected timing of a synchronous digital circuit without requiring a simulation of the full circuit.

In integrated circuit design, dynamic logic is a design methodology in combinational logic circuits, particularly those implemented in metal–oxide–semiconductor (MOS) technology. It is distinguished from the so-called static logic by exploiting temporary storage of information in stray and gate capacitances. It was popular in the 1970s and has seen a recent resurgence in the design of high-speed digital electronics, particularly central processing units (CPUs). Dynamic logic circuits are usually faster than static counterparts and require less surface area, but are more difficult to design. Dynamic logic has a higher average rate of voltage transitions than static logic, but the capacitive loads being transitioned are smaller so the overall power consumption of dynamic logic may be higher or lower depending on various tradeoffs. When referring to a particular logic family, the dynamic adjective usually suffices to distinguish the design methodology, e.g. dynamic CMOS or dynamic SOI design.

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

In electronics, flip-flops and latches are circuits that have two stable states that can store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will output its state. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.

Unfolding is a transformation technique of duplicating the functional blocks to increase the throughput of the DSP program in such a way that preserves its functional behavior at its outputs. Unfolding was first proposed by Keshab K. Parhi and David G. Messerschmitt in 1989. Unfolding in general program is as known as Loop unrolling.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

References

Leiserson, 1C. E.; Saxe, J. B. (1983). "Optimizing Synchronous Systems". Journal of VLSI and Computer Systems. 1 (1): 41–67.{{cite journal}}: CS1 maint: numeric names: authors list (link)

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Charles E. Leiserson, Flavio M. Rose, JamesB. Saxe (1983). "Optimizing Synchronous Circuitry by Retiming". Third Caltech Conference on Very Large Scale Integration. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[one-2] Charles E. LeisersonJames B. Saxe (June 1991). "Retiming synchronous circuitry". Algorithmica. 6 (1). Springer: 5–35. doi:10.1007/BF01759032. S2CID 18674287.

[two-3] 1 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.

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

[1]

[2]

[3]

[4]