A TIMING ANALYSIS OF LEVEL-CLOCKED CIRCUITRY

Abstract

This paper presents an algorithm for verifying proper timing in VLSI circuits where latches are controlled by the levels (high or low) of the controlling clocks rather than the transitions (edges) of the clocks. Such level-clocked circuits are frequently used in MOS VLSI design. A level-clocked circuit is modeled as a graph G = (V, E), where V consists of components-latches and functional elements-and E represents intercomponent connections. The algorithm verifies the proper timing of a circuit in worst-case O(V/E) time and O(V + E) space. Our analysis decouples the problem of generating timing constraints from the problem of efficiently checking them. We show how various base step functions can be used to provide sufficient conditions for a circuit to operate properly, and we provide a new base step function which is less pessimistic than those used in previous timing verifiers, yet correctly handles timing constraints that are cyclic or extend across the boundaries of multiple clock phases or cycles. The base step function is used to derive a computational expansion of the circuit from which a collection of simple linear constraints are derived. These constraints can be efficiently checked using standard graph algorithms. VLSI systems, Level-clocking, Timing constraints, Timing analysis, Timing verification, Computational expansions, Delta-constraints, Formal modeling, Graph algorithm applications, Algorithmic techniques.