Method and apparatus for propagating cost functions

• US 7,013,448 B1
• Filed: 10/31/2002
• Issued: 03/14/2006
• 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): WHITMORE, STACY
• Application Number:
  US10/285,758
• Time in Patent Office: 1,230 Days
• Field of Search: 716 12- 14
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method of expanding a path in a space with dimensional states. 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. The method identifies a first expansion for the path from a start state to a first destination state. It then specifies a first cost function that expresses the cost of the first expansion. The first cost function is defined over the destination state. The method also identifies a second expansion for the path from a first portion of the first destination state to a second destination state. From a portion of the first cost function that is defined over the first portion of the first destination state, the method computes a second cost function that specifies the cost of the second expansion.

Claims

1. A method of expanding a path in a space, said space having a plurality of states, the method comprising:

a) identifying a first expansion for the path from a start state to a first destination state, said first destination state having at least one dimension;

b) specifying a first cost function that specifies the cost of the first expansion, wherein the first cost function is defined over the first destination state;

c) identifying a second expansion for the path from a first portion of the first destination state to a second destination state, wherein said first portion is less than the entirety of said first destination state; and

d) from a particular portion of the first cost function that is defined over the first portion of the first destination state, computing a second cost function that specifies the cost of the second expansion, wherein said particular portion of the first cost function does not represent the entirety of said first cost function.

2. The method of claim 1 further comprising:

identifying portions of the first destination state where the value of the first cost function is less than the value of a filter function that is defined over the first destination state and that expresses the lowest cost of expansions that were previously identified to the first destination state,

wherein the first portion is one of the identified portions.

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

4. The method of claim 3, wherein identifying the portions comprises filtering the first cost function by the filter function.

5. The method of claim 2, wherein identifying the portions includes identifying a plurality of portions, wherein the method further comprises:

specifying path-search identifiers for each identified portion;

storing the specified path-search identifiers other than the path-search identifier for the first portion.

6. The method of claim 5 further comprising:

after computing the second cost function, retrieving a path-search identifier for a second portion from the storage structure;

identifying a third expansion for the path from the second portion of the first destination state to the second destination state;

from a portion of the first cost function that is defined over the second portion of the first destination state, computing a third cost function that specifies the cost of the third expansion.

7. The method of claim 5 further comprising:

after computing the second cost function, retrieving a path-search identifier for a second portion from the storage structure;

identifying a third expansion for the path from the second portion of the first destination state to a third destination state;

from a portion of the first cost function that is defined over the second portion of the first destination state, computing a third cost function that specifies the cost of the third expansion.

8. The method of claim 1, wherein the space further includes a zero-dimensional state.

9. The method of claim 1, wherein at least one of the start, first destination, and second destination states is a line.

10. The method of claim 1, wherein at least one of the start, first destination, and second destination states is a surface.

11. A computer readable medium that stores a computer program having executable code, the computer program for expanding a path in a space, said space having a plurality of states, the computer program comprising sets of instructions for:

a) identifying a first expansion for the path from a start state to a first destination state, said first destination state having at least one dimension;

b) specifying a first cost function that specifies the cost of the first expansion, wherein the first cost function is defined over the first destination state;

c) identifying a second expansion for the path from a first portion of the first destination state to a second destination state, wherein said first portion is less than the entirely of said first destination state; and

d) from a particular portion of the first cost function that is defined over the first portion of the first destination state, computing a second cost function that specifies the cost of the second expansion, wherein said particular portion of the first cost function does not represent the entirety of said first cost function.

12. The computer readable medium of claim 11,

wherein the computer program further comprises a set of instructions for identifying portions of the first destination state where the value of the first cost function is less than the value of a filter function that is defined over the first destination state and that expresses the lowest cost of expansions that were previously identified to the first destination state,

wherein the first portion is one of the identified portions.

13. The computer readable medium of claim 12, wherein the cost functions are piecewise linear functions.

14. The computer readable medium of claim 13, wherein the set of instructions for identifying the portions comprises a set of instructions for filtering the first cost function by the filter function.

15. The computer readable medium of claim 12, wherein the set of instructions for identifying the portions includes a set of instructions for identifying a plurality of portions, wherein the computer program further comprises sets of instructions for:

specifying path-search identifiers for each identified portion;

storing the specified path-search identifiers other than the path-search identifier for the first portion.

16. The computer readable medium of claim 15, wherein the computer program further comprises sets of instructions for:

retrieving, after computing the second cost function, a path-search identifier for a second portion from the storage structure;

identifying a third expansion for the path from the second portion of the first destination state to the second destination state;

from a portion of the first cost function that is defined over the second portion of the first destination state, computing a third cost function that specifies the cost of the third expansion.

17. The computer readable medium of claim 15, wherein the computer program further comprises sets of instructions for:

retrieving, after computing the second cost function, a path-search identifier for a second portion from the storage structure;

identifying a third expansion for the path from the second portion of the first destination state to a third destination state;

from a portion of the first cost function that is defined over the second portion of the first destination state, computing a third cost function that specifies the cost of the third expansion.

18. The computer readable medium of claim 11, wherein the space further includes a zero-dimensional state.

19. The computer readable medium of claim 11, wherein at least one of the start, first destination, and second destination states is a line.

20. The computer readable medium of claim 11, wherein at least one of the start, first destination, and second destination states is a surface.