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

• US 7,000,209 B1
• Filed: 08/28/2002
• Issued: 02/14/2006
• 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): Smith, Matthew
• Assistant Examiner(s): LEVIN, NAUM B
• Application Number:
  US10/233,312
• Time in Patent Office: 1,266 Days
• Field of Search: 716/2, 716 4- 6, 716 12- 16, 703/2
• US Class Current: 703/2
• 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 surface. 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 each intersection of the boundary of the surface and one of the vectors, the method computes a cost. Based on the computed costs, the method specifying a second PLF that is defined over the second state.

Claims

1. For a multi-state space comprising plurality of states, a method of propagating a first piecewise linear function (PLF), which represents costs associated with a first state, to represent costs associated with a second state, wherein the second state is a surface, wherein the first PLF has plurality of inflection points, the method comprising:

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

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

c) based on the computed costs, specifying a second PLF that represent costs associated with the second state.

2. The method of claim 1, wherein the surface has a number of vertices along its boundary, the method further comprising:

computing a cost at any boundary vertex of the surface that does not intersect one of the vectors; and

using at least one of the costs computed at a boundary vertex of the surface to specify further the second PLF.

3. The method of claim 2, 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.

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

computing the distance between a second point on the surface boundary that the projected vector intersects and the first point in the direction of the projected vector that intersects the second point;

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

5. The method of claim 4, wherein computing the cost at a surface boundary vertex that does not intersect one of the projected vectors comprises:

identifying the distance between the vertex and the first point according to the specified set of interconnect lines;

summing the distance and the cost of the first PLF at the first point.

6. The method of claim 3, wherein computing the cost an intersection at the boundary of the surface and a particular projected vector comprises:

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

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

7. The method of claim 6, wherein computing the cost at a surface boundary vertex that does not intersect one of the projected vectors comprises:

if the vertex 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 vertex and the second vector-emanating point;

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

8. The method of claim 6, 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, computing the cost at a surface boundary vertex that does not intersect one of the projected vector comprises:

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

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

9. The method of claim 3, the first state is a line.

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

11. A computer readable medium that stores a computer program that, in a multi-state space comprising plurality of states, propagates a first piecewise linear function (PLF), which represents costs associated with a first state, to represent costs associated with a second state, wherein the second state is a surface, wherein the first PLF has plurality of inflection points, the computer program comprising set of instructions for:

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

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

c) based on the computed costs, specifying a second PLF that represent costs associated with the second state.

12. The computer readable medium of claim 11, wherein the surface has a number of vertices along its boundary, the computer program further comprises set of instructions for:

computing a cost at any boundary vertex of the surface that does not intersect one of the vectors; and

using at least one of the costs computed at a boundary vertex of the surface to specify further the second PLF.

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 set of instructions for projecting vectors comprise a set of 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 set of instructions for computing the cost at an intersection at the boundary of the surface and one of the projected vectors comprises instructions for:

computing the distance between a second point on the surface boundary that the projected vector intersects and the first point in the direction of the projected vector that intersects the second point;

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 set of instructions for computing the cost at a surface boundary vertex that does not intersect one of the projected vectors comprises instructions for:

identifying the distance between the vertex and the first point according to the specified set of interconnect lines;

summing the distance and the cost of the first PLF at the first point.

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

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

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

17. The computer readable medium of claim 16, wherein for the case where the vertex is between two projected vectors that emanate from a second vector emanating point on the first state, the set of instructions for computing the cost at a surface boundary vertex that does not intersect one of the projected vectors comprises instructions for:

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

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 the case where 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, the set of instructions for computing the cost at a surface boundary vertex that does not intersect one of the projected vector comprises instructions for:

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

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 13, the first state is a line.

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