AbstractWe investigate two strategies for reducing the clock period of a two-phase, level-clocked circuit:

clock tuning, which adjusts the waveforms that clock the circuit, andretiming, which relocates circuit latches. These methods can be used to convert a circuit with edge-triggered latches into a faster level-clocked one.We model a two-phase circuit as a graph

G= (V,E) whose vertex setVis a collection of combinatorial logic blocks, and whose edge setEis a set of interconnections. Each interconnection passes through zero or more latches, where each latch is clocked by one of the two periodic, nonoverlapping waveforms, orphases.We give efficient polynomial-time algorithms for problems involving the timing verification and optimization of two-phase circuitry. Included are algorithms for

We give fully polynomial-time approximation schemes for clock period minimization, within any given relative error epsilon > 0, by

- verifying proper timing:
O(VE) time.- minimizing the clock period by clock tuning:
O(VE) time.- retiming to achieve a given clock period when the phases are symmetric:
O(VE+V^2 lgV) time.- retiming to achieve a given clock period when either the duty cycle (high time) of one phase or the ratio of the phases' duty cycles is fixed:
O(V^3).The first two of these approximation algorithms can be used to obtain the optimum clock period in the special case where all propagation delays are integer.

- retiming and tuning when the duty cycles of the two phases are required to be equal:
O((VE+V^2 lgV) lg (V/epsilon)) time.- retiming and tuning when either the duty cycles of one phase is fixed or the ratio of the phases' duty cycle is fixed:
O(V^3 log(V/epsilon)) time.- simultaneous retiming and clock tuning with no conditions on the duty cycles of the two phases:
O(V^3 (1/epsilon) lg(1/epsilon) + (VE+V^2 lgV) lg(V/epsilon)) time.We generalize most of the results for two-phase clocking schemes to simple multiphase clocking disciplines, including ones with overlapping phases. Typically, the algorithms to verify and optimize the timing of

k-phase circuitry are at most a factor ofkslower than the corresponding algorithms for two-phase circuitry.Our algorithms have been implemented in TIM, a timing package for two-phase, level-clocked circuitry developed at MIT.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: B.6.3 [Logic Design]: Design Aids; B.7 [Integrated Circuits]; F.2 [Analysis of Algorithms and Problem Complexity]

General Terms: Algorithms, Design

Additional Key Words and Phrases: Clock tuning, level-clocked circuitry, multiphase clocking, retiming, timing analysis and optimization, VLSI

Selected references

- Charles E. Leiserson and James B. Saxe. A mixed-integer linear programming problem which is efficiently solvable. Journal of Algorithms, 9(1):114-128, March 1988.

- Charles E. Leiserson and James B. Saxe. Retiming synchronous circuitry. Algorithmica, 6:5-35, 1991.

- Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, January 1984.

- Nimrod Megiddo. Partitioning with two lines in the plane. Journal of Algorithms, 6(3):430-433, September 1985. Note.