For sub-100nm processes, predictions are putting initial process yields in the single digits. At the same time, at 130nm, we saw that two chips designed with the same methodology and same design rules could deliver completely different manufacturing yields.This panel will discuss the reasons for these phenomena and talk about future trends in DFM that will need to be addressed for success below 100nm.

Increasingly, system houses are attracted to the customer-owned tooling (COT) model to gain more control of their schedules and costs. COT project risk and cost are high, often seeming more like customer owned "trouble," so the design team needs to be expertly prepared. The pathways to implement a COT design include (a) Manage the sourcing (internal or third party resources) of individual supply chain and cost reduction functions; (b) Use an integrated design-to-parts service; or (c) A hybrid of these two extremes. This panel will consider the pros and cons for each approach.

A new approach to the interconnect-driven floorplanning problem integrates bus planning and is intended for bus-based designs where each bus consists of a large number of wires. The floorplanner optimizes the timing and ensures routability by generating the exact location and shape of interconnects above and between the circuit blocks. Experiments with Microelectronics Center of North Carolina benchmarks clearly show the advantage of integrated floorplanning over the classical floorplan-analysis-and-then-refloorplan approach. Our floorplans are routable, meet all timing constraints, and are on average 12%-13% smaller in area as compared to traditional floorplanning algorithms.

A new approach to the interconnect-driven floorplanning problem that integrates bus planning with floorplanning is presented. The integrated floorplanner is intended for bus-based designs. Each bus consists of a large number of wires. The floorplanner ensures routability by generating the exact location and shape of interconnects (above and between the circuit blocks) and optimizes the timing. Experiments with MCNC benchmarks clearly show the superiority of integrated floorplanning over the classical floorplan-analyze-and-then-re-floorplan approach. Our floorplans are routable, meet all timing constraints, and are on average 12-13% smaller in area as compared to the traditional floorplanning algorithms.

No abstract available.

As microprocessor design progresses from tens of millions of transistors on a chip using 0.18-/spl mu/m process technology to approximately a billion transistors on a chip using 0.10-/spl mu/m and finer process technologies, the microprocessor designer faces unprecedented Electronic Design Automation (EDA) challenges over the future generations of microprocessors. This paper describes the changes in the design environment that will be necessary to develop increasingly complex microprocessors. In particular, the paper describes the current status and the future challenges along three important areas in a design flow: design correctness, performance verification and power management.

This paper presents three minimum-area floorplanning algorithms that use flexible arbitrary rectilinear shapes for the standard cell regions in MBC design. The first algorithm (pure HCST) introduces a grid traversal technique which guarantees a minimum-area floorplan. The second algorithm (Hybrid-BF) uses a combination of HCST and Breadth First (BF) traversals to give a practical solution that approximately places flexible blocks at specified locations calledseeds. The third algorithm (Hybrid-MBF) improves on the shapes of the flexible blocks generated by Hybrid-BF by using a combination of HCST and a Modified Breadth First (MBF) traversal. All three algorithms are polynomial in the number of grid squares. Optimized implementations of Hybrid-BF and Hybrid-MBF required less than two seconds on a SUN SPARCstation 10.

VLSI fabrication has entered the deep sub-micron era and communication between different components has significantly increased. Interconnect delay has become the dominant factor in total circuit delay. As a result, it is necessary to start interconnect planning as early as possible. We propose a method to combine interconnect planning with floorplanning. Our approach is based on the Wong-Liu (1986) floorplaning algorithm. When the positions, orientations, and shapes of the cells are decided, the pin positions and routing of the interconnects are decided as well. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperature to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Experimental results show that our approach performs well.

Transistor density on an integrated circuit continues to grow at an exponential rate. The associated complexities when applied to synthesis, layout, and timing analysis will become untenable within the framework of our current technological capabilities. This paper briefly outlines the problems facing the semiconductor industry early into the next decade. A SRC research thrust team consisting of members from various companies prioritized these problems and established a top ten list. This paper includes both problem descriptions as well as metrics to benchmark proposed solutions.

This paper identifies important objectives that an MBC floorplanner using flexible, arbitrary rectilinear shapes for standard cell regions should achieve including area minimization, proximity, and connectivity. It then presents an algorithm that guarantees area minimization and connectivity and gives good results with respect to proximity.

In this paper, we consider the two row maximum planar subset (TRMPS) problem in over-the-cell routing. The TRMPS problem requires selection of the maximum planar subset of nets, which can be routed between two rows of terminals in a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They stated the complexity of this problem to be unknown, and presented a min {1,k/d(S)} approximation algorithm, where k is the number of tracks available over the cell area and d(S) is the density of a solution S. We show that TRMPS problem can be solved optimally in polynomial time. We present a O(kn/sup 2/) dynamic programming algorithm for the TRMPS problem, where n is the number of nets. We also present a parallel version of our algorithm, which has a complexity of O(kn). Our algorithm can also be extended to solve the TRMPS problem, in the presence of prerouted nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain a 0.5 approximation, for over the cell routing in middle terminal model, thus improving the best known existing algorithm. The weighted version of the TRMPS problem, as well as, all the extensions can also be solved in O(kn/sup 2/) time.

