Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-12-18
2001-11-27
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06324675
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to wire routing within the field of electronic design automation used in the design and fabrication of integrated circuit devices.
2. Related Art
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist and automate most steps of the circuit design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually. To automate the circuit design and fabrication of integrated circuit devices, electronic design automation (EDA) systems have been developed.
An EDA system is a computer software system designers used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated by the EDA system into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes. (elements) and edges, e.g., connections between nodes, and can be represented using a directed cyclic graph structure having nodes which are connected to each other with signal lines. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device.
More specifically, within a typical EDA system, the circuit designer first produces a high-level description of the circuit in a hardware description language such as Verilog or VHDL. This high-level description is converted into a netlist using a computer implemented synthesis process such as a the “Design Compiler” by Synopsys of Mountain View, Calif. A netlist is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (“nets”). Importantly, the netlist does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of a computer controlled placement process and a computer controlled routing process.
The placement process finds a location for each cell on a circuit board or silicon chip. The locations are specified, typically, in two dimensional spatial coordinates, e.g., (x, y) coordinates, on the circuit board or silicon chip. The locations are typically selected to optimize certain objectives such as wire length, wire routibility, circuit speed, circuit power consumption, and/or other criteria, subject to the condition that the cells are spread evenly over the circuit board or silicon chip and that the cells do not overlap with each other. The output of the automatic computer controlled cell placement process includes a data structure including the (x, y) location for each cell of the IC design.
Next, the designer supplies the netlist and the cell location data structure, generated by the placement program, to a computer implemented automatic wire routing process (“router”). The router generates wire geometry within data structure for connecting pins together. The wire geometry data structure and cell placement data structure together are used to make the final geometric database needed for fabrication of the circuit. Routers typically include a course routing process and a fine routing process. The coarse router provides a general path for the routing that is done at the detail stage. The coarse router examines at the level of the whole integrated circuit chip and its available resources and determines what the rough pathways should be from a topological standpoint. The fine or detail router lays down the actual geometries and connected wire segments in the appropriate layers as a wire connection may span multiple layers. The fine router creates wire routes that are “clean,” e.g., do not have design rule violations, do not overlap other structures and can be fabricated.
FIG. 1
illustrates a layout configuration
10
used in a typical grid-based router. Within a grid-based router, wires are routed along defined and equally spaced grid lines of a grid array. Horizontal
30
and vertical
32
grid lines are shown for an exemplary grid array of layout
10
. To route wires between a source pin and a target (e.g., destination) pin, the grid lines must be used in a grid-based router. For instance, wire route
18
that couples pins on block
12
and
14
utilizes, and is aligned with, the horizontal and vertical grid lines. Grid lines of the grid array are used in the routing process to speed up the process of finding the wire routing solutions by reducing the number of pathways to consider for routing. However, the grid-based router approach also has several disadvantages which are described below.
One disadvantage of grid-based routers is that they have trouble routing with circuit blocks that do not use a single defined grid array, as is common in today's complex circuit implementations. Modern integrated circuit designs (e.g., “system-on-a-chip” designs) typically include several custom integrated circuit designs that are implemented by different companies. Therefore, these custom designs may or may not use the same grid array dimensions as used by the layout
10
of FIG.
1
. Further, hand-designed integrated circuits, like circuit
16
, may not even use any grid array at all. For instance, pins
4
and pins
6
of the custom designs
12
and
14
, respectively, do not align with the grid array of grid lines
30
and
32
because these circuit blocks use a different dimension grid array. This causes a problem for the grid-based router because pins
6
and
4
do not match the grid array of layout
10
and special time consuming attention needs to be paid to these pins. In some cases, the grid-based router does not have any mechanism for dealing with pins that do not align with the main grid array.
Another disadvantage of grid-based routing is that the routing problem is not really a grid-based problem to begin with. In a grid-based router, the grid array is used to locate minimum cQst wire routes. However, wire routing really depends on wire length, wire width and wire separation, not a predefined wire grid array. Wire length and wire geometry dictate signal delay which is an ever increasingly large consideration in modern sub-micron designs. To reduce delay, the wires can be made wider and can be separated a greater distance from each other. Therefore, forcing wires to lie on predefined grid lines does not really address the greater underlying problem of signal delay.
Another disadvantage of grid-based routing is that it tends to waste a large percentage of routable area within an integrated circuit substrate. For instance, consider wire route
20
between block
14
and block
16
. This route
20
, as shown, is located between grid lines
32
b
and
32
a
. If this route
20
were made in the grid array it would consume (e.g., occupy) both of the adjacent grid lines
32
b
and
32
a
, even though there is room to run other wires between these grids lines and wire route
20
. In a grid-based router, when adjacent grid lines are occupied, it is not possible to route a wire there though even though there might be room for such.
Accordingly, what is needed is a routing proc
Dutta Robi
Rao Ravi
Vittal Ashok
Garbowski Leigh Marie
Smith Matthew
Synopsys Inc.
Wagner , Murabito & Hao LLP
LandOfFree
Efficient iterative, gridless, cost-based fine router for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient iterative, gridless, cost-based fine router for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient iterative, gridless, cost-based fine router for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2616927