Method and apparatus for identifying a path between source and target states in a space with more than two dimensions

• US 7,069,531 B1
• Filed: 08/09/2002
• Issued: 06/27/2006
• Est. Priority Date: 07/15/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US10/215,923
• Time in Patent Office: 1,418 Days
• Field of Search: 716/12, 716/10, 716/13, 716/5
• US Class Current: 716/126
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method for identifying a path between a set of source states and a set of target states in a space with more than two dimensions. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. At least some of the states are non-zero dimensional states. For instance, in some embodiments, the space is a graph that includes points, lines, and surfaces. The method specifies at least one path that starts from one state. It then iteratively specifies new paths by expanding previously specified paths to other states in the space until identifying a path that connects the source and target states. At least one of the expansions of a previously specified path includes an expansion in more than two dimensions of the space.

Claims

1. A method of identifying a path between a set of source states and a set of target states in a space with more than two dimensions, the method comprising:

specifying at least one path that starts from one state;

after specifying the at least one path, iteratively specifying new paths by expanding previously specified paths to other states in the space until a path is identified that connects a source and target state, wherein expanding previously specified paths includes expanding paths in more than two dimensions of the space, wherein at least some of the states are non-zero dimensional states; and

for at least one specified path that includes an expansion to a particular non-zero dimensional state, computing a particular cost function that is defined over the particular non-zero dimensional state, wherein the particular cost function comprises at least two different values associated with at least two different locations on the particular non-zero dimensional state.

2. The method of claim 1, wherein expanding paths in more than two dimensions comprises:

expanding paths in one or more planes parallel with two particular dimensions of the space; and

expanding paths in a direction perpendicular to the two particular dimensions of the space.

3. The method of claim 2, wherein the space has multiple layers, wherein each layer is a plane that is parallel to the two particular dimensions of the space, wherein an expansion that is in a direction perpendicular to the two particular dimensions of the space is an expansion to a state in the space that belongs to two different layers of the space.

4. The method of claim 3, wherein the space is a graph, and the states in the graph include points, lines, and surfaces.

5. The method of claim 4, wherein two-dimensional surfaces are the states that belong to more than one layer in the graph.

6. The method of claim 5, wherein each surface represents the location of a via between two different layers in the graph.

7. The method of claim 4 further comprising:

for each specified path that results from expanding a previously specified path to another state in the graph, propagating a cost function that expresses the cost of the previously specified path to the other state.

8. The method of claim 4 further comprising:

for each specified path that results from expanding a previously specified path to another state in the graph, computing a cost function that expresses the cost of expanding the previously specified path to the other state.

9. The method of claim 8, wherein the cost function of a path that reaches a particular state is defined over the particular state.

10. The method of claim 8, wherein the state that each particular path reaches is the particular path'"'"'s destination state, wherein iteratively specifying new paths comprises at each iteration:

selecting a previously specified path that has a best cost-function value; and

only if (i) the selected path still is a best path for at least a portion of the selected path'"'"'s destination state and (ii) the selected path'"'"'s cost function over the portion still provides a best cost of all the previously-specified paths, then specifying a new set of paths by identifying expansions of the selected path to other destination states in the graph.

11. The method of claim 10 further comprising:

after identifying and computing the cost of each specified path, storing an identifier for the expansion in a storage structure, wherein the identifiers are stored in the storage structure in a sorted order based on the best cost-function value of the corresponding paths of the identifiers,

wherein selecting a previously identified path that has the best cost-function value comprises selecting from the storage structure the identifier that is first in the sorted order.

12. The method of claim 11, wherein the best cost-function value is the lowest cost-function value.

13. The method of claim 10 further comprising:

to determine whether a selected path is still the best path to at least a portion of the destination state of the path, determining whether the cost function for the selected path specifies as good a cost for any portion of the selected path'"'"'s destination state as a cost function that expresses the best cost of all paths that have reached the destination state.

14. The method of claim 10, wherein, at each iteration, identifying expansions of the selected path to other destination states comprises:

