Probabilistic routing method and apparatus
First Claim
1. A method of routing a plurality of nets in a region of an integrated circuit (“
- IC”
) layout, each net having a set of pins in the region, the method comprising;
a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins; and
c) using the identified edge-intersect probabilities to identify routes for the nets.
2 Assignments
0 Petitions
Accused Products
Abstract
Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular net and each particular edge, identifies an edge-intersect probability that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, and (2) uses the identified edge-intersect probabilities to identify routes for the nets. A potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins.
In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method (1) for each particular net and each particular path, identifies a path-use probability that specifies the probability that a set of potential routes for the particular net will use the particular path, and (2) uses the identified path-use probabilities to identify routes for the nets.
-
Citations
26 Claims
-
1. A method of routing a plurality of nets in a region of an integrated circuit (“
- IC”
) layout, each net having a set of pins in the region, the method comprising;a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins; and
c) using the identified edge-intersect probabilities to identify routes for the nets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
- IC”
-
13. A method of routing a plurality of nets in a region of an integrated circuit (“
- IC”
) layout, each net having a set of pins in the region, the method comprising;a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins; and
c) using the identified path-use probabilities to identify routes for the nets. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
- IC”
-
22. A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“
- IC”
) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for;a) partitioning the region into several sub-regions, wherein a plurality of edges exist between said sub-regions, b) for each particular net, identifying an edge-intersect probability for each particular edge that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins; and
c) using the identified edge-intersect probabilities to identify routes for the nets. - View Dependent Claims (23)
- IC”
-
24. A computer readable medium that stores a computer program for routing a plurality of nets in a region of an integrated circuit (“
- IC”
) layout, each net having a set of pins in the region, the computer program comprising sets of instructions for;a) partitioning the region into several sub-regions, wherein a plurality of paths exist between said sub-regions, b) for each particular net, identifying a path-use probability for each particular path that specifies the probability that a set of potential routes for the particular net will use the particular path, wherein a potential route for a particular net traverses the set of sub-regions that contain the particular net'"'"'s set of pins; and
c) using the identified path-use probabilities to identify routes for the nets. - View Dependent Claims (25, 26)
- IC”
Specification