Karem A. Sakallah
Student: V. Chandramouli
Professor: K.A. Sakallah
Sponsor: Advanced Research Projects Agency
The stringent performance requirements on today's high performance VLSI designs is forcing a reassessment of the conventional timing models and analysis methods. Not only do we need to have accurate circuit level timing models but also a way of abstracting these models to higher levels in the design hierarchy without sacrificing accuracy. However, we find the current situation in the field to be woefully inadequate in meeting these two goals. On the modeling front, by ignoring the temporally close switching of inputs, circuit level models for multi-input gates do not account for state dependency, causing inaccuracy. Since interconnect delays can no longer be ignored, considerable effort is being spent on developing accurate models for them. However, there is no uniformity in interconnect modeling and gate modeling approaches, despite several similarities in the underlying phenomena. Moreover, owing to the lack of a suitable abstraction mechanism and need for greater accuracy, these timing models are being overloaded with the details of the analog waveform, thus making these models complicated for global analysis of entire chips. In the case of timing analysis, inaccuracy is caused by keeping separate the inherently linked functional and temporal models. To remove such inaccuracies, different sensitization criteria and adhoc extensions to switching algebra have been proposed making timing analysis unnecessarily complicated and confusing. The principal source of these problems is the lack of a rigorous theoretical foundation for timing.
This research is aimed at taking the first few steps in providing such a foundation by treating gates, interconnects and memory elements in a unified framework, that accounts for state dependency where necessary. The basis for this framework is a recently developed formal calculus of digital waveforms that embodies a systematic treatment of static and dynamic behavior. The modeling framework will be validated on the 1GHz PUMA high-performance microprocessor design project. In particular, we are developing delay models for static and dynamic CGaAs gates, on-chip interconnect wires, and multichip module transmission lines.
Student: Michael A. Riepe
Professor: K.A. Sakallah
Sponsor: Advanced Research Projects Agency
We are studying the problem of leaf cell generation for structured custom VLSI design. This involves the synthesis of transistor-level mask geometry for circuits of between one and one hundred transistors. The input is a sized transistor netlist, a technology description, and a set of high-level constraints that specify the aesthetic appearance of the resulting cell. These high-level constraints may, for example, constrain the geometry to achieve a layout for a standard-cell synthesis system by forcing power rails to lie at the top and bottom of the cell, and ports to align to a horizontal grid of metal2 contacts.
We have examined a wide range of techniques for leaf cell generation and characterized them based on their flexibility in reorganizing the layout to optimize the cell under different sets of design rules. These techniques range from those very limited in their flexibility, such as compiled cell generator code (we refer to these as cell capture techniques) and gate-matrix techniques, to those of intermediate flexibility, such as one and two-dimensional compaction, to unrestricted methods that treat cell generation as a transistor-level floor planning and routing problem.
Our current research involves the study of systems that treat leaf cell generation as a generalized floor planning and routing problem. Our goal is to automate the layout of digital VLSI leaf cell libraries, and to produce layouts of a quality comparable to those that are hand designed. We believe that the best method to achieve this is by using the most unrestrained model for manipulating the layout that is possible, so that the layout is not forced to conform to non-beneficial regularity. However, the tools will guide the optimization process by recognizing beneficial regularity when it exists. Building on work in macro-block floor planning and routing, we are studying how the problem is best solved when the blocks being placed and routed are individual transistors. We are also studying how to generalize the problem to incorporate arbitrary high-level constraints so that we can constrain the tools to produce layouts for a wide variety of different technologies and different design-tool environments. As an example, if it is likely that a gate-matrix style layout is an optimal configuration in a certain static CMOS technology, the tool will be capable of recognizing this fact, and constraining the transistors to lie in dual complementary rows. However, the tool will also be flexible enough to handle odd-sized transistors that do not fit well into such a restricted layout model.
Student: Victor Kravets
Professor: K.A. Sakallah
Sponsor: Advanced Research Projects Agency
Operation in the 1GHz range requires that all aspects of a design be carefully tuned to deliver this level of performance. Our experience in the ARPA-sponsored GaAs MIPS project indicated that the standard multi-level logic synthesis techniques used in CMOS design perform poorly in the fanin/fanout-limited DCFL NOR logic gate family. The Aurora-II control unit, for example, has a critical path with 16 logic levels. At 100ps/gate, and disregarding interconnect delays, this corresponds to 1.6ns. We conjecture that the reasons for the poor quality of the synthesized circuitry is the limited flexibility (only NOR gates) at the technology mapping step of logic synthesis. This, however, may present an opportunity that is peculiar to GaAs. The fact that all logic in DCFL must be implemented with NOR gates suggests that the technology mapping step in logic synthesis is superfluous and better results could be obtained by constructively creating the logic circuit using NOR gates. This is not a new idea. As early as 1968, Davidson and Muroga presented algorithms for optimal NAND decomposition of logic functions. More recently, Mithani suggested algorithms for NAND synthesis using implicants containing output variables. The most recent account of this type of synthesis appeared in 1989 for optimal NOR circuits. Unfortunately, these algorithms are not applicable except to very small circuits because they are designed around an exponential (truth table) representation of logic functions.
A more serious shortcoming of current logic synthesis tools is their poor estimation of wiring costs. We have observed a factor of 5 increase in area and delay that is solely attributable to the wiring complexity of a synthesized circuit.
To address these issues, in this research we view the logic synthesis problem as a search in the space of possible structural implementations of a set of logic functions. Using very efficient satisfiability-based search tools developed at the University of Michigan, a suitable circuit implementation of a logic function is found by searching in the space of "desirable" circuit topologies, namely those with low wiring complexities. we plan to identify takes a radical approach to logic synthesis.
Student: Jeffrey L. Bell
Professor: K.A. Sakallah
Sponsor: Semiconductor Research Corporation
In the development of a digital design, there is a degree of planning by the designer, that can be used to simplify the verification. The goal of this research is to develop timing verification methods that make use of the higher level constructs.
One problem in verifying the timing constraints of a circuit is how to ignore the timing along paths that cannot be sensitized. If these paths occur within a section of logic that follows particular connectivity style (such as an adder or a multiplier) it should be possible to use a higher level construct in place of the low level logic gates. Since the designer is probably well aware of the true critical paths, such an RTL model can be given the proper end-to-end delay. This research is into ways to incorporate the data dependent portion of the delay into the timing model.
Another approach to the false path problem is to automatically generate the set of false paths. Since most designs have portions of that are datapaths and other portions that are control, it is possible to condense the signal timing of the datapath into single signals which are either in a stable or changing state. By reducing the design in this way the number of cases that must be checked can be greatly reduced, since it is only the state devices of the control logic that need to be checked for reachable states.
A third activity is an investigation into the nature of delay. Most engineers have an intuitive understanding of what delay specifications in a data book mean, but a more rigorous definition needs to be developed in order to describe the effects of functional dependencies, simultaneous switching, edge rate effects, and pulse shrinkage.
Student: Jesse Paul Whittemore
Professor: K.A. Sakallah
Sponsor: EECS Department Fellowship
This project aims at building an experimental software workbench for studying the recently proposed symbolic waveform calculus for digital circuits. This calculus exposes the intrinsic relation between the static and dynamic behaviors of digital circuits and unifies them in one comprehensive modeling framework. The first phase in the development of the experimental workbench was the creation of fundamental data structures that will serve as the building blocks to future exploration tools. Currently, an interactive "boolean function calculator" is being constructed to exercise our models. It will provide us with a better understanding of their behavior by allowing us to quickly and easily manipulate symbolic boolean functions in the manner described by the waveform calculus. Our future research includes the addition of finite-slope rise/fall times to our models and the construction of a circuit timing analyzer using this approach.
Students: V. Chandramouli and Jong-gwan Yook
Professor: K.A. Sakallah (Joint with Prof. L. Katehi)
Sponsor: Intel Corporation
The goal of this project is to provide more systematic analysis and design procedures for estimating and controlling simultaneous switching noise in printed circuit boards. The starting point is a 2-D equivalent circuit of the power distribution system that captures all its resistive, capacitive, and inductive parasitic. Transient simulation of this circuits using traditional circuit simulators such as SPICE, or the much faster but less accurate asymptotic waveform simulators such as AWESim and RICE, is then used to determine the existence and severity of power glitches and ground bounce. Interactive decoupling capacitance insertion at appropriate locations is then applied to reduce the noise on the power and ground lines. The long term objective of this project is to automatically determine the location and size of the decoupling capacitors that are necessary to dampen the noise below acceptable limits.