Method and apparatus for specifying a distance between an external state and a set of states in space

• US 7,051,298 B1
• Filed: 12/31/2002
• Issued: 05/23/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): Thompson, A. M.
• Assistant Examiner(s): ROSSOSHEK, YELENA
• Application Number:
  US10/334,665
• Time in Patent Office: 1,239 Days
• Field of Search: 716/4, 716/5, 716/7, 716/11, 716/12, 716/13, 716/2, 703/19, 370/389, 370/238
• US Class Current: 716/130
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments provide a method of computing the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon based on a model that allows penalizes measurements in certain directions more than other directions. Based on the projected vectors, the method then identifies the estimated distance.

Claims

1. For a multi-state space representing a region of a design layout, a method of computing an estimated distance between a first state and a set of states in the space, the method comprising:

a) defining a polygon that encloses the set of states;

b) projecting vectors in at least two different directions from the one or more vertices of the polygon, each direction having an associated scalar constant wherein at least two of the associated scalar constants have different values; and

c) identifying the estimated distance between said first state and said set of states using the projected vectors and the associated scalar constants.

2. The method of claim 1, wherein when the first state is a point, the estimated distance is a single value.

3. The method of claim 1, wherein when the first state is a line, identifying the estimated distance comprises using the projected vectors to identify a function that is defined over the line.

4. The method of claim 1, wherein when the first state is a surface, identifying the estimated distance comprises using the projected vectors to identify a function that is defined over the surface.

5. The method of claim 1, wherein said projecting vectors comprises only projecting vectors along a side of said first state such that said first state is positioned between said projecting vectors.

6. The method of claim 1, wherein the polygon is a bounding box.

7. The method of claim 6, wherein the design layout has horizontal and vertical axes and the bounding box has sides aligned with said horizontal and vertical axes of the design layout.

8. The method of claim 6, wherein the design layout has horizontal and vertical axes and the bounding box has sides that are not aligned with said horizontal and vertical axes of the design layout.

9. The method of claim 1, wherein defining the polygon comprises:

defining two other polygons that each enclose the set of states; and

defining the polygon as the intersection of the two other polygons.

10. For a multi-state space representing a region of a design layout, a method of computing an estimated distance between a first state and a set of states in the space, said method comprising:

a) defining a polygon that encloses the set of states;

b) based on a wiring model that penalizes certain wiring directions more than other wiring directions, projecting vectors in at least two different wiring directions from the one or more vertices of said polygon, each wiring direction having an associated scalar constant wherein a first wiring direction having a higher associated scalar constant than a second wiring direction is a penalized wiring direction; and

c) estimating the distance between said first state and said set of states using the projected vectors and the associated scalar constants, wherein said estimated distance accounts for penalties of certain wiring directions.

11. A computer readable medium storing a computer program for computing an estimated distance between a first state and a set of states in a multi-state space, said multi-state space representing a region of a design layout, said computer program comprising sets of instructions for:

a) defining a polygon that encloses said set of states;

b) projecting vectors in at least two different directions from the one or more vertices of said polygon, each direction having an associated scalar constant wherein at least two of the associated scalar constants have different values; and

c) estimating the distance between said first state and said set of states using the projected vectors and the associated scalar constants.

12. The computer readable medium of claim 11, wherein when said first state is a point, said estimated distance is a single value.

13. The computer readable medium of claim 11, wherein said set of instructions for estimating the distance comprises a set of instructions for using said projected vectors to identify a function that is defined over a line when said first state is said line.

14. The computer readable medium of claim 11, wherein said set of instructions for estimating the distance comprises a set of instructions for using said projected vectors to identify a function that is defined over a surface when said first state is said surface.

15. The computer readable medium of claim 11, wherein said set of instructions for projecting vectors comprises a set of instructions for only projecting vectors along a side of said first state such that said first state is positioned between said projected vectors.

16. The computer readable medium of claim 11, wherein said polygon is a bounding box.

17. The computer readable medium of claim 16, wherein the design layout has horizontal and vertical axes and said bounding box has sides aligned with said horizontal and vertical axes of said design layout.

18. The computer readable medium of claim 16, wherein the design layout has horizontal and vertical axes and said bounding box has sides that are not aligned with said horizontal and vertical axes of said design layout.

19. The computer readable medium of claim 11, wherein said set of instructions for defining said polygon comprises sets of instructions for:

defining two other polygons that each enclose said set of states; and

defining said polygon as the intersection of said two other polygons.