Patent US6317859B1 successfully refreshed from Google Patents.
US6317859B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for determining critical area for circuit layouts
Assignee: International Business Machines Corp
•
Filing: 1999-06-09
•
Granted: 2001-11-13
•
Expires: 2019-06-09
Abstract
Abstract A method for computing critical area for opens of a layout, which may be implemented by program storage device readable by machine, tangibly embodying a program of instructions executable by the machine, to perform the method steps includes computing Voronoi diagrams of shapes of the layout, determining core elements and weights for the core elements of the shapes, computing a weighted Voronoi diagram for the layout 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 opens in the layout.
Inventors
- 👤 Evanthia Papadopoulou
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 12:29
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
89 words
A method for computing critical area for opens of a layout, comprising the steps of: computing Voronoi diagrams of shapes of the layout; determining core elements and weights for the core elements of the shapes; computing a weighted Voronoi diagram for the layout 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 opens in the layout; and identifying areas in the layout sensitive to opens based on the critical areas.
Claim 2
Independent Claim
89 words
A method for computing critical area for opens of a layout, comprising the steps of: computing Voronoi diagrams of shapes of the layout; determining core elements and weights for the core elements of the shapes; computing a weighted Voronoi diagram for the layout 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 opens in the layout; and identifying areas in the layout sensitive to opens based on the critical areas.
Claim 3
Dependent Claim
78 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 4
Dependent Claim
36 words
The method as recited in claim 2 , 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 5
Dependent Claim
51 words
The method as recited in claim 1 , wherein the Voronoi diagram includes Voronoi edges associated with shapes of the layout and the method further comprises the step of classifying the Voronoi edges to identify between edges that contribute to the critical area and edges that subtract from the critical area.
Claim 6
Dependent Claim
16 words
The method as recited in claim 4 , wherein the shapes include locations for circuit components.
Claim 7
Dependent Claim
23 words
The method as recited in claim 1 , wherein the Voronoi diagram and the weighted Voronoi diagram include an L ∞ distance metric.
Claim 8
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 9
Dependent Claim
29 words
The method as recited in claim 1 , wherein the step of weighting the Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 10
Dependent Claim
24 words
The method as recited in claim 1 , further comprises the step of adjusting the shapes of the layout according to the critical area.
Claim 11
Dependent Claim
29 words
The method as recited in claim 1 , further comprises the step of computing areas for regions of the layout associated with shapes having edges running horizontally and vertically.
Claim 12
Dependent Claim
34 words
The method as recited in claim 1 , further comprises the step of adapting computations of areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 13
Dependent Claim
46 words
The method as recited in claim 1 , wherein the step of summing the critical areas includes the steps of: adding amounts derived from Voronoi edges that contribute to the total critical areas; and subtracting amounts derived from Voronoi edges that reduce the total critical area.
Claim 14
Dependent Claim
17 words
The method as recited in claim 1 , wherein the opens include one of breaks and blocks.
Claim 15
Dependent Claim
53 words
The method as recited in claim 1 , wherein the opens include partial opens and the method further comprising the step of providing a partial critical area for computing the critical area of a partial open by multiplying neighboring core elements by a fraction to represent a critical radius of the partial open.
Claim 16
Independent Claim
97 words
A method for predicting yield based on critical area for opens of a layout of a circuit, comprising the steps of: computing a Voronoi diagram based on core elements of the layout; computing a weighted Voronoi diagram for segments of the core elements 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 opens 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
97 words
A method for predicting yield based on critical area for opens of a layout of a circuit, comprising the steps of: computing a Voronoi diagram based on core elements of the layout; computing a weighted Voronoi diagram for segments of the core elements 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 opens 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
78 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 19
Dependent Claim
36 words
The method as recited in claim 16 , 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 20
Dependent Claim
51 words
The method as recited in claim 15 , wherein the Voronoi diagram includes Voronoi edges associated with shapes of the layout and the method further comprises the step of classifying the Voronoi edges to identify between edges that contribute to the critical area and edges that subtract from the critical area.
Claim 21
Dependent Claim
16 words
The method as recited in claim 18 , wherein the shapes include locations for circuit components.
Claim 22
Dependent Claim
23 words
The method as recited in claim 15 , wherein the Voronoi diagram and the weighted Voronoi diagram include an L ∞ distance metric.
Claim 23
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 24
Dependent Claim
31 words
The method as recited in claim 15 , wherein the step of computing a weighted Voronoi diagram includes the step of computing the weighted Voronoi diagram using a sweep line algorithm.
Claim 25
Dependent Claim
29 words
The method as recited in claim 15 , further comprises the step of computing areas for regions of the layout associated with shapes having edges running horizontally and vertically.
Claim 26
Dependent Claim
34 words
The method as recited in claim 15 , further comprises the step of adapting computations of areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 27
Dependent Claim
46 words
The method as recited in claim 15 , wherein the step of summing the critical areas includes the steps of: adding amounts derived from Voronoi edges that contribute to the total critical areas; and subtracting amounts derived from Voronoi edges that reduce the total critical area.
Claim 28
Dependent Claim
17 words
The method as recited in claim 15 , wherein the opens include one of breaks and blocks.
Claim 29
Dependent Claim
53 words
The method as recited in claim 15 , wherein the opens include partial opens and the method further comprising the step of providing a partial critical area for computing the critical area of a partial open by multiplying neighboring core elements by a fraction to represent a critical radius of the partial open.
Claim 30
Dependent Claim
95 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing critical area for opens of a layout, the method steps comprising: computing Voronoi diagrams of shapes of the layout; determining core elements and weights for the core elements of the shapes; computing a weighted Voronoi diagram for the layout 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 opens in the layout.
Claim 31
Dependent Claim
95 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing critical area for opens of a layout, the method steps comprising: computing Voronoi diagrams of shapes of the layout; determining core elements and weights for the core elements of the shapes; computing a weighted Voronoi diagram for the layout 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 opens in the layout.
Claim 32
Dependent Claim
80 words
The program storage device as recited in claim 28 , 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 33
Dependent Claim
36 words
The program storage device as recited in claim 29 , wherein the defect density function includes the defect size distribution D(r)=r 0 2 /r 3 where r denotes spot defect radius and rodenotes a constant size.
Claim 34
Dependent Claim
54 words
The program storage device as recited in claim 28 , wherein the Voronoi diagram includes Voronoi edges associated with shapes of the layout and the method steps further comprising the step of classifying the Voronoi edges to identify between edges that contribute to the critical area and edges that subtract from the critical area.
Claim 35
Dependent Claim
18 words
The program storage device as recited in claim 31 , wherein the shapes include locations for circuit components.
Claim 36
Dependent Claim
25 words
The program storage device as recited in claim 28 , wherein the Voronoi diagram and the weighted Voronoi diagram include an L ∞ distance metric.
Claim 37
Dependent Claim
31 words
The program storage device as recited in claim 28 , wherein the step of computing the Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 38
Dependent Claim
31 words
The program storage device as recited in claim 28 , wherein the step of weighting the Voronoi diagram includes the step of computing the Voronoi diagram using a sweep line algorithm.
Claim 39
Dependent Claim
40 words
The program storage device as recited in claim 28 , wherein the method steps further comprising the step of adapting computations of areas for the regions of the layout associated with shapes in the layout having edges with any slope.
Claim 40
Dependent Claim
48 words
The program storage device as recited in claim 28 , wherein the step of summing the critical areas includes the steps of: adding amounts derived from Voronoi edges that contribute to the total critical areas; and subtracting amounts derived from Voronoi edges that reduce the total critical area.
Claim 41
Dependent Claim
19 words
The program storage device as recited in claim 28 , wherein the opens include one of breaks and blocks.
Claim 42
Dependent Claim
57 words
The program storage device as recited in claim 28 , wherein the opens include partial opens and wherein the method steps further comprise the step of providing a partial critical area for computing the critical area of a partial open by multiplying neighboring core elements by a fraction to represent a critical radius of the partial open.
References Cited (Backward Citations)
US6178539B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-12 | 2005-05-14 | 2005-11-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-12 | 2009-05-14 | 2009-11-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-12 | 2013-05-14 | 2013-11-13 | $7700.00 | Window Closed / Lapsed |