In this paper we solve the planar over-the-cell routing problem, in which nets must have at least one terminal on the boundary. Such nets allow for nontraditional cell designs, where all terminals must be placed on the boundaries giving a degree of freedom to the cell designer. We present a dynamic programming algorithm that optimally solves this problem, in O(K/sup 2/n/sup 4/) time, where K is the number of tracks available over the cell for a given cell row region, and n is the number of nets to be routed.

Several Ov er-the-Cell (OTC) routing algorithms have been proposed for two and three layer processes.All the existing OTC routers can be used only on the cell models for whic h they were developed for.In this paper, we develop a uni ed approach t o m ulti-layer routing, motiv ated by o v er-the-cell routing, which can be used for full-custom la youts.Our approac h can also be directly applied to standard cell layouts, irrespective of the cell model used in the design.Our router has been implemen ted in C and tested on industrial benchmarks, suc h as PRIMARY I and PRIMARY I I , for which it obtained channel-less layouts.

Abstract- In this paper, we present a new routing approach for MCMs in which the routing space is partitioned into several towers. The routing is carried out in three steps. In the rst step, the routing density is uniformly distributed over the three dimensional routing space. In the next step, the exact locations of nets on the faces of each tower are determined. Finally, the exact paths for the nets in each tower are determined and routed. Unlike the traditional MCM routing which converts the three dimensional routing problem into a set of two dimensional routing problems, our approach decomposes the problem into a set of smaller, yet three dimensional tower routing problems. Experimental results show the validity of our methodology. 1

The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.>

In this paper, we present ARCHITECT, the floorplanner for high performance Mixed Block and Cell designs. A novel and significant feature of ARCHITECT is that it exploits the flexibility of the standard cell regions by generating arbitrary rectilinear shapes for the flexible blocks. We have implemented ARCHITECT on a Sun SPARC station 1+ using C and Xview. We have tested the floorplanner on various randomly generated examples. Experimental results indicate that ARCHITECT generates floorplans with minimal white space within the user specified bounds.>

Recently four new cell models have been developed for over the cell routing. The usefulness of a cell model cannot simply be determined by utilization of OTC areas since cell widths, gate delays and layout parameters must also be considered. In this paper, we develop standard cells libraries in all the four models and compare the cell width and gate delay analysis of the cells. We also study the parameters which contribute to the variation in cell widths and gate delay between the different cell models. We show that the main parameters which contribute to the difference in cell widths in the four models are the number of terminals, intracell routing and cell functionality.>

In this paper, we present an hierarchical clock routing scheme, which minimizes the longest source to sink path, and obtains a path balanced clock tree with minimal total wirelength. Our scheme takes into consideration, the hierarchical design of a circuit. Our approach is applicable to large VLSI circuits and MCM's. The algorithm has been implemented and experimental results are encouraging.>

Several Over-the-Cell (OTC) routing algorithms have been proposed for two and three layer processes. All the existing OTC routers assume that the terminals are laid out in a specific predetermined fashion. These restrictions on the terminals complicate the task of cell design and increase the width of the cells. In this paper, we develop a four layer OTC router which allows arbitrary terminal locations. Freed from fixed terminal placement restrictions, cell designers can aim to design with minimum width. Our router has been implemented and tested on several circuits. For most of the circuits, it obtained channel-less layouts.>

A provably good approximation algorithm for the multilayer topological planar routing problem is presented. The algorithm, called the iterative-peeling algorithm, finds a solution whose weight is guaranteed to be at least 1-(1/e) approximately=63.2% of the weight of an optimal solution. The algorithm works for multiterminal nets and arbitrary number of routing layers. For a fixed number of routing layers, even tighter performance bounds are used. In particular, the performance ratio of the iterative-peeling algorithm is at least 75% for two-layer routing and is at least 70.4% for three-layer routing. Experimental results confirm that the algorithm can always route a majority of the nets without using vias, even when the number of routing layers is fairly small.>

The WISER algorithm for over-the-cell channel routing in the standard cell design style using the two-layer routing model is presented. The novelty of this approach lies in the use of vacant terminals for over-the-cell routing. Longest paths in the vertical constraint graph and channel density are considered as a basis for choosing nets to route over the rows of standard cells. WISER has been implemented and tested on several benchmarks, including PRIMARY1 and Deutsch's difficult example. The experimental results show that WISER reduces the channel height by an average of 29%, as compared to conventional channel routers, and 15%, as compared to existing over-the-cell routers. In addition, it reduces the total number of vias per routing by 32%.>

