Automated interconnect routing system

• US 5,187,671 A
• Filed: 08/24/1990
• Issued: 02/16/1993
• Est. Priority Date: 08/24/1990
• Status: Expired due to Fees

• Current Assignee: Microelectronics and Computer Technology Corporation
• Original Assignee: Microelectronics and Computer Technology Corporation
• Inventors: Cobb, Deborah D.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/572,744
• Time in Patent Office: 907 Days
• Field of Search: 364/491, 364/490, 364/489, 364/488
• US Class Current: 716/130
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.