Hierarchical routing method and apparatus that use diagonal routes
First Claim
1. A method of hierarchically routing a net within a particular region of an integrated circuit (“
- IC”
) layout, the net having a plurality of pins, the method comprising;
a) partitioning the particular IC region into a first set of sub-regions;
b) identifying a first route that connects a group of first-set sub-regions containing the net'"'"'s pins, wherein the route has an edge that is at least partially diagonal;
c) partitioning the first-set sub-regions into a second set of smaller sub-regions;
d) propagating the first route into the second-set sub-regions; and
e) using the propagated first route to identify hierarchically a second route that connects a group of second-set sub-regions containing the net'"'"'s pins.
2 Assignments
0 Petitions
Accused Products
Abstract
Some embodiments provide a hierarchical routing method that uses diagonal routes. This method routes a net within a particular region of an integrated circuit (“IC”) layout. This net includes several pins in the region. The method initially partitions the particular IC region into a first set of sub-regions. It then identifies a first route that connects a group of first-set sub-regions that contain the net'"'"'s pins. The identified first route has an edge that is at least partially diagonal. The method next partitions the first-set sub-regions into a second set of smaller sub-regions. It then propagates the first route into the second-set sub-regions.
-
Citations
29 Claims
-
1. A method of hierarchically routing a net within a particular region of an integrated circuit (“
- IC”
) layout, the net having a plurality of pins, the method comprising;a) partitioning the particular IC region into a first set of sub-regions; b) identifying a first route that connects a group of first-set sub-regions containing the net'"'"'s pins, wherein the route has an edge that is at least partially diagonal; c) partitioning the first-set sub-regions into a second set of smaller sub-regions; d) propagating the first route into the second-set sub-regions; and e) using the propagated first route to identify hierarchically a second route that connects a group of second-set sub-regions containing the net'"'"'s pins. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
- IC”
-
20. A computer readable medium comprising a computer program having executable code for hierarchically routing a set of nets within a region of an integrated circuit (“
- IC”
) layout, wherein each net includes a set of pins in the region, the computer program comprising;a first set of instructions for partitioning the IC region into a first set of sub-regions, wherein a first set of paths exists between the first set of sub-regions, wherein some of the first set 4 paths are diagonal; a second set of instructions for identifying, for each particular net, a first route that connects a group of first-set sub-regions containing the particular net'"'"'s pins, wherein each particular first route is defined in terms of the paths from the first path set that the first route traverses, wherein at least one of the first routes traverses at least one of the diagonal paths of the first path set; a third set of instructions for partitioning the first-set of sub-regions into a second set of sub-regions, wherein a second set of paths exists between the second set of sub-regions, wherein some of the second set paths are diagonal; and a fourth set of instructions for identifying, for each particular net, a second route that connects a group of second-set sub-regions containing the pins of the particular net, wherein at least one of the second routes traverses at least one of the diagonal paths. - View Dependent Claims (21, 22, 23, 24)
- IC”
-
25. A computer readable medium comprising a computer program having executable code for hierarchically routing a set of nets within a region of an integrated circuit (“
- IC”
) layout, wherein each net includes a set of pins in the region, the computer program comprising;a first set of instructions for partitioning the IC region into a first set of sub-regions, wherein a first set of inter-region edges exists between the first set of sub-regions, wherein some of the first set inter-region edges are diagonal; a second set of instructions for identifying, for each particular net, a first route that connects a group of the first set of sub-regions containing the particular net'"'"'s pins, wherein each particular first route is defined in terms of the inter-region edges from a first-edge set that the particular first route intersects, wherein at least one of the first routes intersects at least one of the diagonal edges of the first-edge set; a third set of instructions for partitioning the first set of sub-regions into a second set of sub-regions, wherein a second set of inter-region edges exists between the second set of sub-regions, wherein some of the second set inter-region edges are diagonal; and a fourth set of instructions for identifying for each particular net, a second route that connects a group of the second-set sub-regions containing the pins of the particular net, wherein at least one of the second routes intersects at least one of the diagonal inter-region edges. - View Dependent Claims (26, 27, 28, 29)
- IC”
Specification