Method and apparatus for determining viability of path expansions

• US 6,931,608 B1
• Filed: 11/05/2002
• Issued: 08/16/2005
• Est. Priority Date: 06/04/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): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US10/288,033
• Time in Patent Office: 1,015 Days
• Field of Search: 716/4, 716/10, 716/13, 716/14, 703/2, 703/16
• US Class Current: 716/130
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

For a path search that identifies a path between source and target states in a space, some embodiments of the invention provide a method for determining viability of an expansion of a path from a first state to a second dimensional state. The method computes a first cost function that expresses the cost of the path to reach the second state. The first cost function is defined over the second state. The method then determines whether the first cost function expresses a better cost over any portion of the second state than a second cost function that expresses the best cost of paths that have reached the second state during the path search. The expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function.

Claims

1. For a path search that identifies a path between source and target states in a space, a method of determining viability of an expansion of a path from a first state to a second state, wherein the second state is a dimensional state, the method comprising:

a) computing a first cost function that expresses a cost of the path to reach the second state, wherein the first cost function is defined over the second state;

b) determining whether the first cost function expresses a better cost over any portion of the second state than a second cost function, wherein the second cost function expresses the best cost of paths that have reached the second state during the path search;

wherein the expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function, wherein said portion of said second state is less than said second state.

2. The method of claim 1, wherein said best cost is a lowest cost value.

3. The method of claim 1, wherein the cost functions are piecewise linear functions.

4. The method of claim 3, wherein the cost functions are convex piecewise linear functions.

5. The method of claim 3, wherein the piecewise linear functions have a plurality of knots, wherein determining whether the first cost function expresses a better cost comprises comparing the first and second cost functions at their knots.

6. The method of claim 5, wherein the second state is a line, and comparing the first and second cost functions at their knots includes performing a line sweep across the second state, wherein the line sweep examines values of the cost functions at each knot.

7. The method of claim 5, wherein the second state is a surface, and comparing the first and second cost functions at their knots includes performing a plane sweep across the second state, wherein the plane sweep examines values of the cost functions at each knot.

8. The method of claim 1, wherein the space is a graph, and the states in the graph include lines and surfaces.

9. A computer readable medium that stores a computer program having executable code, the computer program for a method of determining viability of an expansion of a path from a first state to a second state in a space, wherein the second state is a dimensional state, the computer program comprises sets of instructions for:

a) computing a first cost function that expresses a cost of the path to reach the second state, wherein the first cost function is defined over the second state;

b) determining whether the first cost function expresses a better cost over any portion of the second state than a second cost function, wherein the second cost function expresses the best cost of paths that have reached the second state during the path search;

wherein the expansion is a viable one if the first cost function expresses a better cost over at least a portion of the second state than the second cost function, wherein said portion of said second state is less than said second state.

10. The computer readable medium of claim 9, wherein said best cost is a lowest cost value.

11. The computer readable medium of claim 9, wherein the cost functions are piecewise linear functions.

12. The computer readable medium of claim 11, wherein said piecewise linear functions have a plurality of knots, wherein determining whether said first cost function expresses a better cost comprises comparing said first and second cost functions at their knots.

13. The computer readable medium of claim 12, wherein said second state is a line, and comparing said first and second cost functions at their knots includes performing a line sweep across said second state, wherein the line sweep examines values of said cost functions at each knot.

14. The computer readable medium of claim 12, wherein said second state is a surface, and comparing said first and second cost functions at their knots includes performing a plane sweep across said second state, wherein said plane sweep examines values of said cost functions at each knot.

15. The computer readable medium of claim 9, wherein said space is a graph, and said states in said graph include lines and surfaces.