US5187671A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automated interconnect routing system
Assignee: Microelectronics and Computer Technology Corp
•
Filing: 1990-08-24
•
Granted: 1993-02-16
•
Expires: 2010-08-24
Abstract
Abstract A method of manufacturing a multiple element circuit interconnect substrate is provided which provides an optimized routing plan. The routing plan is based upon a multi-dimensional binary data structure having nodes representing each terminal interconnect requirement which is preprocessed to order the required interconnects according to density.
Inventors
- 👤 Deborah D. Cobb
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 09:00
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
134 words
A method for manufacturing a routing plan for a multiple element electrical circuit interconnect substrate of the type used to interconnect a plurality of circuit element terminals comprising the steps of: (a) providing a net list specifying the circuit terminals to be interconnected by the interconnect substrates, said net list comprising a list of terminal connections, each with an associated net number; (b) generating an ordered FROM-TO list for routing according to connection density; (c) subdividing the area of the substrate for routing into a set of nested rectangular regions according to density; (d) providing an optimized routing plan for each subdivided area, proceeding from the area of highest density to lowest density; and (e) merging the optimized routing plans for each subdivided area to produce a routing plan for the entire interconnect substrate.
Claim 2
Independent Claim
134 words
A method for manufacturing a routing plan for a multiple element electrical circuit interconnect substrate of the type used to interconnect a plurality of circuit element terminals comprising the steps of: (a) providing a net list specifying the circuit terminals to be interconnected by the interconnect substrates, said net list comprising a list of terminal connections, each with an associated net number; (b) generating an ordered FROM-TO list for routing according to connection density; (c) subdividing the area of the substrate for routing into a set of nested rectangular regions according to density; (d) providing an optimized routing plan for each subdivided area, proceeding from the area of highest density to lowest density; and (e) merging the optimized routing plans for each subdivided area to produce a routing plan for the entire interconnect substrate.
Claim 3
Dependent Claim
83 words
The method of claim 1, wherein said step of ordering the FROM-TO list comprises: (a) representing each entry in the net list as a NODE in a multi-dimensional binary tree data structure; (b) searching the binary tree data structure from the lowest level up to locate terminals in the same net; (c) creating a FROM-TO connection data entry for terminals having the same net; and (d) ordering the FROM-TO list from the lowest node in the binary tree data structure to the highest.
Claim 4
Dependent Claim
49 words
The method of claim 1 wherein said step of subdividing the area of the substrate for routing comprises defining a minimal routing rectangle necessary to route connections between the data subtrees formed below the root node of the from terminal and the to terminal under consideration for from-to routing.
Claim 5
Dependent Claim
35 words
The method of claim 1, wherein said step of providing an optimized routing plan for each subdivided area comprises determining one or more minimum bend routes for each FROM-TO connection restricted to the sub-divided area.
Claim 6
Dependent Claim
24 words
The method of claim 4, further comprising selecting the shortest minimum bend route for each FROM-TO connection from among the determined minimum bend routes.
Claim 7
Dependent Claim
59 words
The method of claim 1, wherein said step of merging the routing plans for sub-divided areas comprises: (a) for each node in a first data sub-tree search a second sub-tree for a node in the same net; and (b) if a common net between nodes is found, create a FROM-TO connection between nodes and mark the nodes as merged.
References Cited (Backward Citations)
UST944001I4
Cited
US4593363A
Cited
US4890238A
Cited
US4908772A
Cited
US4815003A
Cited
US4922432A
Cited
US4967367A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-02-16 | 1996-08-17 | 1997-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-02-16 | 2000-08-17 | 2001-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-02-16 | 2004-08-17 | 2005-02-16 | $7700.00 | Window Closed / Lapsed |