US5825659A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for local rip-up and reroute of signal paths in an IC design
Assignee: Bell Semiconductor LLC
•
Filing: 1995-06-16
•
Granted: 1998-10-20
•
Expires: 2015-06-16
Abstract
Abstract The present invention provides a local rip-up and reroute (LRR) method to reduce the number of open nets after the initial routers have been applied. Two main tasks are performed under this method. The first task is to identify a locally blocked pin and rip up wire segments in an area around the cell having the locally blocked pin. The second task is to reroute the now freed locally blocked pin. In the first task, an open net is read from the list of open nets. The pins of this open net are identified and determined if they are locally blocked. A pin is considered as locally blocked if a routing path, starting from the pin, cannot be found within N grid point expansions. If a pin is locally blocked, segments of wires within or at the boundary of a predefined bounding box are removed (or ripped-up)--except for two situations. The first exception is that a wire that is connected to a pin is not ripped-up. The second exception is that a SM wire segment that occupies only one horizontal track running through both boundaries of the bounding box is not ripped-up. The ripped-up nets are placed on a removed-net list for later rerouting.
Inventors
- 👤 Lieu T. Nguyen
- 👤 Kwok Ming Yue
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:17
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
142 words
A method for determining a routing path to complete an open net in an integrated circuit design, said open net being completed by connecting pins of two or more cells of the net with wire segments extending along the determined routing path, said integrated circuit design being laid out on at least one layer that is evenly divided by arrays of grid points disposed on said layer, comprising the steps of: a) selecting a pin from a cell of an open net; b) determining if said pin is locally blocked; and c) if said pin is locally blocked, i) generating a bounding box along grid points circumscribing said cell and spaced therefrom a predetermined distance, ii) removing existing wire segments within said bounding box, and iii) finding a routing path from said pin to one or more designated pins within said net.
Claim 2
Independent Claim
142 words
A method for determining a routing path to complete an open net in an integrated circuit design, said open net being completed by connecting pins of two or more cells of the net with wire segments extending along the determined routing path, said integrated circuit design being laid out on at least one layer that is evenly divided by arrays of grid points disposed on said layer, comprising the steps of: a) selecting a pin from a cell of an open net; b) determining if said pin is locally blocked; and c) if said pin is locally blocked, i) generating a bounding box along grid points circumscribing said cell and spaced therefrom a predetermined distance, ii) removing existing wire segments within said bounding box, and iii) finding a routing path from said pin to one or more designated pins within said net.
Claim 3
Dependent Claim
71 words
A method as recited in claim 1 wherein a number of open nets are created when existing wire segments are removed and further including the following steps: iv) if an available routing path is found, routing said open net and the open nets created in step ii); and v) if an available routing path is not found, restoring the removed wire segments to their original locations in said integrated circuit design.
Claim 4
Dependent Claim
30 words
A method as recited in claim 2 wherein said pin is determined as locally blocked if a routing path is not found within a predetermined number of grid point expansions.
Claim 5
Dependent Claim
22 words
A method as recited in claim 3 wherein said bounding box is at least the same size as that of said cell.
Claim 6
Dependent Claim
29 words
A method as recited in claim 4 wherein as a first exception to said removing step, a wire segment connected to a pin of said cell is not removed.
Claim 7
Dependent Claim
37 words
A method as recited in claim 5 wherein as a second exception to said removing step, a wire segment passing through said bounding box on a second layer above or below said one layer is not removed.
Claim 8
Dependent Claim
30 words
A method as recited in claim 1 wherein said pin is determined as locally blocked if a routing path is not found within a predetermined number of grid point expansions.
Claim 9
Dependent Claim
22 words
A method as recited in claim 1 wherein said bounding box is at least the same size as that of said cell.
Claim 10
Dependent Claim
29 words
A method as recited in claim 1 wherein as a first exception to said removing step, a wire segment connected to a pin of said cell is not removed.
Claim 11
Dependent Claim
37 words
A method as recited in claim 1 wherein as a second exception to said removing step, a wire segment passing through said bounding box on a second layer above or below said one layer is not removed.
Claim 12
Independent Claim
89 words
A method for finding a signal path between cells of an open net in an integrated circuit design, wherein each of said cells has at least one pin, comprising the steps of: a) selecting a pin from a cell of said open net; b) determining if said pin is locally blocked; c) if said pin is locally blocked, removing existing wire segments within a bounding box surrounding said cell; and d) for the locally blocked pin, finding a routing path between pins of said cells of said open net.
Claim 13
Independent Claim
89 words
A method for finding a signal path between cells of an open net in an integrated circuit design, wherein each of said cells has at least one pin, comprising the steps of: a) selecting a pin from a cell of said open net; b) determining if said pin is locally blocked; c) if said pin is locally blocked, removing existing wire segments within a bounding box surrounding said cell; and d) for the locally blocked pin, finding a routing path between pins of said cells of said open net.
Claim 14
Dependent Claim
30 words
A method as recited in claim 11 wherein said pin is determined as locally blocked if a routing path is not found within a predetermined number of grid point expansions.
Claim 15
Dependent Claim
22 words
A method as recited in claim 12 wherein said bounding box is at least the same size as that of said cell.
Claim 16
Dependent Claim
29 words
A method as recited in claim 13 wherein as a first exception to said removing step, a wire segment connected to a pin of said cell is not removed.
Claim 17
Dependent Claim
37 words
A method as recited in claim 14 wherein as a second exception to said removing step, a wire segment passing through said bounding box on a second layer above or below said one layer is not removed.
Claim 18
Dependent Claim
22 words
A method as recited in claim 11 wherein said bounding box is at least the same size as that of said cell.
Claim 19
Dependent Claim
29 words
A method as recited in claim 11 wherein as a first exception to said removing step, a wire segment connected to a pin of said cell is not removed.
Claim 20
Dependent Claim
31 words
A method as recited in claim 11 wherein as a second exception to said removing step, a wire segment passing through said bounding box on a second layer is not removed.
Claim 21
Independent Claim
75 words
A method for finding a signal path between cells of an open net in an integrated circuit design, wherein each of said cells contains one or more pins, comprising the steps of: a) determining if any of said pins of said cells are locally blocked; b) removing existing wire segments within bounding boxes surrounding cells containing said locally blocked pins; and c) finding routing paths between said pins of said cells of said open net.
Claim 22
Independent Claim
75 words
A method for finding a signal path between cells of an open net in an integrated circuit design, wherein each of said cells contains one or more pins, comprising the steps of: a) determining if any of said pins of said cells are locally blocked; b) removing existing wire segments within bounding boxes surrounding cells containing said locally blocked pins; and c) finding routing paths between said pins of said cells of said open net.
Claim 23
Dependent Claim
31 words
A method as recited in claim 2 wherein if an available routing path is found, routing said open net only if said open nets created in step ii) can be routed.
Claim 24
Dependent Claim
33 words
A method as recited in claim 3 wherein said cell is of a predetermined size and the number of grid point expansions is determined as a function of the size of said cell.
Claim 25
Dependent Claim
33 words
A method as recited in claim 7 wherein said cell is of a predetermined size and the number of grid point expansions is determined as a function of the size of said cell.
Claim 26
Dependent Claim
33 words
A method as recited in claim 12 wherein said cell is of a predetermined size and the number of grid point expansions is determined as a function of the size of said cell.
Claim 27
Dependent Claim
27 words
A method as recited in claim 2 wherein if an available path is found, routing said open net only if no overall additional open net is created.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-19 | 2002-04-20 | 2002-10-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-19 | 2006-04-20 | 2006-10-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-19 | 2010-04-20 | 2010-10-20 | $7700.00 | Window Closed / Lapsed |