To address the problem of accurate timing characterization, this paper proposes a method that fully exploits mode dependency. It is based on the premise that circuit delays are determined largely by a set of control inputs for which the number of useful combinations, i.e., modes, is small for most practical circuits. We take the mode-dependent characterization approach further and enhance it so that the delays of the I/O paths between the control inputs and outputs are calculated more accurately. We prove that, with a careful choice of propagation conditions, our method can generate timing models with very tight path delays that are guaranteed to give correct results. Experimental results using real-life circuits show that cir-cuit delays can vary significantly among different modes for both control and data input delays, and capturing this variation can have a significant impact on the overall system timing.

In deep submicrometer integrated circuit design, there is a growing need to quickly and accurately characterize the timing of large circuit blocks. Accurate timing characterization requires making available as much timing information as possible at each step of the design process. Conventional fast characterization methods typically employ topological analysis, which can be inaccurate because of its inability to eliminate false paths. To address this problem, a new method for creating accurate timing models of circuit blocks by making efficient use of their functionality is introduced. The proposed mode-dependent characterization (ModeChar) method is based on calculating a distinct timing model for each mode of circuit operation and reflects the way practical circuits function. ModeChar produces a mode-dependent timing model that contains delay information for a given set of circuit modes. It is shown that circuit delays are never underestimated by the mode-dependent models. The concept of mode dependency is taken further by extending it to sequential circuits. Given a sequential circuit, a compact set of constraints is derived for each circuit mode that captures all the timing constraints that must be satisfied for correct operation of the circuit. Experimental results are presented that demonstrate the effectiveness of ModeChar in eliminating many false paths that would otherwise result in performance penalties. In addition, our experiments indicate that delays can vary considerably among circuit modes, making conventional topological analysis overly pessimistic. To make the mode-dependent models more compact, an efficient algorithm far coalescing delay information is also introduced.

Two new techniques for mapping circuits are proposed in this paper. The first method, called the odd-level transistor replacement (OTR) method, has a goal that is similar to that of technology mapping, but without the restriction of a fixed library size and maps a circuit to a virtual library of complex static CMOS gates. The second technique, the static CMOS/pass transistor logic (PTL) method, uses a mix of static CMOS and PTL to realize the circuit and utilizes the relation between PTL and binary decision diagrams. The methods are very efficient and can handle all of the ISCAS'85 benchmark circuits in minutes. A comparison of the results with traditional technology mapping using SIS on different libraries shows an average delay reduction above 18% for OTR, and an average delay reduction above 35% for the static CMOS/PTL method, with significant savings in the area.

A high accuracy system for transistor-level static timing analysis is presented. Accurate static timing verification requires that individual gate and interconnect delays be accurately calculated. At the sub-micron level, calculating gate and interconnect delays using delay models can result in reduced accuracy. Instead, the proposed method calculates delays through numerical integration using an embedded circuit simulator. It takes into account short circuit current and carefully chooses the set of conditions that results in a tight upper bound of the worst case delay for each gate. Similar repeating transistor configurations of gates in the circuit are automatically identified and a novel interpolation based caching scheme quickly computes gate delays from the delays of similar gates. A tight object code level integration with a commercial high speed transistor level circuit simulator allows efficient invocation of the simulation.

A method that characterizes the timing of Intellectual Property (ZP) blocks while taking into account IP functionality is presented.IP blocks are assumed to have multiple modes of operation specified by the user.For each mode, our method calculates IO path delays and timing constraints to generate a timing model.The method thus captures the mode-dependent variation in IP delays which, according to our experiments, can be as high as 90%.The special manner in which delay calculation is performed guarantees that IP delays are never underestimated.The resulting timing models are also compacted through a process whose accuracy is controlled by the user.1.1

A new design methodology for mapping circuits is discussed in this paper. It proposes two new techniques for mapping circuits. The first method, known as the odd-level transistor replacement (OTR) method, has a goal that is similar to that of technology mapping, but without the restriction of a fixed library size. The second technique, the Static/PTL method, uses a mix of static CMOS and pass transistor logic (PTL) to realize the circuit, using the relation between PTL and binary decision diagrams. The methods are very efficient and can handle all of the ISCAS85 benchmark circuits in minutes. A comparison of the results with traditional technology mapping using SIS on different libraries shows an average delay reduction about 40% for OTR, and an average delay reduction above 50% for the Static/PTL method.

