Probabilistic congestion prediction with partial blockages

1. A method of estimating routing congestion between pins in a net of an integrated circuit design using a computer system, comprising:

establishing one or more potential routes between the pins which pass through one or more buckets in the net, each bucket having a set of wiring tracks;

assigning a probabilistic usage to each bucket based on any partial blockage of the wiring tracks in each bucket, wherein said assigning includes creating a temporary usage map of the net buckets with an initial value of zero usage in every temporary usage map bucket, storing usage values in corresponding buckets of the temporary usage map, and deriving a final usage map from the temporary usage map;

computing routing congestion for each bucket using its probabilistic usage; and

storing the routing congestion for each bucket in said computer system.

2. The method of claim 1 wherein the net is a two-pin net that is a part of a larger multi-pin net, and further comprising constructing a tree to bridge the two-pin net to another pin of the multi-pin net.

3. The method of claim 1 wherein the routing congestion for each bucket is computed as a ratio of the bucket usage to bucket capacity.

4. The method of claim 1 wherein the routes are L-shaped having at least one bend in a bucket, and the probabilistic usage is proportional to a scale factor α which is a ratio of a minimum number of available wiring tracks for a given route to a sum of minimum numbers of available wiring tracks for all possible routes.

5. The method of claim 1 wherein the routes are Z-shaped having at least two bends in two respective buckets, and the probabilistic usage is equal to a ratio of a minimum capacity of a given route to a sum of minimum capacities of all routes having an associated orientation with the given route.

6. The method of claim 5 wherein the minimum capacity F(n) of the given route n is

F ( n )=min{ F ( u 1 )· F ( d n )/ F R ( d 1 ), . . . , F ( u n )· F ( d n )/ F R ( d n ), F ( d n ), F ( e n )· F ( d n )/ F L ( d n ), . . . , F ( e Q )· F ( d Q )/ F L ( d Q )},

where Q is the number of potential routes, d is one of a plurality of central span portions of the potential routes, u is one of a first plurality of edge portions of the potential routes that lie on a first side of the central span portions, e is one of a second plurality of edge portions of the potential routes that lie on a second side of the central span portions, F(u n ) is the capacity associated with edge u n , F(d n ) is the capacity associated with edge d n , F(e n ) is the capacity associated with edge e n , F L (d n ) is the total capacities of all central spans d to the left of span d n having an associated orientation with the given route, and F R (d n ) is the total capacities of all central spans d to the right of span d n having the associated orientation with the given route.

7. A computer system comprising:

one or more processors which process program instructions;

a memory device connected to said processing means; and

program instructions residing in said memory device for estimating routing congestion between pins in a net of an integrated circuit design by establishing one or more potential routes between the pins which pass through one or more buckets in the net, each bucket having a set of wiring tracks, assigning a probabilistic usage to each bucket based on any partial blockage of the wiring tracks in each bucket wherein said assigning includes creating a temporary usage map of the net buckets with an initial value of zero usage in every temporary usage map bucket, storing usage values in corresponding buckets of the temporary usage map, and deriving a final usage map from the temporary usage map, and computing routing congestion for each bucket using its probabilistic usage.

8. The computer system of claim 7 wherein the net is a two-pin net that is a part of a larger multi-pin net, and said program instructions further construct a tree to bridge the two-pin net to another pin of the multi-pin net.

9. The computer system of claim 7 wherein the routing congestion for each bucket is computed as a ratio of the bucket usage to bucket capacity.

10. The computer system of claim 7 wherein the routes are L-shaped having at least one bend in a bucket, and the probabilistic usage is proportional to a scale factor α which is a ratio of a minimum number of available wiring tracks for a given route to a sum of minimum numbers of available wiring tracks for all possible routes.

11. The computer system of claim 7 wherein the routes are Z-shaped having at least two bends in two respective buckets, and the probabilistic usage is equal to a ratio of a minimum capacity of a given route to a sum of minimum capacities of all routes having an associated orientation with the given route.

12. The computer system of claim 11 wherein the minimum capacity F(n) of the given route n is

F ( n )=min{ F ( u 1 )· F ( d n )/ F R ( d 1 ), . . . , F ( u n )· F ( d n )/ F R ( d n ), F ( d n ), F ( e n )· F ( d n )/ F L ( d n ), . . . , F ( e Q )· F ( d Q )/ F L ( d Q )},

where Q is the number of potential routes, d is one of a plurality of central span portions of the potential routes, u is one of a first plurality of edge portions of the potential routes that lie on a first side of the central span portions, e is one of a second plurality of edge portions of the potential routes that lie on a second side of the central span portions, F(u n ) is the capacity associated with edge u n , F(d n ) is the capacity associated with edge d n , F(e n ) is the capacity associated with edge e n , F L (d n ) is the total capacities of all central spans d to the left of span d n having an associated orientation with the given route, and F R (d n ) is the total capacities of all central spans d to the right of span d n having the associated orientation with the given route.

13. A computer program product comprising:

a computer-readable medium; and

program instructions residing in said medium for estimating routing congestion between pins in a net of an integrated circuit design by establishing one or more potential routes between the pins which pass through one or more buckets in the net, each bucket having a set of wiring tracks, assigning a probabilistic usage to each bucket based on any partial blockage of the wiring tracks in each bucket wherein said assigning includes creating a temporary usage map of the net buckets with an initial value of zero usage in every temporary usage map bucket, storing usage values in corresponding buckets of the temporary usage map, and deriving a final usage map from the temporary usage map, and computing routing congestion for each bucket using its probabilistic usage.

14. The computer program product of claim 13 wherein the net is a two-pin net that is a part of a larger multi-pin net, and said program instructions further construct a tree to bridge the two-pin net to another pin of the multi-pin net.

15. The computer program product of claim 13 wherein the routing congestion for each bucket is computed as a ratio of the bucket usage to bucket capacity.

16. The computer program product of claim 13 wherein the routes are L-shaped having at least one bend in a bucket, and the probabilistic usage is proportional to a scale factor α which is a ratio of a minimum number of available wiring tracks for a given route to a sum of minimum numbers of available wiring tracks for all possible routes.

17. The computer program product of claim 13 wherein the routes are Z-shaped having at least two bends in two respective buckets, and the probabilistic usage is equal to a ratio of a minimum capacity of a given route to a sum of minimum capacities of all routes having an associated orientation with the given route.

18. The computer program product of claim 17 wherein the minimum capacity F(n) of the given route n is

F ( n )=min{ F ( u 1 )· F ( d n )/ F R ( d 1 ), . . . , F ( u n )· F ( d n )/ F R ( d n ), F ( d n ), F ( e n )· F ( d n )/ F L ( d n ), . . . , F ( e Q )· F ( d Q )/ F L ( d Q )},

where Q is the number of potential routes, d is one of a plurality of central span portions of the potential routes, u is one of a first plurality of edge portions of the potential routes that lie on a first side of the central span portions, e is one of a second plurality of edge portions of the potential routes that lie on a second side of the central span portions, F(u n ) is the capacity associated with edge u n , F(d n ) is the capacity associated with edge d n , F(e n ) is the capacity associated with edge e n , F L (d n ) is the total capacities of all central spans d to the left of span d n having an associated orientation with the given route, and F R (d n ) is the total capacities of all central spans d to the right of span d n having the associated orientation with the given route.