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 combinational 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 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(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 ) time.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:-retiming and tuning when either the duty cycle of one phase is fixed or the ratio of the phases' duty cycles is fixed: O(V 3 lg(V/⑀)) time.-simultaneous retiming and clock tuning with no conditions on the duty cycles of the two phases: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 integers.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

This paper presents methods for retiming VLSI systems that contain precharged circuit structures and/or "gated" clock signals. Due to the tangible speed, power, and area benefits of circuit structures that utilize precharging techniques and/or gated clock signals, both are common in "high-performance" VLSI designs. Previous methods for performing retiming (i.e., optimizing the placement of latches) have not, however, addressed the pecularities of such circuit structures, and consequently, have not been applicable to many non-ASIC VLSI systems. The presented methods immediately lead to an algorithm which runs, to within a constant factor, in the same amount of time as previous retiming algorithms, yet is capable of handling precharged structures and gated clock signals. Using the algorithm, it is possible to apply retiming techniques to "full custom" VLSI designs. Though the paper focuses on the problem of retiming, the methods described are also applicable to the problem of timing verification. All results are based upon a general set of "timing" constraints which is directly applicable to circuits that contain precharged structures and gated clocks.

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels with any number of layers and automatically chooses a good assignment of wiring strategies to the different layers. In test cases, MulCh shows significant improvement over Chameleon in terms of channel width, net length, and number of vias.>