Pipelining and Retiming in High Speed Digital Logic Designs

Consider figure 1.1, which pretty much describes the basic block of any digital logic design. The maximum allowable frequency that can be used in a circuit design is given by the equation
Fmax=1/Tmin -------(i)
where Tmin is calculated as
Tmin=Tc-q + Tcomb + Tsu-------(ii)

Note: There may be many such circuits as figure 1.1 in complex system design with variable Tcombs. In such cases, the highest Tcomb is used to determine Tmin and the path associated with it is called critical path.

Tc-q::The time taken by the input at the flip-flop, D ,to give output Q after the trigger edge of the clock.

Tcomb::Total delay of combinational logic in between the flip-flops.

Tsu::The minimum time interval for which the input of the flip-flop must remain stable before the trigger edge of the clock.

Let us take an example:
Suppose, Tc-q=5ns, Tcomb=15ns, Tsu=5 ns
then, Tmin=25ns and thus Fmax=40 Mhz.

In digital systems, processing is basically done by the combinational logic while the flip-flops help to control the data and the processing. As technology advances, processing becomes much more complex. But as the processing becomes more and more complex, the maximum allowable frequency decreases accordingly. Thus realizing high speed Digital system design with large combinational blocks using the basic block as in figure 1.1 is not possible. This is when we need to rearrange the circuit so that high frequency can still be used.Two major techniques are widely followed in high speed digital logic design::
(i) Pipelining
(ii) Retiming

Pipelining::
Pipelining is a process by which a normal large combinational logic block between two flip-flops is broken down into two or more pieces. Then, flip-flops are inserted to isolate those pieces. When applied for critical paths, Tmin decreases, thus allowing us to use higher operational frequencies. If we try to pipeline the circuit described by figure 1.1, we would get a result as described by figure 1.2.

Suppose , Tcomb(2)=6ns
and Tcomb(3)=9ns

From the figure,
The critical path (highest path delay) in the circuit is the path from 2nd D f/f to 3rd D f/f. Thus,

Tmin= Tc-q + Tcomb(3) + Tsu
=19ns
This gives, Fmax= 52.6 Mhz.
This way, efficient pipelining can be used to increase the maximum permissible frequency for a digital design.

Retiming::
Retiming is a much complex technique, which is generally done by the help of software. Consider a circuit where the delay of combinational blocks vary greatly. Then, inspite of the fact that there are paths with low delays, we would have to consider the maximum Tcomb (i.e. of critical path) in order to obtain Tmin. This will give us comparatively low maximum allowable frequency. An example is given in Figure 1.3.


Suppose, Tcomb(4)=3ns
and Tcomb(5)=12ns

Then, Tmin=Tc-q + Tcomb(5) + Tsu
=22ns
This gives, Fmax=45.4 Mhz.



We can redistribute the combinational logic blocks in such a way that the variance in their delays is minimized. If we do this for the circuit described by Figure 1.3 we can, at the best, get two blocks of 7.5 ns.
Then, Fmax would be 57.1 Mhz.

Note: The example denotes an ideal case. In general, after rearranging, Tcomb(4) will be > =3ns and Tcomb(5) will be < =12ns.

Even if we don't get this optimal result, any decrement in the critical path delay due to this process of redistribution will enable us to use higher frequencies.This procedure is termed as Retiming.

Although the final hardware may increase due these procedures, we gain a lot in terms of maximum allowable frequency. And in case of high speed digital logic designs, the latter is given priority.