This work presents strategies to insert buffers in a circuit, combined with gate sizing, to achieve better power delay and area-delay tradeoffs. The purpose of this work is to examine how combining a sizing algorithm with buffer insertion will help us achieve better area delay or power-delay tradeoffs, and to determine where and when to insert buffers in a circuit, The delay model incorporates placement-based information and the effect of input slew rates on gate delays. The results obtained by using the new method are significantly better than the results given by merely using a TILOS-like gate sizing algorithm alone, as is illustrated by several area delay tradeoff curves shown in this paper.

A method for concurrent transistor sizing and buffer insertion is proposed. The method considers the tradeoff between upsizing transistors and inserting buffers and chooses the solution with the lowest possible power and area cost. The method operates by analyzing the feasible region of the cost-delay curves of the unbuffered and buffered circuits. As such the feasible region of circuits optimized by our method is extended to encompass the envelop of cost-delay curves which represent the union of the feasible regions of all buffered and unbuffered versions of the circuit. The method is e#cient and tunable in that optimality can be traded for compute time and the method can in theory produce near optimal results.

A novel constraint-graph algorithm for the optimization of yield is presented.This algorithm improves the yield of a layout by carefully spacing objects to reduce the probability of faults due to spot defects.White space b etween objects is removed and spacing in tightly packed a r e as of the layout is increased.The computationally expensive problem of optimizing yield is transformed into a network ow problem, which can be solved via known ecient algorithms.Yield can be improved either without changing the layout area, or if necessary by increasing the layout area to maximize the number of good chips per wafer.Our method c an in theory provide the best possible yield achievable without modifying the layout topology.The method is able to handle a general class of convex objective functions, and can therefore optimize not only yield, but other circuit performance functions such as wire-length, cross-talk and power.

Hierarchical compaction requires that a system of linear equations be solved, usually via linear programming (IE) techniques.In the presence of overconstraints, LP techniques provide inadequate information to locate the cause of these overconstraints.A new graph theoretical method capable of identifying overconstraints and providing meaningful feedback to the user is described.The method also considerably reduces the number oj equations to be solved by LPI making %gompaction of very large layouts possible.

A method for efficiently performing hierarchical compaction in the presence of over the cell routing (OTCR) is described. By treating the OTCR objects as part of the cells they overlap, the amount of interaction between cells in the hierarchy is reduced. This method eliminates the need to make all objects within a cell that interact with OTCR into ports. An explosion in the complexity of the problem that needs to be solved via linear programming (LP) is thus avoided. Computation is shifted away from LP and into the graph domain where efficient and accurate solution methods have been demonstrated.>

The process of verifying that a circuit's schematic netlist obeys a particular design methodology is formalized. Circuit correctness is tied to a rigorous set of context free grammar composition rules. These rules define how a small set of module symbols may be combined for circuits adhering to the design methodology. Schematic netlists are represented as graphs, and composition rules are defined as graph transformations akin to grammatical productions. Starting with a circuit netlist, a hierarchical parse tree that can demonstrate the wellformedness of the circuit is constructed. The procedure is hierarchical, incremental, and fast. GRASP operates one to two orders of magnitude faster than previous approaches.

This paper investigates technical issues concerning the automated generation of highly regular VLSI circuit layouts (e.g. RAMs, PLAs, systolic arrays) that are crucial to the designability and realizability of large VLSI systems. The key is to determine the most profitable level of abstraction for the designer, which is accomplished by the introduction of macro abstraction, interface inheritance, delayed binding, and the complete decoupling of procedural and graphical design information. These abstraction mechanisms are implemented in the Regular Structure Generator, an operational layout generator with significant advantages over first generation layout tools. Its advantages are demonstrated by a pipelined array multiplier layout example.

The throughput of a combinational array multiplier is shown to be asymptotically suboptimal using performance measures derived from VLSI models of computation. Applying a systematic transformation called retiming, a class of asymptotically optimal pipelined array multipliers is obtained. The optimum circuit performance within this class must be deternmined empirically through repeated iterations of multiplier layout generation, circuit extraction, and electrical simulation. The structure of these pipelined multipliers facilitates such an empirical investigation by admitting very regular layouts that can be generated quickly and interactively.