Accession Number : ADA256796


Title :   A Timing Analysis of Level-Clocked Circuitry


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE


Personal Author(s) : Ishii, Alexander T ; Leiserson, Charles E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a256796.pdf


Report Date : Sep 1992


Pagination or Media Count : 35


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.


Descriptors :   *ALGORITHMS , *CLOCKS , *METAL OXIDE SEMICONDUCTORS , *TIME SIGNALS , *VERY LARGE SCALE INTEGRATION , *LATCHES , *TIMING CIRCUITS , FUNCTIONS , PHASE , BOUNDARIES , TRANSITIONS , CIRCUITS , DELTAS , HIGH VOLTAGE , PAPER , COLLECTION , EXPANSION , STANDARDS , TIME , CYCLES , GRAPHS , EDGES , VERIFICATION


Subject Categories : Electrical and Electronic Equipment
      Solid State Physics


Distribution Statement : APPROVED FOR PUBLIC RELEASE