Retiming is a powerful technique for optimizing sequential circuits. The transparent nature of level sensitive latches enables level-clocked circuits to operate faster and require fewer memory elements than edge-triggered circuits. However, this transparency makes the operation of level-clocked circuits very complex, and optimization of level-clocked circuits is a difficult task. This work presents efficient algorithms for retiming large level-clocked circuits. To provide us with a simpler view of the operation of level-clocked circuits, we present the relationship between retiming and clock skew optimization. We then utilize this relationship to develop efficient retiming algorithms for period and area optimization. For period optimization, we present an algorithm which produces near-optimal results, but is significantly faster than the traditional algorithms. In this approach, we first calculate the best possible clock period and the amount of motion required for each latch. The latches are then relocated in an attempt to achieve this period. Area, as measured by the number of latches in the circuit can be optimized by solving a linear program. We apply efficient pruning techniques to reduce the size of this linear program, while preserving optimality. Since generating the linear program is a major part of the computational requirements of minarea retiming, we present techniques for efficient generation of the reduced linear program. This enables us to perform area optimization of large circuits clocked by symmetric multiphase clocks in very reasonable time, without sacrificing optimality. We present results on circuits with up to 56000 gates, performing period optimization in under 20 s and area optimization in under 1.5 h.

Delay-constrained area optimization is an important step in synthesis of VLSI circuits. Minimum area (minarea) retiming is a powerful technique to solve this problem. The minarea retiming problem has been formulated as a linear program; in this work we present techniques for reducing the size of this linear program and efficient techniques for generating it. This results in an efficient minarea retiming method for large level-clocked circuits (with tens of thousands of gates).

Retiming, introduced by Leiserson and Saxe (1983, 1991), is a powerful transformation of circuits that preserves functionality and improves performance. The ASTRA algorithm proposed an alternative view of retiming using the equivalence between retiming and clock skew optimization and also presented a fast algorithm for minimum period (minperiod) retiming. Since minperiod retiming may significantly increase the number of flip-flops in the circuit, minimum area (minarea) retiming is an important problem. Minarea retiming is a much harder problem than minperiod retiming, and previous techniques were not capable of handling large circuits in a reasonable time. This work defines the relationship between the Leiserson-Saxe and the ASTRA approaches and utilizes it for efficient minarea retiming of large circuits. The new algorithm, Minaret, uses the same basis as the Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is incorporated to reduce the number of variables and constraints generated in the problem. This allows minarea retiming of circuits with over 56 000 gates in under 15 min.

The concept of improving the timing behavior of a circuit by relocatingflip-flops is called retiming and was first presented by Leisersonand Saxe. The ASTRA algorithm proposed an alternativeview of retiming using the equivalence between retiming and clockskew optimization. This work defines the relationship betweenthe Leiserson-Saxe and the ASTRA approaches and utilizes it tosolve the problem of retiming for minimum area. The new algorithm,Minaret, uses the linear programming formulation of theLeiserson-Saxe approach. The underlying philosophy of the ASTRAapproach is incorporated to reduce the number of variablesand constraints in the linear program. This reduction in the sizeof the linear program makes Minaret space and time efficient, enablingminimum area retiming of circuits with over 56,000 gates inunder 15 minutes.

Traditional minimum area retiming algorithms attempt to achieve their prescribed objective with no regard to maintaining the initial state of the system. This issue is important for circuits such as controllers, and our work addresses this problem. The procedure described generates bounds on the retiming variables that guarantee an equivalent initial state after retiming. A number of possible sets of bounds can be derived, and each set is used to solve a minimum area retiming problem that is set up as a 0/1 mixed integer linear program, using a new technique that models the maximal sharing of flip-flops at latch outputs. The best solution is found through enumeration of these sets, terminated on the achievement of a calculated lower bound. Experimental results show that after a small number of enumerations, optimal or near-optimal results are achievable.

A new approach for fast retiming of level-clocked circuits is presented. The method relies on the relation between clock skew and retiming, and computes the optimal skew solution to translate it to a retiming. Since clock skew optimization operates on the latches (rather than the gates as in conventional retiming), it is much faster because of a smaller problem size; the translation to the retiming solution is computationally cheap. The minimum period retiming for each of the ISCAS89 circuits was obtained within minutes by this algorithm.