Method and apparatus for hierarchical global routing descend
First Claim
1. A method for optimizing the routing of nets in an integrated circuit device, said method comprising the following steps:
- a. dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction;
b. dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction;
c. forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross;
d. globally routing nets as a function of said first routing graph;
e. further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction;
f. forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
g. for a net globally routed in step d, forming a first local net in a first fragment of said second routing graph; and
h. rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
11 Assignments
0 Petitions
Accused Products
Abstract
Net routing is optimized in an integrated circuit device by dividing an integrated circuit design with a first group of substantially parallel lines in a first direction and with a group of substantially parallel lines in a second direction, with the second direction being substantially perpendicular to the first direction. A first routing graph is formed with vertices corresponding to locations where lines in the first direction and lines in the second direction cross, and nets are globally routed as a function of the first routing graph. The integrated circuit design is further subdivided with a second group of substantially parallel lines in the first direction, and a second routing graph is formed with vertices corresponding to locations where lines in the first and second groups of substantially parallel lines in the first direction cross lines in the group of substantially parallel lines in the second direction. For a net globally routed using the first routing graph, a first local net is formed in a first fragment of the second routing graph, and the first local net is rerouted within the first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of the edge penalty values.
174 Citations
19 Claims
-
1. A method for optimizing the routing of nets in an integrated circuit device, said method comprising the following steps:
-
a. dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction;
b. dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction;
c. forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross;
d. globally routing nets as a function of said first routing graph;
e. further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction;
f. forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
g. for a net globally routed in step d, forming a first local net in a first fragment of said second routing graph; and
h. rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
i. further dividing said integrated circuit design with a third plurality of substantially parallel lines in said first direction;
j. forming a third routing graph with vertices corresponding to locations where lines in said first, second and third pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
k. for a second net previously routed, forming a second local net in a second fragment of said third routing graph; and
l. rerouting said second local net within said second fragment.
-
-
6. The method of claim 5 wherein said first routing graph, second routing graph and third routing graph each cover the same area and the respective number of vertices of said routing graphs are in the approximate ratio of 1:
- 2;
4.
- 2;
-
7. The method of claim 1 wherein said local net comprises at least one pin from the net globally routed in step d and an edge that was previously in the net'"'"'s routing.
-
8. The method of claim 1 wherein step h comprises calculating penalty function values corresponding to all possible reroutings of said first local net within said first fragment.
-
9. The method of claim 8 wherein the first local net is rerouted so as to have the minimum total of edge penalty values corresponding to edges in the rerouting.
-
10. An apparatus for optimizing the routing of nets in an integrated circuit device, said apparatus comprising:
-
a. means for dividing an integrated circuit design with a first plurality of substantially parallel lines in a first direction;
b. means for dividing said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction;
c. means for forming a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross;
d. means for globally routing nets as a function of said first routing graph;
e. means for further dividing said integrated circuit design with a second plurality of substantially parallel lines in said first direction;
f. means for forming a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
g. means for a net globally routed by said globally routing means, forming a first local net in a first fragment of said second routing graph; and
h. means for rerouting said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
i. means for further dividing said integrated circuit design with a third plurality of substantially parallel lines in said first direction;
j. means for forming a third routing graph with vertices corresponding to locations where lines in said first, second and third pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
k. means for a second net previously routed, forming a second local net in a second fragment of said third routing graph; and
l. means for rerouting said second local net within said second fragment.
-
-
15. The apparatus of claim 14 wherein said first routing graph, second routing graph and third routing graph each cover the same area and the respective number of vertices of said routing graphs are in the approximate ratio of 1:
- 2;
4.
- 2;
-
16. The apparatus of claim 10 wherein said local net comprises at least one pin from the net globally routed by said means d and an edge that was previously in the net'"'"'s routing.
-
17. The apparatus of claim 10 wherein rerouting performed by said means h comprises calculating penalty function values corresponding to all possible reroutings of said first local net within said first fragment.
-
18. The apparatus of claim 17 wherein the first local net is rerouted so as to have the minimum total of edge penalty values corresponding to edges in the rerouting.
-
19. A computer storage medium for optimizing the routing of nets in an integrated circuit device, comprising:
-
a computer storage medium readable by a computer; and
means recorded on said storage medium for directing the computer to;
a. divide an integrated circuit design with a first plurality of substantially parallel lines in a first direction;
b. divide said integrated circuit design with a plurality of substantially parallel lines in a second direction, wherein said second direction is substantially perpendicular to said first direction;
c. form a first routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross;
d. globally route nets as a function of said first routing graph;
e. further divide said integrated circuit design with a second plurality of substantially parallel lines in said first direction;
f. form a second routing graph with vertices corresponding to locations where lines in said first and second pluralities of substantially parallel lines in said first direction cross lines in said plurality of substantially parallel lines in said second direction;
g. form, for a net globally routed according to the instruction in element d, a first local net in a first fragment of said second routing graph; and
h. reroute said first local net within said first fragment by computing edge penalty values for edges in the first fragment and rerouting the first local net as a function of said edge penalty values.
-
Specification