Method and apparatus for computing cost of a path expansion to a surface

• US 7,246,338 B1
• Filed: 12/31/2002
• Issued: 07/17/2007
• 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): Garbowski; Leigh M.
• Application Number:
  US10/335,179
• Time in Patent Office: 1,659 Days
• Field of Search: None
• US Class Current: 716/130
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method for costing an expansion to a two-dimensional state in a path search that searches for a path between two sets of states in a space. The method identifies a cost function that is defined over the two-dimensional state. The method computes a second cost function that is defined over the two-dimensional state. It also computes a third cost function that is defined over the two-dimensional state. It then adds the second and third cost functions to obtain the first cost function.

Claims

1. In a path search that searches for a path between two sets of states in a space, a method for defining routes in a design layout of a circuit by computing a first cost function that is defined over a two-dimensional state, the method comprising:

a) computing a second cost function that is defined over the two-dimensional state;

b) computing a third cost function that is defined over the two-dimensional state; and

c) adding the second and third cost functions to obtain the first cost function.

2. The method of claim 1, wherein adding the functions comprises performing a line sweep across the two-dimensional state.

3. The method of claim 2, wherein the second and third cost functions are piecewise linear functions (‘

PLF'"'"'s”

), wherein each PLF has a plurality of knots, wherein the line sweep comprises examining each unique knot location in the second and third cost functions.

4. The method of claim 3, wherein the line sweep is performed in a particular direction that has a first end and a second end, wherein each cost function has a plurality of edges, wherein each edge is between an edge-opening knot and an edge-closing knot, the method comprising:

a) selecting a first knot in either the second or third function that is closest to the first end;

b) identifying at least one edge that has the first knot as an edge-opening knot;

c) selecting a second knot in either the second or third function that is the next closest knot to the first end;

d) when the second knot is an edge-closing knot of a particular edge in the second knot'"'"'s function that does not intersect any identified edge of the other function, adding the particular edge to the definition of the first cost function;

e) when the second knot is an edge-closing knot of a particular edge in the second knot'"'"'s function that does intersect one or more identified edges of the other function, specifying a set of knots to account for the intersection and adding a set of edges that are defined based on the specified set of knots to the definition of the first cost function.

5. The method of claim 3, wherein the line sweep is performed in a particular direction that has a first end and a second end, wherein each cost function has a plurality of edges, wherein each edge is between an edge-opening knot and an edge-closing knot, the method comprising:

a) selecting a first knot in either the second or third function that is closest to the first end;

b) identifying each edge that has the first knot as an edge-opening knot;

c) selecting a second knot in either the second or third function that is the next closest knot to the first end;

d) if the second knot is an edge-closing knot of any edge in the second knot'"'"'s function,

for each particular edge closed by the second knot, determining whether the particular edge intersects any previously identified edge of the other function;

if the particular edge does not intersect any edge, adding the particular edge to the definition of the first cost function;

if the particular edge intersects one or more previously identified edges of the other function, specifying a set of knots to account for the intersections and adding a set of edges that are defined based on the specified set of knots to the definition of the first cost function.

6. The method of claim 5 further comprising:

identifying each edge that has the second knot as its edge-opening knot.

7. The method of claim 6 further comprising:

successively examining each knot in the second and third functions in the order of the knot'"'"'s proximity to the first end;

wherein the examination of each particular knot comprises;

determining whether the particular knot is an edge-closing knot of any edge in the particular knot'"'"'s function,

if the particular knot is the edge-closing knot of any edge in the particular knot'"'"'s function,

for each particular edge closed by the particular knot, determining whether the particular edge intersects any previously identified edge of the other function;

if the particular edge does not intersect any edge, adding the particular edge to the definition of the first cost function;

if the particular edge intersects a set of previously identified edges of the other function, specifying a set of knots to account for the intersections and adding a set of edges that are defined based on the set of knots to the definition of the first cost function;

identifying each edge that has the particular knot as its edge-opening knot.

8. The method of claim 1, wherein the first cost function is an estimated cost of a path from the first set of states through the two-dimensional state to the second set of states.

9. The method of claim 8, wherein the second cost function is a cost of a path from the first set of states to the two-dimensional state, and the third cost function is an estimated cost of a path from the two-dimensional state to the second set of states.

