Reexamination Certificate
1997-08-06
2001-02-13
Teska, Kevin J. (Department: 2763)
Reexamination Certificate
active
06186676
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits. In particular, the present invention relates to the art of estimating wire routing on integrated circuit chips.
2. Description of Related Art
An integrated circuit chip (hereafter referred to as an “IC” or a “chip”) comprises of cells and connections between the cells formed on a surface of a semiconductor substrate. The IC may include a large number of cells and require complex connections between the cells.
A cell is a group of one or more circuit elements such as transistors, capacitors, and other basic circuit elements grouped to perform a function. Each of the cells of an IC may have one or more pins, each of which, in turn, may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip.
A net is a set of two or more pins which must be connected. Because a typical chip has thousands, tens of thousands, or hundreds of thousands of pins, which must be connected in various combinations, the chip also includes definitions of thousands, tens of thousands, or hundreds of thousands of nets, or sets of pins. All the pins of a net must be connected. The number of the nets for a chip is typically in the same order as the order of the number of cells on that chip. Commonly, a majority of the nets include only two pins to be connected; however, many nets comprise three or more pins. Some nets may include hundreds of pins to be connected. A netlist is a list of nets for a chip.
FIG. 1
shows a common organization of an IC. On a semiconductor substrate
10
, vertical strips of alternating columns
12
and channels
14
are defined. The cells
16
are fabricated in the columns, and the channels are typically used for running vertical wires to connect the pins
18
of the cells
16
. For illustrative purposes, only one wire is shown in FIG.
1
. In IC fabrication technology, it is common to use only the rectilinear connections as illustrated by the wire
20
. Therefore, all distances are measured using rectilinear or Manhattan distance method.
For simplicity, the chip
8
of
FIG. 1
shows only a few columns; however, in a practical implementation, it is common for a chip to have many hundreds of columns and channels, and hundreds of thousands of cells and about the same number of nets.
The channels of a chip are commonly used to run vertical wires for the chip. To run horizontal wires, another layer of material is fabricated on the surface of the chip. Via's are used to bring the pins up to the second layer for the horizontal connections. If the surface area is at premium, another, layer of material may be fabricated on top of the horizontal-wire layer. This third layer may be used to run the vertical wires and the width of the channels may be reduced to decrease the overall surface area requirement.
Because there are a large number of pins to connect and the complex nature of the connections required, a proper placement of the cells and the routing of the wires are critical for a successful implementation of a chip. Some placement and routing schemes may result in uneven distribution of cells and wires leading to congestion in some areas of the chip while other areas of the chip may be sparsely used.
After placement of the cells on the chip's surface, wire routing congestion must be analyzed. To determine the congestion levels, a common method has been to actually determine the routing of the wires for the chip. However, the routing process is very costly in computational time, and for mere finding of congested areas, not necessary.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide for a method and apparatus to quickly find a good global routing estimation on a chip. The method and apparatus disclosed herein quickly estimates the routing of wires, or edges, of an IC.
The present invention provides a method of determining the edges of wire routing of a net having pins. First, the a grid is defined. Second, connected-pin-sets (c-p-sets) are defined. Finally, the c-p-sets are connected and merged until only one c-p-set is remaining. The c-p-sets are connected and merged by connecting and merging two closest c-p-sets and repeating the process until only one c-p-set remains. Each of the connections are the edges. A c-p-set has a group of pins or Steiner pins.
The present invention also provides for an integrated circuit chip (IC) having been built using the quick routing method of the present invention.
The present invention also provides for an apparatus for determining the edges for routing a set of pins. The apparatus includes a processor which reads in a net, connects it to determine the edges, and writes a set of edges. To connect the net, the processor defines a grid and c-p-sets. The c-p-sets are connected and merged, two at a time, until a single c-p-set remains. The instructions for the processor is stored in memory, connected to the processor. The memory may be any machine-readable storage medium containing the instructions for the processor to perform the above-discussed steps.
These and other aspects, features, and advantages of the present invention will be apparent to those persons having ordinary skilled in the art to which the present invention relates from the foregoing description and the accompanying drawings.
REFERENCES:
patent: 5491641 (1996-02-01), Scepanovic et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5500804 (1996-03-01), Honsinger et al.
patent: 5568322 (1996-10-01), Azami et al.
patent: 5568636 (1996-10-01), Koford
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5615128 (1997-03-01), Scepanovic et al.
patent: 5625563 (1997-04-01), Rostoker et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5636129 (1997-06-01), Her
patent: 5638293 (1997-06-01), Scepanovic et al.
patent: 5661663 (1997-08-01), Scepanovic et al.
patent: 5682322 (1997-10-01), Boyle et al.
patent: 5712793 (1998-01-01), Scepanovic et al.
patent: 5742510 (1998-04-01), Rostoker et al.
patent: 5745363 (1998-04-01), Rostoker et al.
patent: 5808899 (1998-09-01), Scepanovic et al.
patent: 5841664 (1998-11-01), Cai et al.
Manjit Borah et al, [An Edge-Based Heuristic for Steiner Routing], Dec. 1994, IEEE 0278-0070/94 $04.00, pp. 198-203.
Manjit Borah et al., [Fast Algorithm for Performance-Oriented Steiner Routing], 1995, IEEE 1066-1395/95, pp. 1563-1568.
Andreev Alexander E.
Pavisic Ivan
Scepanovic Ranko
Knox Lonnie A.
LSI Logic Corporation
Mitchell Silberberg & Knupp LLP
Teska Kevin J.
LandOfFree
Method and apparatus for determining wire routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining wire routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining wire routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604702