This paper quantifies the approximation error when results obtained by Clark (1961) are employed to compute the maximum (max) of Gaussian random variables, which is a fundamental operation in statistical timing. We show that a finite lookup table can be used to store these errors. Based on the error computations, approaches to different orderings for pairwise max operations on a set of Gaussians are proposed. Experimental results show accuracy improvements in the computation of the max of multiple Gaussians, in comparison to the traditional approach. In addition, we present an approach to compute the tightness probabilities of Gaussian random variables with dynamic runtime-accuracy tradeoff options. We replace required numerical computations for their estimations by closed form expressions based on Taylor series expansion that involve table lookup and a few fundamental arithmetic operations. Experimental results demonstrate an average speedup of 2 using our approach for computing the maximum of two Gaussians, in comparison to the traditional approach, without any accuracy penalty.

In this paper, we propose a statistical gate sizing approach to maximize the timing yield of a given circuit, under area constraints. Our approach involves statistical gate delay modeling, statistical static timing analysis, and gate sizing. Experiments performed in an industrial framework on combinational International Symposium on Circuits and Systems (ISCAS'85) and Microelectronics Center of North Carolina (MCNC) benchmarks show absolute timing yield gains of 30% on the average, over deterministic timing optimization for at most 10% area penalty. It is further shown that circuits optimized using our metric have larger timing yields than the same optimized using a worst case metric, for iso-area solutions. Finally, we present an insight into statistical properties of gate delays for a commercial 0.13-mum technology library which intuitively provides one reason why statistical timing driven optimization does better than deterministic timing driven optimization

Variability in the chip design process has been relatively increasing with technology scaling to smaller dimensions. Using worst case analysis for circuit optimization severely over-constrains the system and results in solutions with excessive penalties. Statistical timing analysis and optimization have consequently emerged as a refinement of the traditional static timing approach for circuit design optimization. In this paper, we propose a statistical gate sizing methodology for timing yield improvement. We build statistical models for gate delays from library characterizations at multiple process corners and operating conditions. Statistical timing analysis is performed, which drives gate sizing for timing yield optimization. Experimental results are reported for the ISCAS and MCNC benchmarks. In addition, we provide insight into statistical properties of gate delays for a given technology library which intuitively explains when and why statistical optimization improves over static timing optimization.

Programmable circuit design has played an important role in improving design productivity over the last few decades. By imposing structure on the design, efficient automation of synthesis, placement and routing is possible. We focus on a class of programmable circuits known as mask programmable circuits. In this paper, we describe key issues in design and tool methodology that need to be addressed in creating a programmable fabric. We construct an efficient design flow that can explore different logic and routing architectures. The main advantage of our work is that we tailor tools designed for standard cell design, that are readily available in the market, to work on a programmable fabric. Our flow requires some additional software capability. A special router that understands programmable routing constructs to complete connections is described. In addition, a tool that packs logic efficiently after synthesis is also presented.

China and India represent two of the most rapidly evolving markets for IC design today. According to the CMP China IC Design Survey 2002, demand for IC design services in China is growing exponentially alongside 8- and 12-inch wafer fab construction. In India, multinationals and local companies continue to accelerate the development of complex IC's, matching the sophistication of design teams world wide. China and India are graduating the most EEs annually of any other countriess. This dynamic growth of IC design and its associated infrastructure in China & India is causing is causing all participants in the semiconductor value chain to carefully consider their business interactions in these countries. This panel will evaluate how IC design is changing in these emerging markets. Panelists will represent a variety of viewpoints, including multinationals, local government, local universities, and large local companies. The panel will also explore of this emerging market on the EDA industry.

Routing is an important problem in the process of design creation. In this paper, we focus on the problem of designing a database for the non-partitioned routing problem. New technology libraries describe constraints that are hard to manage in grid-based approaches to the routing database. While general region query based data-structures have been proposed, they typically suffer from speed problems when applied to large blocks. We introduce an interval-based approach. It provides more flexibility than grid-based techniques. It exploits the notion of preferred direction for metal layers to manage the memory efficiently. It supports efficient region queries. We finally present a comparison study for real industrial designs on this database.

Routing is one of the most complex stages in the back-end design process. Simple routing algorithms based on two stages of global routing and detailed routing do not offer appropriate opportunities to address problems arising from signal delay, cross-talk and process constraints. An intermediate stage of track assignment between global and detailed routing proves to be an ideal place to address these problems. With this stage it is possible to use global routing information to efficiently address these problems and to aid the detailed router in achieving the wiring completions. In this paper we formulate routing as a three stage process; global routing, track assignment and detailed routing. We describe the intermediate track assignment problem and suggest an efficient heuristic for its solution. We introduce cost metrics to model basic effects arising from connectivity. We discuss extensions to include signal integrity and process constraints. We propose a heuristic based on weighted bipartite matching as a core routine. To improve its performance additional heuristics based on lookahead and segment splitting are also suggested. Experimental results are given to highlight the efficacy of track assignment stage in routing process.

We present the tile-cached kd-tree, an efficient external-memory (disk) implementation of two-dimensional region query for use in a detailed area router. Most researchers have heretofore focused on in-memory algorithms. However as the need to tackle very large problems increases, conventional in-memory algorithms suffer from unpredictable caching and paging behavior and their performance may degrade considerably. In addition, since the region-query data structure is only part of the overall system, its consumption of large memory resources affects other parts of the system as well. Our implementation takes advantage of spatial locality in the detailed-routing process. We partition the routing space into tiles, each storing the data of objects (rectangles) that lie strictly within it. Objects that cross tile boundaries are separately stored. The data within a tile are then written out to disk, and a configurable cache is used to hold in memory the most recently visited tiles. Experimental results on large real-life routing problems show that this scheme significantly reduces memory usage with tolerable performance penalty.

Minimum spanning tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(n log n) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.

Increasing delay variation due to crosstalk has a dramatic impact on deep sub-micron technologies. It is now necessary to include crosstalk in timing analysis. But timing analysis with crosstalk is a chicken-and-egg problem since crosstalk effect in turn depends on timing behavior of a circuit. In this paper, we establish a theoretical foundation for timing analysis with crosstalk. We show that solutions to the problem are fixpoints on a complete lattice. Base on that, we prove in general the convergence of any iterative approach. We also show that, starting from different initial solutions, an iterative approach will reach different fixpoints. The current prevailing practice, which starts from the worst case solution, will always reach the greatest fixpoint (which is the loosest solution). In order to reach the least fixpoint, we need to start from the best case solution. Base on chaotic iteration and heterogeneous structures of coupled circuits, we also design techniques to speed up iterations.

Traditional ASIC design flows have treated logic synthesis and physical design as separate steps in the flow. A recent trend in design automation has been to integrate placement and logic synthesis operations for designs that strive for high performance. The motivation for this is ascribed to achieving timing convergence. These efforts attempt a brute-force combination of techniques from the two fields. We present an architecture for combining synthesis transforms with rough placement. There are three main contributions of this paper. First we present a system architecture that permits a clean separation of placement and synthesis issues and combines the two solutions in an elegant manner. Second, we propose a minor modification to the current ASIC design flow to enable timing convergence. Third, we use design rules for correct circuit operation to drive the placement and the synthesis components of the system. We present results for a set of high performance ASIC designs which demonstrate the practicality of our method.

Due to deep sub micron effects, accurate gate sizing is increasingly important. Most advanced methods for sizing assume that gates can be sized continuously, while most design is done with discrete gate array and standard cell libraries. To bridge this gap, this paper proposes a new approach to gate sizing which combines a small number of discrete gate sizes to approximate the ideal of continuous sizing. To date research has focussed on deciding an appropriate set of logic functions for the primitive gates in a library. The main contribution of this paper is the development of a theoretical framework for strategies of drive strength selection for libraries. We demonstrate that nearly continuous sizing can be achieved by combining gates of a small number of sizes. The experimental procedure is based on simulated annealing. The results show that with only 5 discrete sizes any continuous size within a range of two orders of magnitude can be approximated with an accuracy of 1.7%.

We present a new model for circuits which have memory elements using conditional clocking, This is termed as the “gated” clock problem. Conventionally most of the recent efforts in timing analysis focus on memory elements controlled by clock signals only, We describe a simple restriction on the conditional signale which makes automatic verification easy. An algorithm to solve the timing verification problem for the case of restricted circuits based on previous approaches is given.

This paper describes an algorithm for deriving necessa~andsufticient constraints for a multi-phase sequential pipeline to operate at a target clock cycle.Constraints on delays of the pipeline stages are used to drive a combinational logic delay optimizer to resynthesize the pipeline stagesfor improved performance.A main advantage of such an approach is that a global picture of the d~tribution of delays in the circuit is obtained.It also permits safe cycle stealing through level-sensitive latches acrosspipeline stages.

Combinational circuits are often embedded in synchronous designs with memory elements at the input and output ports. A performance metric for a circuit is the cycle time of the clock signal. Correct circuit operation requires that all paths have a delay that lies between an upper bound and a lower bound. Traditional approaches in delay optimization for combinational circuits have dealt with methods to decrease the delay of the longest path. We address the issue of satisfying the lower bound constraints. Such a problem also arises in wave pipelining of circuits. We propose to handle short path constraints as a post processing step after traditional delay optimization techniques. There are two issues presented in this paper. We first discuss necessary and sufficient conditions for successful delay insertion without increasing delays of any long paths. In the second part, we present a naive approach to padding delays (greedy heuristic) and an algorithm based on linear programming. We describe an application of the theory to wave pipelining of circuits. Results are presented on a set of benchmark circuits, using two delay models.

For performance-driven synthesis of sequential circuits, the optimal clocking problem is considered, and it is shown that it is reducible to a parametric shortest path problem. Constraints are used that take into account both the short and long paths. The main contributions are efficient graph algorithms to solve the set of constraints necessary for correct clocking.>

Timing verification and optimization have been formulated as mathematical programming problems. The computational aspects of using such a formulation for verifying clock schedules are considered. The formulation can have multiple solutions, and these extraneous solutions can cause previously published algorithms to produce incorrect or misleading results. The conditions under which multiple solutions exist are characterized, and it is shown that even when the solution is unique, the running times of these previous algorithms can be unbounded. By contrast, a simple polynomial time algorithm for clock schedule verification is exhibited. The algorithm was implemented and used to check the timing of all the circuits in the ISCAS-89 benchmark suite. Observed running times are linear in circuit size and quite practical.>

The authors address the problem of synthesis for a popular class of programmable gate array architecture-the table look-up architectures. These use lookup table memories to implement logic functions. The authors present improved techniques for minimizing the number of table look up blocks used to implement a combinational circuit. On average, the results obtained on a set of benchmarks are 15-29% better than results obtained by previous approaches.>

The authors address the problem of delay optimization for programmable gate arrays. The main considerations are the number of levels in the circuit and the wiring delay. The authors propose a two-phase approach: the first phase involves delay optimizations during logic synthesis before placement, while the second uses logic resynthesis in the case of a timing-driven placement technique. Results and comparisons on benchmarks are presented.>

An algorithm is developed for the retiming of single phase sequential circuits with level sensitive (transparent) latches. A set of constraints that permit retiming and optimal clock cycle computation are also developed. It is shown that a design with edge-triggered latches may be tested for speed-up using transparent latches.>

The problem of combinational logic synthesis is addressed for two interesting and popular classes of programmable gate array architectures: table-look-up and multiplexor-based. The constraints imposed by some of these architectures require new algorithms for minimization of the number of basic blocks of the target architecture, taking into account the wiring resources.