Metal layer assignment
First Claim
Patent Images
1. A method for assigning routing layers to connection segments in integrated circuit design, said method comprising:
- an obtaining step of obtaining a routing description of a net that includes plural connection segments and plural vertices, each of the plural vertices being a vertex;
a generating step of generating a tree-shaped routing graph from the routing description by selecting one of the plural vertices to be a root and forming edges corresponding to the connection segments such that each vertex other than the root has only one edge leading to it from a next higher hierarchical level;
a determining step of determining penalty values for plural different potential routing layer assignment combinations by traversing the tree-shaped routing graph in a bottom-up fashion, wherein each potential routing layer assignment combination represents one possible combination of assignments of at least a subset of the edges to specific routing layers; and
an assigning step of assigning routing layers to the plural connection segments based on the penalty values determined in said determining step.
11 Assignments
0 Petitions
Accused Products
Abstract
Routing layers are assigned to connection segments in integrated circuit design. A routing description that includes connection segments and a vertex where at least two of the connection segments connect to each other is obtained. A penalty is determined for the vertex based on a potential layer assignment combination for the connection segments that connect at the vertex, and routing layers are assigned to the connection segments based on the determined penalty.
358 Citations
32 Claims
-
1. A method for assigning routing layers to connection segments in integrated circuit design, said method comprising:
-
an obtaining step of obtaining a routing description of a net that includes plural connection segments and plural vertices, each of the plural vertices being a vertex;
a generating step of generating a tree-shaped routing graph from the routing description by selecting one of the plural vertices to be a root and forming edges corresponding to the connection segments such that each vertex other than the root has only one edge leading to it from a next higher hierarchical level;
a determining step of determining penalty values for plural different potential routing layer assignment combinations by traversing the tree-shaped routing graph in a bottom-up fashion, wherein each potential routing layer assignment combination represents one possible combination of assignments of at least a subset of the edges to specific routing layers; and
an assigning step of assigning routing layers to the plural connection segments based on the penalty values determined in said determining step. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
identifying situations when at least two of the plural different potential routing layer assignment combinations result in a same routing layer assignment for the one edge leading to a particular vertex from the next higher hierarchical level; and
determining whether said at least two of the plural different potential routing layer assignment combinations result in different penalty values for said particular vertex and, if so, eliminating an inferior one of said at least two of the plural different potential routing layer assignment combinations.
-
-
10. A method according to claim 1, wherein the penalty values are determined at the vertices of the routing graph, and wherein the penalty value for each vertex is defined with respect to a particular potential routing layer assignment combination as:
- (i) a first component that is based on routing layer assignments for all edges connecting at said each vertex;
plus (ii) the penalty values, still assuming said particular potential routing layer assignment combination, for all vertices that are immediate descendants of said each vertex.
- (i) a first component that is based on routing layer assignments for all edges connecting at said each vertex;
-
11. A method according to claim 10, wherein, for each vertex, a penalty value is determined for each potential routing layer assignment combination remaining for the vertices below said each vertex in the tree-shaped routing graph.
-
12. A method according to claim 11, wherein inferior potential routing layer assignment combinations, as determined by the penalty values, are eliminated when processing each vertex.
-
13. A method according to claim 1, further comprising a step of enumerating the edges so that each edge has a higher number than any of its descendants, and wherein in said determining step the edges are processed in order of the enumeration.
-
14. A method according to claim 13, wherein the edges are processed using dynamic programming to identify a layer assignment combination for all of the edges having a minimum combined penalty.
-
15. A method according to claim 1, further comprising an identifying step of identifying allowable routing layers for each edge.
-
16. A method according to claim 15, wherein the allowable routing layers for a particular edge include only those routing layers for which both:
- (1) there is space for the particular edge; and
(2) a relative occupancy of edges corresponding to the particular connection segment on lower routing layers having a same direction as the particular edge is not less than the relative occupancy of corresponding edges on all routing layers having the same direction as the particular edge.
- (1) there is space for the particular edge; and
-
17. A method according to claim 1, wherein said determining step is performed by utilizing dynamic programming.
-
18. A method according to claim 1, wherein said obtaining step, said determining step said generating step and said assigning step are performed for each net to be implemented in the integrated circuit design.
-
19. An apparatus for assigning routing layers to connection segments in integrated circuit design, said apparatus comprising:
-
obtaining means for obtaining a routing description of a net that includes plural connection segments and plural vertices, each of the plural vertices being a vertex;
generating means for generating a tree-shaped routing graph from the routing description by selecting one of the plural vertices to be a root and forming edges corresponding to the connection segments such that each vertex other than the root has only one edge leading to it from a next higher hierarchical level;
determining means for determining penalty values for plural different potential routing layer assignment combinations by traversing the tree-shaped routing graph in a bottom-up fashion, wherein each potential routing layer assignment combination represents one possible combination of assignments of at least a subset of the edges to specific routing layers; and
assigning means for assigning routing layers to the plural connection segments based on the penalty values determined by said determining means. - View Dependent Claims (20, 21, 22, 23, 24, 25)
identifying situations when at least two of the plural different potential routing layer assignment combinations result in a same routing layer assignment for the one edge leading to a particular vertex from the next higher hierarchical level; and
determining whether said at least two of the plural different potential routing layer assignment combinations result in different penalty values for said particular vertex and, if so, eliminating an inferior one of said at least two of the plural different potential routing layer assignment combinations.
-
-
26. A computer-readable medium storing computer-executable process steps for assigning routing layers to connection segments in integrated circuit design, said process steps comprising:
-
an obtaining step to obtain a routing description of a net that includes plural connection segments and plural vertices, each of the plural vertices being a vertex;
a generating step to generate a tree-shaped routing graph from the routing description by selecting one of the plural vertices to be a root and forming edges corresponding to the connection segments such that each vertex other than the root has only one edge leading to it from a next higher hierarchical level;
a determining step to determine penalty values for plural different potential routing layer assignment combinations by traversing the tree-shaped routing graph in a bottom-up fashion, wherein each potential routing layer assignment combination represents one possible combination of assignments of at least a subset of the edges to specific routing layers; and
an assigning step to assign routing layers to the plural connection segments based on the penalty values determined in said determining step. - View Dependent Claims (27, 28, 29, 30, 31, 32)
identify situations when at least two of the plural different potential routing layer assignment combinations result in a same routing layer assignment for the one edge leading to a particular vertex from the next higher hierarchical level; and
determine whether said at least two of the plural different potential routing layer assignment combinations result in different penalty values for said particular vertex and, if so, eliminate an inferior one of said at least two of the plural different potential routing layer assignment combinations.
-
Specification