Journal of the Association for Computing Machinery, Vol. 44, No. 1, January 1997, pp. 148–199.

Optimizing Two-Phase, Level-Clocked Circuitry

ALEXANDER T. ISHII

CHARLES E. LEISERSON

AND

MARIOS C. PAPAEFTHYMIOU

Abstract. We 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

• verifying proper timing: O(V E) time.

• minimizing the clock period by clock tuning: O(V E) time.

• retiming to achieve a given clock period when the phases are symmetric: O(V E + 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}).

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

• retiming and tuning when the duty cycles of the two phases are required to be equal: O((V E + V^{2} lg V) lg(V/ϵ)) 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/ϵ)) time.

• simultaneous retiming and clock tuning with no conditions on the duty cycles of the two phases: O(V^{3}(1/ϵ) lg(1/ϵ) + (V E + V^{2} lg V) lg(V/ϵ)) time.

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.

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

Copyright 1997 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. 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, levelclocked circuitry developed at MIT.

Categories and Subject Descriptors. B.6.3 [Logic Design]: Design Aids—optimization, verification; 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