OPTIMIZING 2-PHASE, LEVEL-CLOCKED CIRCUITRY

We investigate two strategies for reducing the clock period of a two-p hase, 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 l atches into a faster level-clocked one. We model a two-phase circuit a s a graph G = (V, E) whose vertex set V is a collection of combination al logic blocks, and whose edge set E is a set of interconnections. Ea ch interconnection passes through zero or more latches, where each lat ch is clocked by one of two periodic, nonoverlapping waveforms, or pha ses. We give efficient polynomial-time algorithms for problems involvi ng the timing verification and optimization of two-phase circuitry. In cluded are algorithms for verifying proper timing: O(VE) time. minimiz ing 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) t ime. retiming to achieve a given clock period when either the duty cyc le (high time) of one phase or the ratio of the phases' duty cycles is fixed: O(V-3) time. We give fully polynomial-time approximation schem es for clock period minimization, within any given relative error epsi lon > 0, by 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. retim ing and tuning when either the duly cycle of one phase is fixed or the ratio of the phases' duty cycles is fixed: O(V-3 lg(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 I g V)lg(V/epsilon)) time. The first two of these approximation algorith ms can be used to obtain the optimum clock period in the special case where all propagation delays are integers. We generalize most of the r esults for two-phase clocking schemes to simple multiphase clocking di sciplines, including ones with overlapping phases. Typically, the algo rithms to verify and optimize the timing of k-phase circuitry are at m ost a factor of k slower than the corresponding algorithms for two-pha se circuitry. Our algorithms have been implemented in TIM, a timing pa ckage for two-phase, level-clocked circuitry developed at MIT.