Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-01-04
2004-09-21
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06795958
ABSTRACT:
FIELD OF THE INVENTION
The invention is directed towards method and apparatus for generating routes for groups of related net configurations.
BACKGROUND OF THE INVENTION
An integrated circuit (“IC”) is a device that includes many electronic components (e.g., transistors, resistors, diodes, etc.). These components are often interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit components of IC's are jointly referred to below as “components.”
An IC also includes multiple layers of wiring (“wiring layers”) that interconnect its electronic and circuit components. For instance, many IC's are currently fabricated with metal or polysilicon wiring layers (collectively referred to below as “metal layers”) that interconnect its electronic and circuit components. One common fabrication model uses five metal layers. In theory, the wiring on the metal layers can be all-angle wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is commonly referred to as Euclidean wiring. In practice, however, each metal layer typically has a preferred wiring direction, and the preferred direction alternates between successive metal layers. Many IC's use the Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring. In this wiring model, the majority of the wires can only make 90° turns. However, occasional diagonal jogs are sometimes allowed on the preferred horizontal and vertical layers.
Design engineers design IC's by transforming circuit description of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.
EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectangular lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. For the sake of simplifying the discussion, these geometric objects are shown as rectangular blocks in this document.
Also, in this document, the phrase “circuit module” refers to the geometric representation of an electronic or circuit IC component by an EDA application. EDA applications typically illustrate circuit modules with pins on their sides. These pins connect to the interconnect lines.
A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a net list. In other words, a net list specifies a group of nets, which, in turn, specify the interconnections between a set of pins.
FIG. 1
illustrates an example of an IC layout
100
. This layout includes five circuit modules
105
,
110
,
115
,
120
, and
125
with pins
130
-
160
. Four interconnect lines
165
-
180
connect these modules through their pins. In addition, three nets specify the interconnection between the pins. Specifically, pins
135
,
145
, and
160
define a three-pin net, while pins
130
and
155
, and pins
140
and
150
respectively define two two-pin nets. As shown in
FIG. 1
, a circuit module (such as
105
) can have multiple pins on multiple nets.
The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; (5) compaction, which compresses the layout to decrease the total IC area; and (6) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a “loose” route (also called path or routing areas) for the interconnect lines that are to connect the pins of the net. The “looseness” of a global route depends on the particular global router used. After global routes have been created, the detailed routing creates specific individual routing paths for each net.
While some commercial global routers today might allow an occasional diagonal jog, these routers do not typically explore diagonal routing paths consistently when they are specifying the routing geometries of the interconnect lines. This, in turn, increases the total wirelength (i.e., total length of interconnect lines) needed to connect the nets in the layout. Therefore, there is a need for routing method and apparatus that considers diagonal routing paths.
SUMMARY OF THE INVENTION
Some embodiments of the invention provide a method that identifies a set of routes for a net that has a set of pins in a region of a design layout. The method initially partitions the region into a number of sub-regions. It then identifies a first set of sub-regions that contains the net's pins. Based on the first set of sub-regions, the method identifies a first route that traverses a second set of sub-regions. The first and second sets of sub-regions have a particular relationship. Based on this particular relationship, the method identifies a second route from the first route, where the second route traverses the first set of sub-regions.
REFERENCES:
patent: 4593363 (1986-06-01), Burstein et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4673966 (1987-06-01), Shimoyama
patent: 4782193 (1988-11-01), Linsker
patent: 4855929 (1989-08-01), Nakajima
patent: 5097422 (1992-03-01), Corbin, II et al.
patent: 5251147 (1993-10-01), Finnerty
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5281151 (1994-01-01), Arima et al.
patent: 5360948 (1994-11-01), Thornberg
patent: 5375069 (1994-12-01), Satoh et al.
patent: 5532934 (1996-07-01), Rostoker
patent: 5566078 (1996-10-01), Ding et al.
patent: 5578840 (1996-11-01), Scepanovic
patent: 5587923 (1996-12-01), Wang
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5633479 (1997-05-01), Hirano
patent: 5634093 (1997-05-01), Ashida et al.
patent: 5635736 (1997-06-01), Funaki et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5637920 (1997-06-01), Loo
patent: 5640327 (1997-06-01), Ting
patent: 5650653 (1997-07-01), Rostoker et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5717600 (1998-02-01), Ishizuka
patent: 5723908 (1998-03-01), Fuchida et al.
patent: 5742086 (1998-04-01), Rostoker et al.
patent: 5757089 (1998-05-01), Ishizuka
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 5777360 (1998-07-01), Rostoker et al.
patent: 5784289 (1998-07-01), Wang
patent: 5798936 (1998-08-01), Cheng
patent: 5811863 (1998-09-01), Rostoker et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5859449 (1999-01-01), Kobayashi et al.
patent: 5889677 (1999-03-01), Yasuda et al.
patent: 5898597 (1999-04-01), Scepanovic et al.
patent: 5914887 (1999-06-01), Scepanovic et al.
patent: 5973376 (1999-10-01), Rostoker et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6035108 (2000-03-01), Kikuchi
patent: 6058254 (2000-05-01), Scepanovic et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6068662 (2000-05-01), Scepanovic et al.
patent: 6070108 (2000-05-01), Andreev et al.
patent: 6123736 (2000-09-01), Pavisic et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6134702 (2000-10-01), Scepanovic et al.
patent: 6150193 (2000-11-01), Glenn
patent: 6155725 (2000-12-01), Scepanovic et al.
patent:
Ganley Joseph L.
Teig Steven
Cadence Design Systems Inc.
Lin Sun James
Smith Matthew
Stattler Johansen & Adeli LLP
LandOfFree
Method and apparatus for generating routes for groups of... 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 generating routes for groups of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating routes for groups of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3210404