identifying a set of potential expansions about the selected path'"'"'s destination state, wherein each potential expansion specifies a potential destination state for expanding the selected path from the selected path'"'"'s destination state;

for each particular potential expansion to a potential destination state,

determining whether a potential path that is obtained by extending the selected path to the potential destination state is the best path to at least a portion of the potential destination state;

if the potential path provides the best expansion to at least a portion of the potential destination state, specifying the potential path as a new path.

15. The method of claim 14, wherein determining whether a potential path is the best path to at least a portion of a potential destination state comprises:

computing a cost function that expresses a cost of the selected path to reach the potential destination state; and

determining whether the cost function specifies a best cost for any portion of the potential destination state.

16. The method of claim 15, wherein the best cost for any portion of the potential destination state is a cost that is as good as a cost produced by a cost function that expresses the best cost of all paths that have reached the potential destination state.

17. The method of claim 16, wherein specifying at least one path that starts from one state comprises specifying a plurality of paths that start from a plurality of states.

18. The method of claim 1, wherein specifying at least one path that starts from one state comprises specifying a plurality of paths that start from one state.

19. A method of identifying a path between a set of source states and a set of target states in a space with more than two dimensions, the method comprising:

specifying at least one path that starts from one state;

after specifying the at least one path, iteratively specifying new paths by expanding previously specified paths to other states in the space until a path is identified that connects a source and target state, wherein expanding previously specified paths includes expanding paths in more than two dimensions of the space, wherein at least some of the states are non-zero dimensional states; and

for at least one specified path that includes an expansion to a particular non-zero dimensional state, computing a particular cost function that is defined over the particular non-zero dimensional state, wherein the particular cost function is a piecewise linear function.

20. The method of claim 19, wherein the particular cost function is a convex piecewise linear function.

21. A computer readable medium storing a computer program for identifying a path between a set of source states and a set of target states in a space with more than two dimensions, the computer program comprising instructions for:

specifying at least one path that starts from one state;

after specifying the at least one path, iteratively specifying new paths by expanding previously specified paths to other states in the space until a path is identified that connects a source and target state, wherein the instructions for expanding previously specified paths includes instructions for expanding paths in more than two dimensions of the space, wherein at least some of the states are non-zero dimensional states; and

for at least one specified path that includes an expansion to a particular non-zero dimensional state, computing a particular cost function that is defined over the particular non-zero dimensional state, wherein the particular cost function comprises at least two different values associated with at least two different locations on the particular non-zero dimensional state.

22. The computer readable medium of claim 21, wherein the instructions for expanding paths in more than two dimensions comprises instructions for:

expanding paths in one or more planes parallel with two particular dimensions of the space; and

expanding paths in a direction perpendicular to the two particular dimensions of the space.

23. The computer readable medium of claim 22, wherein the space has multiple layers, wherein each layer is a plane that is parallel to the two particular dimensions of the space, wherein an expansion that is in a direction perpendicular to the two particular dimensions of the space is an expansion to a state in the space that belongs to two different layers of the space.

24. The computer readable medium of claim 23, wherein the space is a graph, and the states in the graph include points, lines, and surfaces.

25. The computer readable medium of claim 24, wherein two-dimensional surfaces are the states that belong to more than one layer in the graph.

26. The computer readable medium of claim 25, wherein each surface represents the location of a via between two different layers in the graph.

27. A computer readable medium storing a computer program for identifying a path between a set of source states and a set of target states in a space with more than two dimensions, the computer program comprising instructions for:

specifying at least one path that starts from one state;

after specifying the at least one path, iteratively specifying new paths by expanding previously specified paths to other states in the space until a path is identified that connects a source and target state, wherein the instructions for expanding previously specified paths includes instructions for expanding paths in more than two dimensions of the space, wherein at least some of the states are non-zero dimensional states; and

for at least one specified path that includes an expansion to a particular non-zero dimensional state, computing a particular cost function that is defined over the particular non-zero dimensional state, wherein the particular cost function is a piecewise linear function.

28. The computer readable medium of claim 27, wherein the particular cost function is a convex piecewise linear function.