Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-07-22
2002-06-25
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06412102
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns wire routing optimization, and particularly relates to wire routing optimization during integrated circuit (IC) design.
2. Description of the Related Art
To perform integrated circuit design in an efficient and relatively quick manner, the design process typically is implemented as a series of discrete steps. The starting point for the physical design step typically is a particular type of circuit description, called a “netlist”. In general, a netlist specifies a number of standard circuit elements, called “cells”, together with interconnections between the cells. More specifically, the netlist specifies interconnections between particular “pins” on the various cells. Each connected group of pins is referred to as a “net”. Based on the input netlist, the physical design step generates information which can be used to fabricate an integrated circuit to implement the specified circuit description.
One sub-step of physical design involves laying out (or placing) the cells on the surface of the integrated circuit chip (or die). After the cells have been so placed, wires are routed between pins on the cells as specified by the input netlist. It should be noted that wire routing refers to the mapping out of the intended paths for each connection, with the actual wires being formed during the fabrication step.
In particular, wires ordinarily are routed on one or more metal layers which are formed on top of a semiconductor substrate of the IC die. Currently, a typical IC die includes 2 to 4 metal layers. However, even more metal layers are contemplated. The routing step ordinarily includes a global routing step and a detailed routing step.
Global routing specifies rough routing paths through different regions of the routing space, such as by using a coarse routing grid. Detailed routing then completes the point-to-point connections between the pins based on the global routing information.
After an initial global routing has been completed, it is typically necessary or desirable to perform routing optimization, such as to re-route wires routed in overly congested regions. One example of such routing optimization is described in U.S. patent application Ser. No. 09/062,246 filed Apr. 17, 1998, titled “Method and Apparatus for Coarse Global Routing” , now U.S. Pat. No. 6,260,183. Application Ser. No. 09/062,246(the '246 Application) is hereby incorporated herein by reference, as though set forth herein in full.
The method for routing optimization described in the '246 Application is described as follows. For each net, two quotients are calculated: The length of net's bounding box divided by the length of the design, and the width of the net's bounding box divided by the width of the design. The larger of the two is termed the net's characteristic. This roughly suggests how large a part of design needs to be in order to contain the net's bounding box. The nets are then ordered in descending order according to this characteristic. The nets with a characteristic larger than ¼ are routed sequentially. Then, the design is split into four parts, and different processors are given different parts and instructed to route only the nets that are completely contained in the corresponding parts and have a characteristic that is larger than ⅛. Next, the parts are shifted to the right by a quarter of the design's length and the same operation is followed. The parts are then shifted from their original positions down by a quarter and the routing procedure is repeated. The parts are then shifted from their original positions both down and to the right by a quarter and the routing procedure is repeated. This way all nets with characteristics larger than ⅛ will be routed. Next the design is split into twice smaller parts, the nets of characteristic larger than {fraction (1/16)} are considered and the shifting process is repeated, moving the parts ⅛ instead of ¼. At this point, more processors can be included to speed up the routing process. This process is repeated a few times using smaller and smaller parts, and once all the processors are kept busy, all the remaining nets are re-routed.
Thus, in the foregoing routing optimization technique, the largest nets are processed first, and then the chip is divided into progressively smaller parts to accommodate nets of various sizes, with each part being assigned to a different processor. This technique therefore permits re-routing using parallel processing. However, applicants have discovered that the foregoing technique has certain disadvantages which can limit the speed of routing optimization. First, when using the above technique, each net is re-routed as a whole. As a result, a significant amount of processing time often is required in order to re-route very large nets according to this technique. In addition, maximum use of parallel processing can only be attained with the above technique when the lower levels of chip area division are reached.
FIG. 1
illustrates these problems with the foregoing approach. Specifically,
FIG. 1
illustrates an integrated circuit chip
1
upon which a net
5
is initially routed. Net
5
consists of pins
7
and interconnection segments
9
between the pins. As shown in
FIG. 1
, net
5
is larger than a single quadrant of the integrated circuit chip. Accordingly, net
5
is processed in its entirety in the first stage of the foregoing technique, before the chip is divided into smaller parts. As a result, the advantages of parallel processing are not realized when re-routing net
5
. Moreover, due to the size of net
5
, re-routing it very likely will require a large amount of processing time.
Therefore, a faster method of re-routing nets is desired.
SUMMARY OF THE INVENTION
The present invention addresses this need by dividing a surface, such as a surface of an IC chip, into a set of areas and defining boundary pins where nets intersect the boundary areas.
Thus, according to one aspect, the invention is directed to optimization of an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a set of areas, and a boundary pin is defined at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net. Routing optimization is then performed in at least one of the areas, the routing optimization optimizing the routing among the net pins and the boundary pins within the at least one of the areas.
By virtue of the foregoing arrangement, large nets frequently can be re-routed in smaller portions, which can have the effect of decreasing the amount of time required for routing optimization processing. In addition, use of boundary pins as set forth above generally will permit each area to be processed independently of the others, so as to allow a different processor to process each different area.
The present invention also addresses the foregoing need by independently performing routing optimization in pre-defined areas in a first set, and also independently performing routing optimization in pre-defined areas in a second set, where each of certain pre-defined areas in the first set overlap at least two pre-defined areas in the second set and each of certain pre-defined areas in the second se t overlap at least two pre-defined areas in the first set.
Thus, according to a further aspect, the invention is directed to optimization of an initial routing t hat connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a first set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the first set. The surface is divided into a second set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the second set. It is a feature of this aspect of the invention that each of plural pre-defined areas in the
Andreev Alexander
Pavisic Ivan
Raspopovic Pedja
LSI Logic Corporation
Mitchell Silberberg & Knupp LLP
Smith Matthew
Thompson A. M.
LandOfFree
Wire routing optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wire routing optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wire routing optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960509