Interconnection routing system
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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).
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
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. - View Dependent Claims (13, 14, 15, 16)
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.
Specification