A new class of cell models called middle terminal models (MTM) is introduced. MTM-based cells allow flexibility in the selection of terminal locations and therefore utilize the over-the-cell (OTC) area more efficiently, as compared to cells based on existing models. For MTM-based designs, two new routers, MTM+V and MTM-V are presented. The first router is suitable for processes that allow vias over-the-cell and is based on an optimal Theta (K) algorithm for terminal row selection for over-the-cell channel routing, where K is the number of cell rows. The second router is suitable for the processes which do not allow vias in over-the-cell areas. This router consists of two key steps. The first step consists of the selection of a maximum planar set of nets for routing in between the terminal rows. For the second step, an optimal algorithm is developed for planar routing between the terminal row and the cell boundary. The experimental results on the PRIMARY I benchmark show that for a two-layer model, MTM-V performs 4.20% better than the best existing routers.>

In the model considered, a channel is partitioned into several regions and each region consists of tracks of equal length segments, but segment length is varied uniformly across the regions. Each region is allocated a certain number of tracks. The segments are arranged in a staggered fashion. In order to make optimum use of the model, a routing algorithm is developed. The key feature of the routing algorithm is the assignment of the nets to the appropriate tracks by delay computation and delay matching techniques. Experimental results show that the model and the algorithm improve the longest net delay by as much as 75.16% and the average net delay by 48.28% as compared to the conventional uniformly segmented model.>

A clock routing algorithm for two-phase clock systems is presented. The algorithm, which minimizes both intraclock skew and interclock skew, has been implemented on SPARC 1+ in C and has been tested on several industrial benchmarks as well as on randomly generated examples. In particular, the result was tested for a 267 synchronous component circuit at clock rates of 100 MHz. It is significant that this is the first ever result which deals with multiple clock routing with zero skew.>

In this paper, we present a new algorithm, called WISER, for over-the-cell channel routing in the standard cell design technology using the two-layer routing model. The novelty of our approach lies in use of “vacant” terminals for over-the-cell routing. Furthermore, we consider longest paths in the vertical constraint graph as well as channel density as a basis for choosing nets to route over the rows of standard cells. Our approximation algorithm for net selection produces provably good results. Algorithm WISER has been tested on several benchmark examples, and experimental results show that WISER reduces the channel height by an average of 29% as compared to conventional channel routers. In addition, it reduces the total number of vias by 32% in the average case.

The authors present a novel algorithm for three-layer, over-the-cell channel routing of standard cell designs. The novelty of the proposed approach lies in the use of 'vacant' terminals for over-the-cell routing. Furthermore, the authors consider both the maximum cliques in the horizontal constraint graph and the longest paths in the vertical constraint graph as a basis for choosing the nets to route over the cells. They prove that their net selection algorithm is guaranteed to produce a solution within 68% of the optimum. The proposed algorithm has been implemented and tested on several benchmark examples. For the entire PRIMARY 1 benchmark, they reduce the total routing height by 76% as compared to a two-layer channel router, which leads to a 7% reduction in chip height.>

The authors consider the topological via minimization problem in a bounded region. The problem is known to be NP-complete. An approximation algorithm is proposed for this problem, which solves the two-layer topological via minimization problem in a bounded region with at most 0.25m* more vias than the optimal number of vias, where m* is the size of the maximum two-planar subset of nets for the given problem. A graph-theoretic heuristic algorithm is also proposed to obtain a geometric routing from a topological solution.>

The authors consider a problem related to global routing of multiterminal nets in VLSI layout. They investigate the problem of finding the minimum Steiner tree in the presence of obstacles when the terminals lie on the boundary of a rectangle (RSTO) and present two results. The first contribution is an exact solution for finding the rectilinear Steiner tree in the presence of an obstacle when the terminals lie on the boundary of a rectangle. Second, an approximation algorithm for RSTO in the presence of k obstacles is given. It is shown that the algorithm has a tight performance bound. A heuristic algorithm which produces solutions very close to the optimal is given.>

In this paper, we present a new gridless three layer channel router (MISER) based on an integrated approach to routing and compaction. MISER partitions the input net-list into several sub net-lists called levels and forms a level graph. This level graph is used to guide the routing and compaction process. Compaction is done immediately after each level is routed. Experimental results show that our algorithm usually performs 5-10% better than existing three layer channel routing algorithms.

In this paper, we present a new heuristic algorithm for the classical single row routing problem. The algorithm is based on a graph theoretic decomposition scheme and uses modified cut-numbers. The algorithm was implemented in C on VAX 8200. The experimental results show that the quality of solutions generated by our algorithm could be up to 36% better as compared to the existing algorithms.