Hierarchical timing analysis of digital circuits.

Abstract

This thesis presents systematic modeling and analysis techniques for the accurate and efficient timing analysis of complex digital integrated circuits. Two major, but little studied, aspects of timing analysis are emphasized: characterization of the timing behavior of basic circuit elements, and the use of a circuit's design hierarchy to manage complexity. We also investigate the links between these two issues to develop approximations that abstract away irrelevant low-level timing information for more efficient timing analysis at higher levels of design. Fundamental to timing analysis is a rigorous representation of the behavior of dynamic signals. To address this, we develop a series of waveform models that characterize digital signal behavior at different levels of detail. Accurate delay computation further requires precise characterization of the way signal events propagate through a circuit. To this end, we use the concept of event propagation conditions (PCs), and systematically derive the PCs for all waveform models. Key to hierarchical timing analysis is a consistent timing model of circuit modules independent of their abstraction level. For this purpose, we introduce the conditional delay matrix (CDM) model to encapsulate in a uniform manner a circuit's path delays and the PCs associated with events propagating through its paths. The CDM approach naturally leads to an exact hierarchical delay computation method, which we have implemented in a symbolic program called CAT. We present an extensive set of experiments, which apply CAT to the ISCAS-85 and other benchmark circuits, and demonstrate the effectiveness of our method for large, practical designs. The CDM model also provides a framework within which various approximations and trade-offs between accuracy and computational effort can be made. We define and analyze one such approximation method that substantially simplifies the PCs by eliminating their dependence on the data inputs of a circuit, which usually have little impact on the circuit delay. We describe further experiments with high-level models of the ISCAS-85 benchmarks and CAT, which demonstrate that the approximate method is up to three orders of magnitude faster than the exact method, with little or no loss in accuracy.