Timing in level-clocked circuits
Alexander T. Ishii · Medical Entomology and Zoology · 1992
This thesis investigates algorithmic design aids for high-throughput VLSI systems. In particular, the thesis addresses the difficulties that arise when the levels (high or low) of external clocks, rather than the transitions (edges), are used to synchronize the operation of the various system components. The use of such level clocking is common in MOS VLSI circuits. The thesis presents algorithms for verifying the throughput of systems which utilize level clocking, and algorithms for exploring the throughput-performance benefits of transforming an edge-triggered system into a level-clocked one. The thesis focuses on algorithms that are mathematically well characterized, and guaranteed to run in polynomial time. The primary analytical result of the thesis is a class of simple linear constraints, the $\Delta$-constraints, whose elements can serve as a sufficient, and in some cases necessary, set of conditions for the proper of a level-clocked system. A level-clocked system is represented as a graph G = (V,E), where elements of V represent system components--latches and functional elements--and elements of E represent inter-component connections. Sets of $\Delta$-constraints are defined using the notions of and functions. Computational expansions encode the time-dependent behavior of a given system and are defined in terms of a base-step function. Base-step functions provide a simple means of adapting computational expansions, and thus sets of $\Delta$-constraints, to the peculiarities of specific systems. The thesis presents one structural base-step function which is easily computed, yet reflects all the various timing phenomena that are not dependent on the specific functions computed by the functional elements of a system. In addition, the thesis demonstrates that, in aggregate, the constraints yielded by the presented base-step function are tight in the sense that they cannot be relaxed unless additional constraints are imposed on the specific functions computed by functional elements. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened with permission of school.)