In this paper, we present a method for efficiently obtaining area and delay estimates from RTL descriptions of a logic design. The estimates are obtained through fast compiler-type optimizations on the RTL descriptions followed by application of best-fit polynomial area and delay models on the resulting technology-independent representation. The estimation techniques were incorporated into a tool called QUEST. QUEST was used by designers of a large commercial CPU to obtain quick feedback on the area and delay impart of behavioral modifications, resulting In significant savings in design schedule.

This paper describes a diagnosis technique for locating design errors in circuit implementations which do not match their functional speci cation.The method eciently propagates mismatched p atterns from erroneous outputs backward into the network and calculates circuit regions which most likely contain the error(s).In contrast to previous approaches, the described t e chnique does not depend on a xed set of error models.Therefore, it is more general and especially suitable for transistor-level circuits, which have a broader variety of possible design errors than gate-level implementations.Furthermore, the proposed method is also applicable for incomplete sets of mismatched p atterns and hence c an be used not only as a debugging aid for formal veri cation techniques but also for simulationbased approaches.Experiments with industrial CMOS circuits show that for most design errors the identi ed problem region is less than 3% of the overall circuit.

In this paper an algorithm is described for obtaining an initial placement of small-cell ICs subject to performance constraints. The algorithm employs an effective nonlinear wirelength function and an accurate timing model using a block-oriented representation of paths. By introducing the concept of a reduced forest of timing constraints for cap turing the structure inherent in the constraints an efficient algorithm for performance driven initial placement is developed and its finiteness proved under less stringent conditions than [JSKSO]. In addition, it does not require an initial feasible solution. The algorithm presented in [JSKSO] required an initial feasible solution, which is computationally expensive, taking over 9 hours for an example with 1418 modules. The new algorithm presented in this paper is shown to be effective on practical examples. For the example with 1418 modules, it is able to find an optimal solution in under 8 minutes of CPU time without requiring a feasible solution. Limited space necessitated a highly simplified presentation of the algorithm here. Details may be found in [SriSO].

An efficient algorithm, RITUAL (residual iterative technique for updating all Lagrange multipliers), for obtaining a placement of cell-based ICs subject to performance constraints is described. Using sophisticated mathematical techniques, one is able to solve large problems quickly and effectively. The algorithm is very simple and elegant, making it easy to implement. In addition, it yields very good results, as is shown on a set of real examples. The algorithm was tested on the ISCAS set of logic benchmark examples using parameters for 1 mu m CMOS technology. On average , there is a 25% improvement in the wire delay for these examples compared to TimberWolf-5.6 with a small impact on the chip area.>

In this paper we focus on routing techniques for opti-mizing clock signals in small-cell (e.g., standard-cell, sea-of gate, etc...) ASICs. In previously reported work, the routin P of the clock net has been ordinary g obal routing techniques base a” erformed using on a minimum or minimal Steiner tree that have little under-of clock routing problems. We F resent a novel to clock routing that all but e rminates clock yields excellent phase delay results for a wide range of chip sizes, net sizes (pin count), minimum fea-ture sizes, and pin distributions on both randomly cre-ated and standard industrial benchmarks. For certain classes of pin distributions we have proven theoretically and observed exnerimentallv a decrease in skew with an increase in net Bize. In practice, we have observed a two to three order magnitude reduction in skew when compared to a minimum rectilinear spanning tree.

An algorithm was developed for the placement of small-cell ICs subject to performance constraints that is efficient in terms of speed and memory usage. The approach models wirelength using a nonlinear cost function similar to that of R.S. Tsay et al. (1988) and a timing model which uses a block-oriented representation of paths like that of M.A.B. Jackson and E.S. Kuh (1989). The timing constraints are implicitly represented using a network and nonlinear programming techniques are used to solve the wirelength minimization problem while satisfying the constraints. This allows critical paths to dynamically adjust while the placement changes to minimize wirelength. The solution of the nonlinear programming problem yields an initial placement of cells that may violate slot constraints. The authors propose hierarchical solution techniques to resolve the slot constraints. By exploiting structure inherent in the formulation, a large reduction is achieved in the number of variables that represent the problem. Additionally, developing special techniques to take advantage of the interaction between the timing model and the physical position of the cells enabled the authors to achieve a speed-up of 10-15 times over Jackson and Kuh (1989) even with a crude implementation of the algorithm.>

An investigation was made of the analogous graph structure for representing and manipulating discrete variable problems. The authors define the multi-valued decision diagram (MDD), analyze its properties (in particular prove a strong canonical form) and provide algorithms for combining and manipulating MDDs. They give a method for mapping an MDD into an equivalent BDD (binary decision diagram) which allows them to provide a highly efficient implementation using the previously developed BDD packages. A direct implementation of the MDD structure has also been carried out, but this initial implementation has not yet been tuned to the same extent as the BDDs to allow a reasonable comparison to be made. The authors have used the mapping to BDDs to provide an initial understanding of the limits on the sizes of real problems that can be executed. The results are encouraging.>