US6330707B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic routing method
Assignee: DAIKIN MATSUSHITA ELECTRIC INDUSTRIAL Co Ltd
•
Filing: 1998-09-21
•
Granted: 2001-12-11
•
Expires: 2018-09-21
Abstract
Abstract First, initial routing is performed on a net. If a design rule error exists in a wire already routed as a result of the initial routing, the wire already routed, causing the design rule error, is removed. Next, if the wire already routed and removed is a wire interconnecting a movable terminal, freely placeable within a predetermined region, to another terminal, then the movable terminal is displaced within the predetermined region and the removed wire is re-routed such that the displaced movable terminal is interconnected to the other terminal. Accordingly, the movable terminal can be located at an appropriate position within the predetermined region in accordance with the situation of surrounding wires. As a result, routing results of a higher density can be obtained.
Inventors
- 👤 Noriko Shinomiya
- 👤 Masahiro Fukui
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:31
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
113 words
An automatic routing method for routing and designing an LSI, the method comprising the steps of: a) initial routing of a net; b) removing a wire already routed if a design rule error exists in the wire or a non-routable wire is caused as a result of the initial routing; and c) if the wire already routed and removed is a wire interconnecting a movable terminal, freely placeable within a predetermined region, to another terminal placed within a wiring region, displacing the movable terminal to a newly generated and previously unoccupied position within the predetermined region and re-routing the removed wire such that the displaced movable terminal is interconnected to the another terminal.
Claim 2
Dependent Claim
113 words
An automatic routing method for routing and designing an LSI, the method comprising the steps of: a) initial routing of a net; b) removing a wire already routed if a design rule error exists in the wire or a non-routable wire is caused as a result of the initial routing; and c) if the wire already routed and removed is a wire interconnecting a movable terminal, freely placeable within a predetermined region, to another terminal placed within a wiring region, displacing the movable terminal to a newly generated and previously unoccupied position within the predetermined region and re-routing the removed wire such that the displaced movable terminal is interconnected to the another terminal.
Claim 3
Dependent Claim
17 words
The method of claim 1 , wherein the movable terminal is a source/drain terminal of a MOSFET.
Claim 4
Dependent Claim
36 words
The method of claim 1 , wherein in the predetermined region where the movable terminal is placed, an area where the movable terminal is placed and the other areas of the region are all routable areas.
Claim 5
Dependent Claim
40 words
The method of claim 1 , wherein the step a) comprises the steps of: d) defining the predetermined region where the movable terminal is placeable; and e) determining an initial position of the movable terminal in the defined, predetermined region.
Claim 6
Dependent Claim
34 words
The method of claim 1 , wherein in the step b), the wire already routed and to be removed is extracted by regarding the number of the movable terminals as an index of evaluation.
Claim 7
Dependent Claim
26 words
The method of claim 1 , wherein the step a) is performed without taking into consideration a design rule error caused by a wire already routed.
Claim 8
Dependent Claim
25 words
The method of claim 1 , wherein the step a) is performed without allowing a design rule error to happen with a wire already routed.
Claim 9
Independent Claim
181 words
A method for searching for a wiring route during automatically routing and designing an LSI in accordance with a maze algorithm in which a wiring route cost is calculated by adding a cost every time a single grid is passed in a wiring region divided into a plurality of grids, the method comprising the steps of: a) inputting at least one of a height constraint and a lateral width constraint of the wiring region and hardwiring information; b) calculating a number of available grids for each column of grids, on which the height constraint of the wiring region is applied, or each row of grids, on which the lateral width constraint of the wiring region is applied, during routing based on the hardwiring information; and c) setting a passage cost for one of the columns of grids or one of the rows of grids, to which column or row the wiring route to be searched for proceeds, based on the number of available grids calculated for the column or the row, and adding the passage cost to the wiring route cost.
Claim 10
Independent Claim
181 words
A method for searching for a wiring route during automatically routing and designing an LSI in accordance with a maze algorithm in which a wiring route cost is calculated by adding a cost every time a single grid is passed in a wiring region divided into a plurality of grids, the method comprising the steps of: a) inputting at least one of a height constraint and a lateral width constraint of the wiring region and hardwiring information; b) calculating a number of available grids for each column of grids, on which the height constraint of the wiring region is applied, or each row of grids, on which the lateral width constraint of the wiring region is applied, during routing based on the hardwiring information; and c) setting a passage cost for one of the columns of grids or one of the rows of grids, to which column or row the wiring route to be searched for proceeds, based on the number of available grids calculated for the column or the row, and adding the passage cost to the wiring route cost.
Claim 11
Dependent Claim
61 words
The method of claim 8 , wherein in the step b), the number of available grids is calculated by subtracting a size of a wiring forbidden region in each said column or row of grids and a total size of wires already assigned to the column or row of grids from the height or lateral width constraint of the wiring region.
Claim 12
Dependent Claim
24 words
The method of claim 8 or 9 , further comprising the step of d) extracting a wiring route having a minimum wiring route cost.
Claim 13
Dependent Claim
41 words
The method of claim 8 or 9 , wherein in the step c), the passage cost is set based on not only the number of available grids but also a penalty for failing to satisfy the height or lateral width constraint.
Claim 14
Dependent Claim
63 words
The method of claim 11 , further comprising the steps of: d) repeatedly searching for the wiring route if the height or lateral width constraint of the wiring region has not been satisfied after all the routes have been searched; and e) changing the penalty for failing to satisfy the height or lateral width constraint every time the wiring route is repeatedly searched.
Claim 15
Dependent Claim
24 words
The method of claim 12 , wherein in the step e), the penalty is gradually changed from a smaller value to a larger value.
References Cited (Backward Citations)
US4615011A
Cited
US5224057A
Cited
US5315535A
Cited
US5729469A
Cited
US5461576A
Cited
US5852562A
Cited
US5790414A
Cited
US5889681A
Cited
US5943486A
Cited
US5867398A
Cited
US6067409A
Cited
US6014507A
Cited
US6011912A
Cited
US5930500A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-10 | 2005-06-11 | 2005-12-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-10 | 2009-06-11 | 2009-12-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-10 | 2013-06-11 | 2013-12-11 | $7700.00 | Window Closed / Lapsed |