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

• US 6,978,432 B1
• Filed: 08/28/2002
• Issued: 12/20/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): Whitmore, Stacy A.
• Assistant Examiner(s): Dinh, Paul
• Application Number:
  US10/232,795
• Time in Patent Office: 1,210 Days
• Field of Search: 716/2, 716 5- 6, 716 10- 14
• 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 propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, which is a point. 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. If the second state is between two projected vectors that emanate from a vector-emanating point on the first state, the method then computes a cost at the second state that equals the sum of the cost of the first PLF at the vector-emanating point and the distance between the vector-emanating point and the second state in the design layout. On the other hand, if the second state is between two projected vectors that emanate from the different points on the first state, the method identifies the length of a first line that is parallel to the two projected vectors and that is between the second state and a termination point on a second line connecting the two points on the first state from which the two projected vectors emanate. The method then computes a cost at the second state that equals the sum of the identified length and the cost of the first PLF at the termination point.

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 point, wherein the PLF has a plurality of vertices, the method comprising:

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

b) if the second state is between two projected vectors that emanate from a same vector-emanating point on the first state, computing a cost at the second state that equals the sum of the value of the first PLF at the vector-emanating point and the distance between the vector-emanating point and the second state.

2. The method of claim 1 further comprising:

if the second state is between two projected vectors that emanate from two different points on the first state,

identifying the length of a first line between the second state and a termination point on a second line that connects the two different points on the first state, wherein the first line is parallel to the two projected vectors; and

computing a cost at the second state that equals the sum of the identified length and the value of the first PLF at the termination point.

3. The method of claim 2, wherein the multi-state space represents a design layout, wherein a specified 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 distance between the vector-emanating point and the second state in the design layout equals the length of the shortest path between the vector-emanating point and the second state along the specified set of interconnect lines.

5. The method of claim 4, wherein the first state is a surface.

6. The method of claim 4, wherein the first state is a line.

7. The method of claim 4, wherein the first state is a set of collinear points.

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

9. The method of claim 1, wherein the space is a triangulated graph that includes points, lines, and surfaces.

10. 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 point, wherein the PLF has a plurality of vertices, the method comprising:

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

b) if the second state is between two projected vectors that emanate from two different points on the first state,

identifying the length of a first line between the second state and a termination point on a second line that connects the two different points on the first state, wherein the first line is parallel to the two projected vectors; and

computing a cost at the second state that equals the sum of the identified length and the value of the first PLF at the termination point.

11. 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 point, wherein the PLF has a plurality of vertices, the computer program comprising instructions for:

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

b) if the second state is between two projected vectors that emanate from a same vector-emanating point on the first state, computing a cost at the second state that equals the sum of the value of the first PLF at the vector-emanating point and the distance between the vector-emanating point and the second state.

12. The computer readable medium of claim 11, wherein for the case where the second state is between two projected vectors that emanate from the different points on the first state, the computer program further comprises instructions for:

identifying the length of a first line between the second state and a termination point on a second line that connects the two points on the first state from which the two projected vectors emanate, wherein the first line is parallel to the two projected vectors;

computing a cost at the second state that equals the sum of the identified length and the value of the first PLF at the termination point.

13. The computer readable medium of claim 12, wherein the multi-state space represents a design layout, wherein a specified 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 distance between the vector-emanating point and the second state in the design layout equals the length of the shortest path between the vector-emanating point and the second state along the specified set of interconnect lines.

15. The computer readable medium of claim 14, wherein the first state is a surface.

16. The computer readable medium of claim 14, wherein the first state is a line.

17. The computer readable medium of claim 14, wherein the first state is a set of collinear points.

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

19. The computer readable medium of claim 11, wherein the space is a triangulated graph that includes points, lines, and surfaces.