US6412102B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Wire routing optimization
Assignee: Bell Semiconductor LLC
•
Filing: 1998-07-22
•
Granted: 2002-06-25
•
Expires: 2018-07-22
Abstract
Abstract 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. The invention is also 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 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 first set overlaps at least two pre-defined areas in the second set, and each of plural pre-defined areas in the second set overlaps at least two pre-defined areas in the first set.
Inventors
- 👤 Alexander Andreev
- 👤 Ivan Pavisic
- 👤 Pedja Raspopovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:43
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
273 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: a dividing step of dividing the surface into a set of areas; a boundary pin defining step of defining a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization step of independently performing a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting step of shifting the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating step of eliminating the boundary pins defined in said boundary pin defining step; a second boundary pin defining step of defining a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization step of independently performing a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 2
Independent Claim
273 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: a dividing step of dividing the surface into a set of areas; a boundary pin defining step of defining a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization step of independently performing a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting step of shifting the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating step of eliminating the boundary pins defined in said boundary pin defining step; a second boundary pin defining step of defining a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization step of independently performing a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 3
Dependent Claim
20 words
A method according to claim 1 , wherein the surface is at least a portion of an integrated circuit die.
Claim 4
Dependent Claim
22 words
A method according to claim 2 , wherein the initial routing is implemented on plural metal layers of the integrated circuit die.
Claim 5
Dependent Claim
29 words
A method according to claim 1 , wherein each of the areas has a size of approximately twice an expected average net size in each of length and width.
Claim 6
Dependent Claim
28 words
A method according to claim 1 , wherein the shifting step shifts each boundary of the areas by a same amount to obtain the second set of areas.
Claim 7
Independent Claim
151 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: a first dividing step of dividing the surface into a first set of pre-defined areas; a first routing optimization step of performing routing optimization independently in each of the pre-defined areas in the first set; a second dividing step of dividing the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization step of performing routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
Claim 8
Independent Claim
151 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: a first dividing step of dividing the surface into a first set of pre-defined areas; a first routing optimization step of performing routing optimization independently in each of the pre-defined areas in the first set; a second dividing step of dividing the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization step of performing routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
Claim 9
Dependent Claim
20 words
A method according to claim 6 , wherein the surface is at least a portion of an integrated circuit die.
Claim 10
Dependent Claim
22 words
A method according to claim 7 , wherein the initial routing is implemented on plural metal layers of the integrated circuit die.
Claim 11
Dependent Claim
17 words
A method according to claim 6 , wherein the pre-defined areas in the first set are rectangular-shaped.
Claim 12
Dependent Claim
32 words
A method according to claim 6 , wherein the second set of pre-defined areas is formed by shifting boundaries of the pre-defined areas in the first set in only a single dimension.
Claim 13
Dependent Claim
53 words
A method according to claim 10 , wherein each area in the first set of pre-defined areas has a characteristic length in the single dimension, and wherein the first set of pre-defined areas is shifted approximately one-half of the characteristic length in the single dimension to obtain the second set of pre-defined areas.
Claim 14
Dependent Claim
45 words
A method according to claim 6 , further comprising: a third dividing step of dividing the surface into a third set of pre-defined areas; and a third routing optimization step of performing routing optimization independently in each of the pre-defined areas in the third set.
Claim 15
Dependent Claim
42 words
A method according to claim 12 , wherein each area in the second set overlaps at least two pre-defined areas in the third set, and wherein each area in the third set overlaps at least two pre-defined areas in the second set.
Claim 16
Dependent Claim
42 words
A method according to claim 13 , wherein each area in the first set overlaps at least two pre-defined areas in the third set, and wherein each area in the third set overlaps at least two pre-defined areas in the first set.
Claim 17
Dependent Claim
27 words
A method according to claim 12 , wherein the third set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the second set.
Claim 18
Dependent Claim
43 words
A method according to claim 6 , wherein the routing optimization performed on the pre-defined areas in the first set and the routing optimization performed on pre-defined areas in the second set are executed so as to re-route connections routed through congested areas.
Claim 19
Dependent Claim
43 words
A method according to claim 6 , wherein the routing optimization performed on the pre-defined areas in the first set and the routing optimization performed on pre-defined areas in the second set are identical to each other and similar to the initial routing.
Claim 20
Dependent Claim
52 words
A method according to claim 6 , further comprising a boundary pin defining step of defining a boundary pin at each point on a boundary of one of the pre-defined areas in the first set where the boundary of the one of the pre-defined areas in the first set intersects a net.
Claim 21
Dependent Claim
32 words
A method according to claim 6 , wherein the second set of pre-defined areas is obtained by shifting each boundary of the pre-defined areas in the first set by a same amount.
Claim 22
Independent Claim
115 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: dividing the surface into a first set of pre-defined areas; performing routing optimization independently in each of the pre-defined areas in the first set; dividing the surface into a second set of pre-defined areas; and performing routing optimization independently in each of the pre-defined areas in the second set, wherein each of plural pre-defined areas in the first set overlaps at least two pre-defined areas in the second set, and wherein each of plural pre-defined areas in the second set overlaps at least two pre-defined areas in the first set.
Claim 23
Independent Claim
115 words
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising: dividing the surface into a first set of pre-defined areas; performing routing optimization independently in each of the pre-defined areas in the first set; dividing the surface into a second set of pre-defined areas; and performing routing optimization independently in each of the pre-defined areas in the second set, wherein each of plural pre-defined areas in the first set overlaps at least two pre-defined areas in the second set, and wherein each of plural pre-defined areas in the second set overlaps at least two pre-defined areas in the first set.
Claim 24
Dependent Claim
279 words
A computer-readable medium storing computer-executable process steps for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said process steps comprising: a dividing step to divide the surface into a set of areas; a boundary pin defining step to define a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization step to independently perform a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting step to shift the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating step to eliminate the boundary pins defined in said boundary pin defining step; a second boundary pin defining step to define a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization step to independently perform a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 25
Dependent Claim
279 words
A computer-readable medium storing computer-executable process steps for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said process steps comprising: a dividing step to divide the surface into a set of areas; a boundary pin defining step to define a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization step to independently perform a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting step to shift the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating step to eliminate the boundary pins defined in said boundary pin defining step; a second boundary pin defining step to define a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization step to independently perform a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 26
Dependent Claim
21 words
A computer-readable medium according to claim 21 , wherein the surface is at least a portion of an integrated circuit die.
Claim 27
Dependent Claim
23 words
A computer-readable medium according to claim 22 , wherein the initial routing is implemented on plural metal layers of the integrated circuit die.
Claim 28
Dependent Claim
28 words
A computer-readable medium according to claim 21 , wherein each of the areas has a size of approximately twice an expected average net size in each corresponding dimension.
Claim 29
Dependent Claim
29 words
A computer-readable medium according to claim 21 , wherein the shifting step shifts each boundary of the areas by a same amount to obtain the second set of areas.
Claim 30
Dependent Claim
157 words
A computer-readable medium storing computer-executable process steps for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said process steps comprising: a first dividing step to divide the surface into a first set of pre-defined areas; a first routing optimization step to perform routing optimization independently in each of the pre-defined areas in the first set; a second dividing step to divide the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization step to perform routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
Claim 31
Dependent Claim
157 words
A computer-readable medium storing computer-executable process steps for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said process steps comprising: a first dividing step to divide the surface into a first set of pre-defined areas; a first routing optimization step to perform routing optimization independently in each of the pre-defined areas in the first set; a second dividing step to divide the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization step to perform routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
Claim 32
Dependent Claim
21 words
A computer-readable medium according to claim 26 , wherein the surface is at least a portion of an integrated circuit die.
Claim 33
Dependent Claim
54 words
A computer-readable medium according to claim 26 , wherein each area in the first set of pre-defined areas has a characteristic length in the single dimension, and wherein the first set of pre-defined areas is shifted approximately one-half of the characteristic length in the single dimension to obtain the second set of pre-defined areas.
Claim 34
Dependent Claim
50 words
A computer-readable medium according to claim 26 , wherein said process steps further comprise: a third dividing step to divide the surface into a third set of pre-defined areas; and a third routing optimization step to perform routing optimization independently in each of the pre-defined areas in the third set.
Claim 35
Dependent Claim
57 words
A computer-readable medium according to claim 26 , wherein said process steps further comprise a boundary pin defining step to define a boundary pin at each point on a boundary of one of the pre-defined areas in the first set where the boundary of the one of the pre-defined areas in the first set intersects a net.
Claim 36
Dependent Claim
33 words
A computer-readable medium according to claim 26 , wherein the second set of pre-defined areas is obtained by shifting each boundary of the pre-defined areas in the first set by a same amount.
Claim 37
Independent Claim
273 words
An apparatus for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said apparatus comprising: a dividing means for dividing the surface into a set of areas; a boundary pin defining means for defining a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization means for independently performing a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting means for shifting the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating means for eliminating the boundary pins defined by said boundary pin defining means; a second boundary pin defining means for defining a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization means for independently performing a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 38
Independent Claim
273 words
An apparatus for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said apparatus comprising: a dividing means for dividing the surface into a set of areas; a boundary pin defining means for defining a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization means for independently performing a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting means for shifting the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating means for eliminating the boundary pins defined by said boundary pin defining means; a second boundary pin defining means for defining a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization means for independently performing a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.
Claim 39
Independent Claim
151 words
An apparatus for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said apparatus comprising: a first dividing means for dividing the surface into a first set of pre-defined areas; a first routing optimization means for performing routing optimization independently in each of the pre-defined areas in the first set; a second dividing. means for dividing the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization means for performing routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
Claim 40
Independent Claim
151 words
An apparatus for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said apparatus comprising: a first dividing means for dividing the surface into a first set of pre-defined areas; a first routing optimization means for performing routing optimization independently in each of the pre-defined areas in the first set; a second dividing. means for dividing the surface into a second set of pre-defined areas, wherein the second set of pre-defined areas is obtained by shifting boundaries of the pre-defined areas in the first set; and a second routing optimization means for performing routing optimization independently in each of the pre-defined areas in the second set, wherein each area in the first set overlaps at least two pre-defined areas in the second set, and wherein each area in the second set overlaps at least two pre-defined areas in the first set.
References Cited (Backward Citations)
US4612618A
Cited
US4831725A
Cited
US5420800A
Cited
US5583788A
Cited
US5566078A
Cited
US5495419A
Cited
US5838585A
Cited
US5856927A
Cited
US5699265A
Cited
US5909376A
Cited
US5798936A
Cited
US5872718A
Cited
US5963455A
Cited
US6067409A
Cited
US6068662A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-06-24 | 2005-12-24 | 2006-06-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-06-24 | 2009-12-24 | 2010-06-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-06-24 | 2013-12-24 | 2014-06-25 | $7700.00 | Window Closed / Lapsed |