US6178539B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for determining critical area for circuit layouts using voronoi diagrams
Assignee: GlobalFoundries Inc
•
Filing: 1998-09-17
•
Granted: 2001-01-23
•
Expires: 2018-09-17
Abstract
Abstract A method for computing critical area for shorts of a layout, in accordance with the present invention, includes the steps of computing a Voronoi diagram for the layout, computing a second order Voronoi diagram to arrive at a partitioning of the layout into regions, computing critical area within each region and summing the critical areas to arrive at a total critical area for shorts in the layout. A system is also provided for calculating the critical area.
Inventors
- 👤 Evanthia Papadopoulou
- 👤 Der-Tsai Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 12:38
CPC Classifications
H; H10; H10P; H10P74/00; H10P74/23; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
61 words
A method for computing critical area for shorts of a layout, comprising the steps of: computing a Voronoi diagram for the layout; computing a second order Voronoi diagram to arrive at a partitioning of the layout into regions; computing critical area within each region; and summing the critical areas to arrive at a total critical area for shorts in the layout.
Claim 2
Independent Claim
61 words
A method for computing critical area for shorts of a layout, comprising the steps of: computing a Voronoi diagram for the layout; computing a second order Voronoi diagram to arrive at a partitioning of the layout into regions; computing critical area within each region; and summing the critical areas to arrive at a total critical area for shorts in the layout.
Claim 3
Dependent Claim
23 words
The method as recited in claim 1 , further comprising the step of decomposing each region into shapes for calculating the critical areas.
Claim 4
Dependent Claim
18 words
The method as recited in claim 2 , wherein the shapes are associated with second order Voronoi edges.
Claim 5
Dependent Claim
77 words
The method as recited in claim 1 , wherein the step of computing critical area includes the step of computing the critical area according to the following equation: A c = ∫ 0 ∞ A ( r ) D ( r ) r , where A c is the critical area, A(r) is the area of the critical region for defects of radius r and D(r) is a defect density function.
Claim 6
Dependent Claim
36 words
The method as recited in claim 4 , wherein the defect density function includes the defect size distribution D(r)=r 0 2 /r 3 where r denotes spot defect radius and r 0 denotes a constant size.
Claim 7
Dependent Claim
59 words
The method as recited in claim 1 , wherein the second order Voronoi diagram includes Voronoi edges associated with shapes of the layout and the method further comprises the steps of classifying the Voronoi edges to identify between areas of the regions that contribute to the critical area and areas of the regions that subtract from the critical area.
Claim 8
Dependent Claim
16 words
The method as recited in claim 6 , wherein the shapes include locations for circuit components.
Claim 9
Dependent Claim
24 words
The method as recited in claim 1 , wherein the Voronoi diagram and the second order Voronoi diagram include an L ∞ distance metric.
Claim 10
Dependent Claim
29 words
The method as recited in claim 1 , wherein the step of computing the Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 11
Dependent Claim
31 words
The method as recited in claim 1 , wherein the step of computing the second order Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 12
Dependent Claim
31 words
The method as recited in claim 1 , further comprising the step of computing critical areas for regions of the layout associated with shapes having edges with a slope of ±1.
Claim 13
Dependent Claim
30 words
The method as recited in claim 1 , further comprising the step of computing critical areas for regions of the layout associated with shapes having edges running horizontally and vertically.
Claim 14
Dependent Claim
35 words
The method as recited in claim 1 , further comprising the step of adapting computations of critical areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 15
Dependent Claim
44 words
The method as recited in claim 1 , wherein the step of summing the critical areas includes the steps of: adding critical areas that contribute to the total critical areas; subtracting critical areas that reduce the total critical area; and ignoring other critical areas.
Claim 16
Independent Claim
88 words
A method for predicting yield based on critical area for shorts of a layout of a circuit, comprising the steps of: computing a Voronoi diagram for the layout; computing a second order Voronoi diagram to arrive at a partitioning of the layout into regions; computing critical area within each region; summing the critical areas to arrive at a total critical area for shorts in the layout; predicting a sensitivity to defects of the layout based on the total critical area; and modifying the layout according to the sensitivity.
Claim 17
Independent Claim
88 words
A method for predicting yield based on critical area for shorts of a layout of a circuit, comprising the steps of: computing a Voronoi diagram for the layout; computing a second order Voronoi diagram to arrive at a partitioning of the layout into regions; computing critical area within each region; summing the critical areas to arrive at a total critical area for shorts in the layout; predicting a sensitivity to defects of the layout based on the total critical area; and modifying the layout according to the sensitivity.
Claim 18
Dependent Claim
23 words
The method as recited in claim 15 , further comprising the step of decomposing each region into shapes for calculating the critical areas.
Claim 19
Dependent Claim
77 words
The method as recited in claim 15 , wherein the step of computing critical area includes the step of computing the critical area according to the following equation: A c = ∫ 0 ∞ A ( r ) D ( r ) r , where A c is the critical area, A(r) is the area of the critical region for defects of radius r and D(r) is a defect density function.
Claim 20
Dependent Claim
36 words
The method as recited in claim 17 , wherein the defect density function includes the defect size distribution D(r)=r 0 2 /r 3 where r denotes spot defect radius and r 0 denotes a constant size.
Claim 21
Dependent Claim
56 words
The method as recited in claim 15 , wherein the second order Voronoi diagram includes Voronoi edges associated with shapes of the layout and the method further comprises the steps of classifying the Voronoi edges to identify between areas of the layout that contribute to the critical area and areas that subtract from the critical area.
Claim 22
Dependent Claim
16 words
The method as recited in claim 15 , wherein the shapes include locations for circuit components.
Claim 23
Dependent Claim
24 words
The method as recited in claim 15 , wherein the Voronoi diagram and the second order Voronoi diagram include an L ∞ distance metric.
Claim 24
Dependent Claim
29 words
The method as recited in claim 15 , wherein the step of computing the Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 25
Dependent Claim
31 words
The method as recited in claim 15 , wherein the step of computing the second order Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 26
Dependent Claim
31 words
The method as recited in claim 15 , further comprising the step of computing critical areas for regions of the layout associated with shapes having edges with a slope of ±1.
Claim 27
Dependent Claim
30 words
The method as recited in claim 15 , further comprising the step of computing critical areas for regions of the layout associated with shapes having edges running horizontally and vertically.
Claim 28
Dependent Claim
35 words
The method as recited in claim 15 , further comprising the step of adapting computations of critical areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 29
Dependent Claim
44 words
The method as recited in claim 15 , wherein the step of summing the critical areas includes the steps of: adding critical areas that contribute to the total critical areas; subtracting critical areas that reduce the total critical area; and ignoring other critical areas.
Claim 30
Dependent Claim
71 words
A computer based system for computing critical area for shorts of a layout, comprising: means for computing a Voronoi diagram for the layout and a second order Voronoi diagram using a sweep line algorithm to arrive at a partitioning of the layout into regions; means for computing critical area within each region; and means for summing the critical areas to arrive at a total critical area for shorts in the layout.
Claim 31
Dependent Claim
71 words
A computer based system for computing critical area for shorts of a layout, comprising: means for computing a Voronoi diagram for the layout and a second order Voronoi diagram using a sweep line algorithm to arrive at a partitioning of the layout into regions; means for computing critical area within each region; and means for summing the critical areas to arrive at a total critical area for shorts in the layout.
Claim 32
Dependent Claim
22 words
The system as recited in claim 28 , further comprises means for decomposing each region into shapes for calculating the critical areas.
Claim 33
Dependent Claim
20 words
The system as recited in claim 29 , wherein the shapes include at least one of triangles, rectangles and trapezoids.
Claim 34
Dependent Claim
76 words
The system as recited in claim 28 , wherein the means for computing critical area includes means for computing the critical area according to the following equation: A c = ∫ 0 ∞ A ( r ) D ( r ) r , where A c is the critical area, A(r) is the area of the critical region for defects of radius r and D(r) is a defect density function.
Claim 35
Dependent Claim
36 words
The system as recited in claim 31 , wherein the defect density function includes the defect size distribution D(r)=r 0 2 /r 3 where r denotes spot defect radius and r 0 denotes a constant size.
Claim 36
Dependent Claim
24 words
The system as recited in claim 28 , wherein the Voronoi diagram and the second order Voronoi diagram include an L ∞ distance metric.
Claim 37
Dependent Claim
34 words
The system as recited in claim 28 , further comprises means for adapting computations of critical areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 38
Dependent Claim
13 words
The system as recited in claim 28 , wherein the layout includes nets.
Claim 39
Dependent Claim
14 words
The system as recited in claim 28 , wherein the layout includes circuit components.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-23 | 2004-07-24 | 2005-01-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-23 | 2008-07-24 | 2009-01-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-23 | 2012-07-24 | 2013-01-23 | $7700.00 | Window Closed / Lapsed |