10. The method of claim 9, wherein the space represents a region of the design layout of the circuit, and the path identified by the path search is a potential segment of a route between routable elements in the region.

11. A computer readable medium storing a computer program for defining routes in a design layout of a circuit by computing a first cost function that is defined over a two-dimensional state during a path search that searches for a path between two sets of states in a space, the computer program comprising sets of instructions for:

a) computing a second cost function that is defined over the two-dimensional state;

b) computing a third cost function that is defined over the two-dimensional state; and

c) adding the second and third cost functions to obtain the first cost function.

12. The computer readable medium of claim 11, wherein the set of instructions for adding the functions comprises a set of instructions for performing a line sweep across the two-dimensional state.

13. The computer readable medium of claim 12, wherein the second and third cost

functions are piecewise linear functions (“

PLF'"'"'s”

), wherein each PLF has a plurality of knots, wherein the line sweep comprises examining each unique knot location in the second and third cost functions.

14. The computer readable medium of claim 13, wherein the line sweep is performed in a particular direction that has a first end and a second end, wherein each cost function has a plurality of edges, wherein each edge is between an edge-opening knot and an edge-closing knot, the computer program further comprising sets of instructions for:

a) selecting a first knot in either the second or third function that is closest to the first end;

b) identifying at least one edge that has the first knot as an edge-opening knot;

c) selecting a second knot in either the second or third function that is the next closest knot to the first end;

d) when the second knot is an edge-closing knot of a particular edge in the second knot'"'"'s function that does not intersect any identified edge of the other function, adding the particular edge to the definition of the first cost function;

e) when the second knot is an edge-closing knot of a particular edge in the second knot'"'"'s function that does intersect one or more identified edges of the other function, specifying a set of knots to account for the intersection and adding a set of edges that are defined based on the specified set of knots to the definition of the first cost function.

15. The computer readable medium of claim 13, wherein the line sweep is performed in a particular direction that has a first end and a second end, wherein each cost function has a plurality of edges, wherein each edge is between an edge-opening knot and an edge-closing knot, the computer program further comprising sets of instructions for:

a) selecting a first knot in either the second or third function that is closest to the first end;

b) identifying each edge that has the first knot as an edge-opening knot;

c) selecting a second knot in either the second or third function that is the next closest knot to the first end;

d) if the second knot is an edge-closing knot of any edge in the second knot'"'"'s function,

for each particular edge closed by the second knot, determining whether the particular edge intersects any previously identified edge of the other function;

if the particular edge does not intersect any edge, adding the particular edge to the definition of the first cost function;

if the particular edge intersects one or more previously identified edges of the other function, specifying a set of knots to account for the intersections and adding a set of edges that are defined based on the specified set of knots to the definition of the first cost function.

16. The computer readable medium of claim 15, wherein the computer program further comprises a set of instructions for identifying each edge that has the second knot as its edge-opening knot.

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

successively examining each knot in the second and third functions in the order of the knot'"'"'s proximity to the first end;

wherein the examination of each particular knot comprises;

determining whether the particular knot is an edge-closing knot of any edge in the particular knot'"'"'s function,

if the particular knot is the edge-closing knot of any edge in the particular knot'"'"'s function,

for each particular edge closed by the particular knot, determining whether the particular edge intersects any previously identified edge of the other function;

if the particular edge does not intersect any edge, adding the particular edge to the definition of the first cost function;

if the particular edge intersects a set of previously identified edges of the other function, specifying a set of knots to account for the intersections and adding a set of edges that are defined based on the set of knots to the definition of the first cost function;

identifying each edge that has the particular knot as its edge-opening knot.

18. The computer readable medium of claim 11, wherein the first cost function is an estimated cost of a path from the first set of states through the two-dimensional state to the second set of states.

19. The computer readable medium of claim 18, wherein the second cost function is a cost of a path from the first set of states to the two-dimensional state, and the third cost function is an estimated cost of a path from the two-dimensional state to the second set of states.

20. The computer readable medium of claim 19, wherein the space represents a region of the design layout of the circuit, and the path identified by the path search is a potential segment of a route between routable elements in the region.