Method and apparatus for generating multi-layer routes
First Claim
1. For a layout that has multiple layers, a method of generating a multi-layer topological path comprising:
- a) specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; and
b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, identifying a first region on the first layer for the second topological item;
identifying a second region on the second layer for the third topological item;
determining whether an intersection of the first and second regions is larger than a threshold area; and
if the intersection is larger than the threshold area, adding the potential via expansion to the specified set of path expansions.
2 Assignments
0 Petitions
Accused Products
Abstract
Some embodiments of the invention provide a method of generating a multi-layer topological path for a layout that has multiple layers. This method specifies a set of path expansions from a first topological item to a second topological item on a first layer of the layout. For a potential via expansion from the second topological item to a third topological item on a second layer of the layout, the method (1) identifies a first region on the first layer for the second topological item, (2) identifies a second region on the second layer the third topological item, (3) determines whether an intersection of the first and second regions is sufficiently large to contain a via, and (4) if the intersection is sufficiently large, adds the potential via expansion to the specified set of path expansions.
-
Citations
24 Claims
-
1. For a layout that has multiple layers, a method of generating a multi-layer topological path comprising:
-
a) specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout; and
b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, identifying a first region on the first layer for the second topological item;
identifying a second region on the second layer for the third topological item;
determining whether an intersection of the first and second regions is larger than a threshold area; and
if the intersection is larger than the threshold area, adding the potential via expansion to the specified set of path expansions. - View Dependent Claims (2, 3, 4, 5, 6, 7)
before specifying the set of path expansions, decomposing the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges;
wherein at least one of the second and third topological items represents an interior space of a face.
-
-
4. The method of claim 3, wherein the second topological item represents an interior space of a first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
-
5. The method of claim 3, wherein the layout is an IC layout.
-
6. The method of claim 5, wherein the IC layout includes a plurality of routable elements, wherein decomposing the layout comprises:
-
specifying a plurality of nodes along boundaries of the routable elements; and
defining edges between the nodes.
-
-
7. The method of claim 1, wherein each path expansion starts at a source topological item and ends with a destination topological item.
-
8. A computer program stored on a computer readable medium, wherein the computer program generates, for a layout that has multiple layers, a multi-layer topological path, the computer program comprising:
-
a) a first set of instructions for specifying a set of path expansions from a first topological item to a second topological item, wherein the second topological item is on a first layer of the layout;
b) for a potential via expansion from the second topological item to a third topological item on a second layer of the layout, a second set of instructions for identifying a first region on the first layer for the second topological item;
a third set of instructions for identifying a second region on the second layer for the third topological item;
a fourth set of instructions for determining whether an intersection of the first and second regions is larger than a threshold area; and
a fifth set of instructions for adding the potential via expansion to the specified set of path expansions, when the intersection is larger than the threshold area. - View Dependent Claims (9, 10, 11, 12, 13, 14)
a sixth set of instruction for decomposing, before specifying the set of path expansions, the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges;
wherein at least one of the second and third topological items represents an interior space of a face.
-
-
11. The computer program of claim 10, wherein the second topological item represents an interior space of first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
-
12. The computer program of claim 10, wherein the layout is an IC layout.
-
13. The computer program of claim 12, wherein the IC layout includes a plurality of routable elements, wherein the sixth set of instructions comprises:
-
a seventh set of instructions for specifying a plurality of nodes along boundaries of the routable elements; and
an eight set of instructions for defining edges between the nodes.
-
-
14. The computer program of claim 13, wherein each path expansion starts at a source topological item and ends with a destination topological item.
-
15. For an integrated circuit layout that has multiple layers, a method of generating a multi-layer topological path comprising:
-
a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout;
b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion;
c) determining whether an intersection of the first and second regions is larger than a threshold area; and
d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area. - View Dependent Claims (16, 17, 18, 19)
before specifying the set of path expansions, decomposing the layout into a plurality of faces, wherein each face has a set of edges and an interior space between the edges;
wherein at least one of the second and third topological items represents an interior space of a face.
-
-
18. The method of claim 17, wherein the second topological item represents an interior space of a first face on the first layer, and the third topological item represents an interior space of a second face on the second layer.
-
19. The method of claim 17, wherein the IC layout includes a plurality of routable elements, wherein decomposing the layout comprises:
-
specifying a plurality of nodes along boundaries of the routable elements; and
defining edges between the nodes.
-
-
20. A computer program stored on a computer readable medium, wherein the computer program generates, for an integrated circuit layout that has multiple layers, a multi-layer topological path, the computer program comprising sets of instructions for:
-
a) identifying a set of path expansions from a first topological item to a second topological item on a first layer of the layout;
b) identifying a first region on the first layer for the second topological item, and a second region on the second layer for a third topological item that is reachable from the second topological item through a via expansion;
c) determining whether an intersection of the first and second regions is larger than a threshold area; and
d) adding the potential via expansion to the specified set of path expansions when the intersection is larger than the threshold area. - View Dependent Claims (21, 22, 23, 24)
specifying a plurality of nodes along boundaries of the routable elements; and
defining edges between the nodes.
-
Specification