Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-01-13
2003-09-09
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06618849
ABSTRACT:
FIELD OF THE INVENTION
The invention provides method and apparatus for identifying routes for nets.
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. The method next determines whether a storage structure stores a set of routes for the identified first set of sub-regions. If so, the method retrieves the set of routes. If not, the method generates a set of routes. In some embodiments, the method generates a set of routes by first identifying a connection set of sub-regions that when combined with the first set forms a closed set of sub-regions. The closed set of sub-regions does not have any sub-region that is not adjacent to another sub-region in the closed set. The storage structure stores a set of routes for the closed set. For the first set, the method then retrieves the set of routes that are stored for the closed set of sub-regions from the storage structure.
REFERENCES:
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6260183 (2001-07-01), Raspopovic et al.
patent: 6324674 (2001-11-01), Andreev et al.
Chao Heng-Yi
Teig Steven
Cadence Design Systems Inc.
Dinh Paul
Stattler Johansen & Adeli LLP
LandOfFree
Method and apparatus for identifying routes for nets 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 identifying routes for nets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for identifying routes for nets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052402