Interconnection routing system

• US 6,353,918 B1
• Filed: 08/05/1999
• Issued: 03/05/2002
• Est. Priority Date: 03/15/1996
• Status: Expired due to Fees

• Current Assignee: Arizona Board of Regents (University of Arizona)
• Original Assignee: Arizona Board of Regents (University of Arizona)
• Inventors: Li, Donghui, Carothers, Jo Dale
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Speight, Jibreel
• Application Number:
  US09/142,793
• Time in Patent Office: 943 Days
• Field of Search: 716/1, 716/19, 716/6, 716/13, 716/8, 716/12
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

The routing system implements a global approach (400) that proposes several candidate routes for various nets (402) and analyzes compatibility with respect to other routes and constraints (406), such as electrical or thermal considerations (404).

Claims

1. A computer-implemented method of routing a plurality of nets between the terminals of a plurality of circuits, comprising the steps of:

generating a plurality of candidate routes for each of at least a first net and a second net;

analyzing each of said plurality of candidate routes corresponding to said first net for compatibility with each of said plurality of candidate routes corresponding to said second net;

discarding a first analyzed candidate route, wherein said discarded route is incompatible with at least one of the candidate routes corresponding to said second net;

wherein a second analyzed route is compatible with at least one of the candidate routes corresponding to a second net, further comprising the step of routing a corresponding net based on said compatible second analyzed candidate route; and

inserting Steiner points into said routed corresponding net.

2. The method of claim 1, wherein said plurality of candidate routes is associated with a first layer pair of a substrate, further comprising the steps of:

determining whether each of the plurality of nets has an associated route which is compatible with all of a plurality of other routes associated with all of the other nets; and

adding a second layer pair to said substrate if each of the plurality of nets does not have said associated route which is compatible with said set or routes associated with all of the other nets.

3. The method of claim 2, further comprising as the step of redistributing at least one routed net from said first layer pair to said second layer pair to reduce congestion on said first layer pair.

4. The method of claim 3, wherein said step of redistributing comprises the steps of:

generating at least one candidate route corresponding to said routed corresponding net on said second layer;

analyzing said routed corresponding net and said at least one candidate route for congestion on said first and second layer pairs, respectively; and

moving said routed corresponding net to said second layer pair if said at least one candidate route is less congested than said routed corresponding net.

5. The method of claim 1, further comprising the step of removing jogs from said routed corresponding net.

6. The method of claim 1, further comprising the step of re-routing said routed corresponding net to reduce congestion.

7. The method of claim 1, wherein the plurality of nets includes at least one multi-terminal net having n number of terminals, wherein n is greater than two, further comprising the step of decomposing the at least one multi-terminal net into (n−

1) number of two-terminal nets.

8. The method of claim 1, wherein said step of analyzing the candidate routes for compatibility includes analyzing the candidate routes for compatibility based on electrical interaction between the candidate routes.

9. The method of claim 1, wherein said step of generating said plurality of candidate routes includes generating only candidate routes having a first number of vias or fewer.

10. The method of claim 9, further comprising the step of, following the step of discarding said first analyzed candidate route, generating a second plurality of candidate routes for at least one of said first net and said second net, wherein the candidate routes have more than said first number of vias.

11. The method of claim 9, further comprising the step of discarding said first analyzed candidate route, generating a second plurality of candidate routes for at least one of said first net and said second net, wherein at least one of the candidate routes extends beyond the boundaries of a bounding box associated with the at least one net.

12. A computer-implemented method of routing a set of nets between a plurality of circuits having a plurality of terminals and mounted on a multi-layer substrate, comprising the steps of:

selecting a first set of compatible routes from a first set of candidate routes associated with a first layer pair, wherein each route of said first set of compatible routes has a first number of vias or less;

selecting a second set of compatible routes from a second set of candidate routes associated with said first layer pair, wherein each route of said second set of compatible routes has a second number of vias or less, said second number being greater than said first number, and said first and second sets of compatible routes are associated with different sets of nets, and said first and second sets of compatible routes are compatible with each other;

determining whether said first and second sets of compatible routes include a route corresponding to each of the nets;

following the step of determining, adding a second layer pair to the multi-layer substrate if said first and second sets of compatible routes do not include a route corresponding to each of the nets;

repeating said steps of selecting said first set of compatible routes and said second set of compatible routes in conjunction with said second layer pair instead of said first layer pair;

wherein the plurality of nets includes at least one multi-terminal net having n number of terminals, wherein n is greater than two, further comprising the step of decomposing the at least one multi-terminal net into (n−

1) number of two-terminal nets; and

inserting Steiner points into at least one route corresponding to a net.

13. The method of claim 12, further comprising the step of removing jogs from at least one route corresponding to a net.

14. The method of claim 12, further comprising the step of redistributing at least one route corresponding to a net from said second layer pair to reduce congestion on said first layer pair.

15. The method of claim 14, wherein said step of redistributing comprises the steps of:

generating at least one candidate route corresponding to said route corresponding to said net on said second layer;

analyzing said route corresponding to said net and said at least one candidate route for congestion on said first and second layer pairs, respectively; and

moving said route corresponding to said net to said second layer pair if said at least one candidate route is less congested than said routed corresponding net.

16. The method of claim 12, further comprising the step of re-routing said routed corresponding net to reduce congestion.