Method and apparatus for propagating a piecewise linear function to a line

• US 6,915,499 B1
• Filed: 08/28/2002
• Issued: 07/05/2005
• Est. Priority Date: 06/04/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Limited (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): Thompson, A. M.
• Assistant Examiner(s): Dimyan, Magid Y.
• Application Number:
  US10/231,369
• Time in Patent Office: 1,042 Days
• Field of Search: 716 1- 21, 333/21.A, 333/126, 333/129, 333/135, 333/137, 343/756, 705/7, 705/400, 345/419, 717/101
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method for propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, which is a line. 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. For instance, in some embodiments, the space is a graph that includes points, lines, and surfaces. The method projects vectors from points on the first state that are locations of inflection points in the first PLF. At any intersection of the line and one of the vectors, the method computes a cost. The method also computes a cost at any endpoint of the line that does not intersect one of the vectors. Based on the computed costs, the method then specifies a second PLF that is defined over the second state.

Claims

1. For a multi-state space, a method of propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, wherein the second state is a line, wherein the PLF has a plurality of inflection points, the method comprising:

a) projecting vectors from points on the first state that are locations of inflection points in the first PLF;

b) at each intersection of the line and one of the vectors, computing a cost;

c) at each endpoint of the line that does not intersect one of the vectors, computing a cost; and

d) based on the computed costs, specifying a second PLF that is defined over the second state, wherein the second PLF contains information regarding each computed cost.

2. The method of claim 1, wherein the multi-state space represents a design layout, wherein a set of interconnect line directions are available for connecting the first and second states, wherein projecting vectors comprises projecting vectors in at least some of the specified interconnect line directions.

3. The method of claim 2, wherein the first state is a first point, wherein computing the cost at an intersection of the line and one of the projected vectors comprises:

a) computing the distance between a point on the line that the projected vector intersects and the first point in the direction of the projected vector that intersects the line at the point; and

b) summing the computed distance with the cost of the first PLF at the first point.

4. The method of claim 3, wherein computing the cost at an endpoint of the line that does not intersect one of the projected vectors comprises:

identifying the length of the shortest path, according to the specified set of interconnect lines, between the endpoint and the first point; and

summing the length with the cost of the first PLF at the first point.

5. The method of claim 2, wherein computing the cost at an intersection of the line and a particular projected vector comprises:

computing the distance between the intersected point on the line and a first vector-emanating point on the first state from which the projected vector emanates, wherein the distance is along the direction of the particular projected vector; and

summing the computed distance with the cost of the first PLF at the first vector-emanating point on the first state.

6. The method of claim 5, wherein computing the cost at an endpoint of the line that does not intersect one of the projected vectors comprises:

if the endpoint is between two projected vectors that emanate from a second vector-emanating point on the first state, identifying the length of the shortest path, according to the specified set of interconnect lines, between the endpoint and the second vector-emanating point; and

summing the length with the cost of the first PLF at the second vector-emanating point.

7. The method of claim 5, wherein when the endpoint is between two projected vectors that emanate from different points of the first state, and a first line connects the two different points, and the second state is a second line, computing the cost at the endpoint, which does not intersect one of the projected vectors, comprises:

identifying the length of a third line between the endpoint and a termination point on the first line, wherein the third line is parallel to the two projected vectors; and

specifying the cost as the sum of the identified length and the cost of the first PLF at the termination point.

8. The method of claim 1, wherein the first state is a line.

9. The method of claim 1, wherein the first state is a surface.

10. The method of claim 1, wherein first state is a set of collinear points.

11. The method of claim 1, wherein the first state is a set of co-planar points.

12. A computer readable medium that stores a computer program that, in a multi-state space, propagates a first piecewise linear function (PLF), which is defined over a first state, to a second state, wherein the second state is a line, wherein the PLF has a plurality of inflection points, the computer program comprising instructions for:

a) projecting vectors from points on the first state that are locations of inflection points in the first PLF;

b) at each intersection of the line and one of the vectors, computing a cost;

c) at each endpoint of the line that does not intersect one of the vectors, computing a cost; and

d) based on the computed costs, specifying a second PLF that is defined over the second state, wherein the second PLF contains information regarding each computed cost.

13. The computer readable medium of claim 12, wherein the multi-state space represents a design layout, wherein a set of interconnect line directions are available for connecting the first and second states, wherein the instructions for projecting vectors comprises instructions for projecting vectors in at least some of the specified interconnect line directions.

14. The computer readable medium of claim 13, wherein the first state is a first point, wherein the instructions for computing the cost at an intersection of the line and one of the projected vectors comprise instructions for:

a) computing the distance between a point on the line that the projected vector intersects and the first point in the direction of the projected vector that intersects the line at the point; and

b) summing the computed distance with the cost of the first PLF at the first point.

15. The computer readable medium of claim 14, wherein the instructions for computing the cost at an endpoint of the line that does not intersect one of the projected vectors comprise instructions for:

identifying the length of the shortest path, according to the specified set of interconnect lines, between the endpoint and the first point; and

summing the length with the cost of the first PLF at the first point.

16. The computer readable medium of claim 13, wherein the instructions for computing the cost at an intersection of the line and a particular projected vector comprise instructions for:

computing the distance between the intersected point on the line and a first vector-emanating point on the first state from which the projected vector emanates, wherein the distance is along the direction of the particular projected vector; and

summing the computed distance with the cost of the first PLF at the first vector-emanating point on the first state.

17. The computer readable medium of claim 16, wherein for an endpoint that is between two projected vectors that emanate from a second vector-emanating point on the first state, the instructions for computing the cost at an endpoint of the line that does not intersect one of the projected vectors comprise instructions for:

identifying the length of the shortest path, according to the specified set of interconnect lines, between the endpoint and the second vector-emanating point; and

summing the length with the cost of the first PLF at the second vector-emanating point.

18. The computer readable medium of claim 16, wherein for an endpoint that is between two projected vectors that emanate from different points of the first state, wherein a first line connects the two different points, and the second state is a second line, the instructions for computing the cost at the endpoint, which does not intersect one of the projected vectors, comprise instructions for:

identifying the length of a third line between the endpoint and a termination point on the first line, wherein the third line is parallel to the two projected vectors; and

specifying the cost as the sum of the identified length and the cost of the first PLF at the termination point.

19. The computer readable medium of claim 12, wherein the first state is a line.

20. The computer readable medium of claim 12, wherein the first state is a surface.

21. The computer readable medium of claim 12, wherein first state is a set of collinear points.

22. The computer readable medium of claim 12, wherein the first state is a set of co-planar points.

23. For a multi-state space, a method of propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, wherein the second state is a line, wherein the PLF has a plurality of inflection points, the method comprising:

a) projecting vectors from points on the first state that are locations of inflection points in the first PLF;

b) at each intersection of the line and one of the vectors, computing a cost;

c) at each endpoint of the line that does not intersect one of the vectors, computing a cost; and

d) based on the computed costs, specifying a second PLF that is defined over the second state, wherein the second PLF is a function that reflects the cost of a path expansion from the first state to the second state.