Design Feature: February 17, 1994

Retiming is a basic technique for modifying digital circuits' clocking behavior without changing the circuits' functionality. Because the sequential part of many designs involves flip-flops, you can retime a circuit by adding, deleting, or shifting flip-flops in the basic circuit until you achieve desired timing results. The goal of retiming a circuit is to achieve a desired clock rate and simultaneously reduce the circuit density by using a minimum number of flip-flops. In addition, retiming a circuit can create a pipeline architecture by adding or deleting flip-flop stages.

Retiming should change only the timing relationship of signals by advancing or postponing exactly one or more clock cycles. A basic rule for retiming a circuit is that you can freely insert flip-flops into a network or shift a flip-flop through a node within the network (provided timing relationships between branches don't change). If you encounter a fork in the network, you may have to insert more than one flip-flop after the node to maintain the same timing relationship. If multiple network paths join at one node, you can reduce the number of flip-flops preceding the node to one flip-flop after the node.

Fig 1 illustrates this idea: (a) shows a simple node without a pipeline state; (b) inserts a flip-flop before the node, which creates a pipeline architecture. In this architecture, the flip-flop drives both nodes. However, you can maintain the same timing relationships by shifting the flip-flop through the node and adding a flip-flop in each branch after the node (c). Fig 2 illustrates how you can shift flip-flops (or registers) through a node even when the node is connected by combinatorial logic. A vertical bar depicts the flip-flops (or registers) in Fig 2 and will be a convention throughout the rest of this article.

As a practical application for retiming a circuit, consider the FIR filter in Fig 3. The output of the filter is given as

In the basic circuit of Fig 3(a), two registers delay the input signal (I) to develop the I_-1 and I_-2 signals. The time delays of the two adder blocks are in the critical path of the circuit and create a limit to the maximum-output clock frequency attainable. Using the basic rules for retiming lets you shift the registers through the nodes in the circuit, provided you maintain the equivalent timing relationships between branches.

In Fig 3(b), the rule allows registers FF1A and FF1B to replace register FF1. Register FF2 shifts to a new position in the same branch. Essentially, the functional operation of the circuit has not changed. The next step in the retiming procedure is to consolidate registers FF1A and FF1B into one register that resides between the adders (c). The final circuit (d) now has only the time delay of one adder in the critical path. The final circuit will operate at twice the frequency of the original circuit. Note that the circuit-per-formance increase occurs without any increase in circuit density.

Another example of retiming is the pipeline architecture of Fig 4. In Fig 4(b), an additional pipeline stage (FF4 and FF3) is inserted in the positions indicated relative to the original circuit (a). The result of the register addition means the time delay due to combinatorial logic halves, but the output is available one clock cycle later. A timing diagram would show that the time between clock periods for the original circuit could exceed an entire clock period due to the time delays of two combinatorial blocks. Although the output of the final circuit exceeds the clock period by one clock cycle due to the added pipeline registers, the delay between successive clock cycles is shorter than a clock period. This results because the time delay is only one combinatorial block.

Retiming techniques are not new, but today, CAD procedures handle these techniques automatically instead of manually. CAD procedures usually consist of two techniques. A postoptimizer technique relocates existing flip-flops; a design-tool technique allocates pipeline stages. Using the postoptimizer technique, you insert flip-flops (or registers) by schematic entry—or by high-level description language if using synthesis. Often the positioning of the flip-flops is not optimal.

The pipelined architecture in Fig 5(a) could have been created by synthesis or schematic entry. The example has a maximum time delay of four logic gates between the four flip-flops in the branches and the flip-flop in the output path. After design entry, you can postoptimize this design using retiming. The modified design must exhibit the same functionality as the original circuit; therefore, the number of pipeline stages between the inputs and the output must not change. This restriction is called "keeping the latency."

You have a number of ways to postoptimize this design. Fig 5(b) demonstrates one way, which minimizes chip density but maintains a maximum time delay of six logic gates. Achieve the optimized design by shifting the flip-flops in the branches through the combinatorial node to the output path. The design also achieves a power-dissipation reduction, from five to two flip-flops. Fig 5(c) shows another postoptimized design of the original circuit. By moving the four flip-flops in the input branches through the secondary branch nodes, you achieve a maximum time delay of three logic stages. The number of flip-flops decreases from five to three.

Using CAD procedures, a top-down design comprises the following steps: First, make a behavioral high-level description of the circuit. When the behavior is correct, transform the description into a Register Transfer Level (RTL) description. Manually add logical structure to the RTL description to perform gate-level synthesis; you need the additional structure because state-of-the-art gate-level-synthesis tools cannot synthesize sequential operations (except for the special case of state machines, where flip-flops are implicit in the description). Adding structure manually is tedious because it usually takes one or more iterations to meet design constraints. Fig 6 depicts the top-down procedure.

Refer to Listing 1 (see EDN BBS) for an example of the behavioral VHDL (VHSIC hardware-description language) code for a 32-bit comparator. Typical synthesis for this design's VHDL code using the LSI Logic LCA100k library results in 426 gates having an overall time delay of 21 nsec. Because the specification requires a maximum time delay of 15 nsec, the design has to be pipelined. To pipeline the design, the RTL description must be changed manually. Listing 2 (see EDN BBS) shows the resulting RTL-VHDL source code. The synthesized design results in a time delay of 11 nsec using two pipeline stages consisting of 20 flip-flops.

You can retime the design using Optima, a retiming tool from Philips Electronic Design and Tools, to create a pipeline that has exactly 15-nsec time delay. Using Optima, you can specify the time-delay constraint to be exactly 15 nsec. Optima produces a design that has one pipeline stage using eight flip-flops, which is fewer than the synthesized manual design. You could also find the optimized design that uses only one pipeline stage to achieve the shortest time delay. This design results in a time delay of 12 nsec using 17 flip-flops.

Jaap B Sondervan is a marketing manager for Philips Electronic Design and Tools in The Netherlands. Sondervan specializes in CAD-product marketing and public relations and has been with Philips for nine years. His main interests are in synthesis and test for ASICs. Sondervan has an MSC in Electronic Engineering.