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, and retiming, 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 set V is a collection of combinatorial logic blocks, and whose edge set E is 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, or phases.
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 lg V) 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 lg V) 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 of k slower 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.