Patent US6324673B1 successfully refreshed from Google Patents.
US6324673B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for edge-endpoint-based VLSI design rule checking
Assignee: NEC Corp
•
Filing: 1999-05-28
•
Granted: 2001-11-27
•
Expires: 2019-05-28
Abstract
Abstract The method and apparatus for performing design rule checking on Manhattan structures in VLSI circuit layouts. The method and apparatus provides an edge-endpoint-based technique for checking the geometry and spacing of the VLSI circuit layout. The edge-endpoint-based technique uses a scanline algorithm that detects errors between adjacent structures that do not simultaneously intersect the scanline. The method also provides efficient error compilation. The apparatus allows for the design rules to be changed as the VLSI circuit layout evolves. The apparatus can process the VLSI circuit layout with a single processor, and the apparatus provides for multiple processors to process slices of the VLSI circuit layout, thereby enhancing the speed of the design rule checking over traditional software-only techniques.
Inventors
- 👤 Zhen Luo
- 👤 Margaret Martonosi
- 👤 Pranav Ashar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 10:22
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
118 words
The method for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 2
Independent Claim
118 words
The method for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 3
Dependent Claim
50 words
The method as set forth in claim 1 , wherein transforming said integrated circuit mask layout further comprises representing each of said plurality of endpoints as a numerical value, consisting of an X-coordinate field, a Y-coordinate field, a layer field, an orientation field, a directional field and a processing field.
Claim 4
Dependent Claim
64 words
The method as set forth in claim 2 , wherein transforming said integrated circuit mask layout further comprises: sorting said plurality of endpoints in canonical order of said X-coordinate field, said Y-coordinate field, said layer field and said orientation field; grouping said sorted plurality of endpoints by said X-coordinate field; and removing said X-coordinate field from each group of said sorted plurality of endpoints.
Claim 5
Dependent Claim
35 words
The method as set forth in claim 2 , wherein transforming said integrated circuit mask layout further comprises removal of endpoints from said plurality of endpoints wherein said endpoints only differ in said directional field.
Claim 6
Dependent Claim
22 words
The method as set forth in claim 2 , wherein said predetermined intervals correlate to the X-coordinates of said plurality of endpoints.
Claim 7
Dependent Claim
44 words
The method as set forth in claim 1 , wherein decomposing said endpoints into said plurality of true endpoints further comprises using counters to determine if the intersection of said scanline with each of said endpoints is a true endpoint of a bounded region.
Claim 8
Dependent Claim
45 words
The method as set forth in claim 1 , wherein decomposing said endpoints into said plurality of true points further comprises using counters to determine if the intersection of said scanline with each of said old points is a true point of a bounded region.
Claim 9
Dependent Claim
63 words
The method as set forth in claim 1 , wherein decomposing said endpoints further comprises merging true points, true endpoints and old points that were compared to said predetermined design rules at a previous predetermined interval with the true points, true endpoints and old points currently intersecting said scanline, and sorting the merged true points, true endpoints and old points in canonical order.
Claim 10
Dependent Claim
30 words
The method as set forth in claim 8 , wherein decomposing said endpoints into said plurality of old points further comprises deletion of old points that are no longer valid.
Claim 11
Dependent Claim
30 words
The method as set forth in claim 1 , wherein decomposing said endpoints further comprises searching the most forward edge of coincident edges first for true points or true endpoints.
Claim 12
Dependent Claim
33 words
The method as set forth in claim 1 , decomposing said endpoints further comprises adding a virtual extension of predetermined value to selected true endpoints for flagging violations of said predetermined design rules.
Claim 13
Dependent Claim
46 words
The method as set forth in claim 11 , wherein adding a virtual extension further comprises determining if each of said selected true endpoints are true forward ending endpoints outside the edge of a bounded region, or a true backward ending endpoint inside a bounded region.
Claim 14
Dependent Claim
46 words
The method as set forth in claim 11 , wherein evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules further comprises using said virtual extensions of said selected true endpoints to flag violations of said predetermined design rules.
Claim 15
Dependent Claim
61 words
The method as set forth in claim 1 , wherein evaluating said plurality of true points and said plurality of true endpoints against predetermined design rules further comprises using at least two sets of predetermined design rules, each set of said predetermined design rules used at least once in evaluating said plurality of true points and said plurality of true endpoints.
Claim 16
Dependent Claim
20 words
The method as set forth in claim 1 , wherein compiling said design rule errors further comprises discarding repetitive errors.
Claim 17
Dependent Claim
39 words
The method as set forth in claim 1 , wherein transforming said integrated circuit mask layout further comprises dividing said integrated circuit mask layout into a plurality of mask slices, and sweeping said scanline across said mask slices simultaneously.
Claim 18
Dependent Claim
40 words
The method as set forth in claim 16 , wherein the dividing of said integrated circuit mask layout into a plurality of mask slices further comprises extending all edges crossing the slice with a virtual edge of a predetermined length.
Claim 19
Dependent Claim
137 words
A computer system adapted for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: a processor; and a memory including software instructions adapted to enable said computer system to perform: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping of said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 20
Dependent Claim
137 words
A computer system adapted for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: a processor; and a memory including software instructions adapted to enable said computer system to perform: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping of said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 21
Dependent Claim
150 words
A computer program product for enabling a computer to perform analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: software instructions for enabling said computer to perform predetermined operations, and a computer readable medium bearing said software instructions; said predetermined operations including: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping of said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at is each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 22
Dependent Claim
150 words
A computer program product for enabling a computer to perform analysis of an integrated circuit mask layout against predetermined design rules using a scanline, comprising: software instructions for enabling said computer to perform predetermined operations, and a computer readable medium bearing said software instructions; said predetermined operations including: transforming said integrated circuit mask layout into a plurality of endpoints; sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, wherein sweeping of said scanline further comprises: decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at is each of said predetermined intervals; evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, and flagging violations of said predetermined design rules; and compiling said violations of said predetermined design rules.
Claim 23
Independent Claim
120 words
An apparatus for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, including: a processor for transforming said integrated circuit mask layout into a plurality of endpoints, sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, and a design rule processor for decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals, evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, flagging violations of said predetermined design rules, and compiling said violations of said predetermined design rules.
Claim 24
Independent Claim
120 words
An apparatus for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, including: a processor for transforming said integrated circuit mask layout into a plurality of endpoints, sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals, and a design rule processor for decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at each of said predetermined intervals, evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at each of said predetermined intervals along said scanline, flagging violations of said predetermined design rules, and compiling said violations of said predetermined design rules.
Claim 25
Dependent Claim
45 words
The apparatus as set forth in claim 20 , wherein said processor transforms said integrated circuit mask layout into a plurality of endpoints, each consisting of an X-coordinate field, a Y-coordinate field, a layer field, an orientation field, a directional field and a processing field.
Claim 26
Dependent Claim
58 words
The apparatus as set forth in claim 21 , wherein said processor sorts said plurality of endpoints in canonical order of said X-coordinate field, said Y-coordinate field, said layer field and said orientation field, groups said sorted plurality of endpoints by said X-coordinate field, and removes said X-coordinate field from each group of said sorted plurality of endpoints.
Claim 27
Dependent Claim
28 words
The apparatus as set forth in claim 21 , wherein said processor removes endpoints from said plurality of endpoints wherein said endpoints only differ in said directional field.
Claim 28
Dependent Claim
24 words
The apparatus as set forth in claim 21 , wherein said processor correlates said predetermined intervals to the X-coordinates of said plurality of endpoints.
Claim 29
Dependent Claim
38 words
The apparatus as set forth in claim 20 , wherein said processor decomposes said endpoints using counters to determine if the intersection of said scanline with each of said endpoints is a true endpoint of a bounded region.
Claim 30
Dependent Claim
40 words
The apparatus as set forth in claim 20 , wherein said design rule processor decomposes said endpoints using counters to determine if the intersection of said scanline with each of said endpoints is a true point of a bounded region.
Claim 31
Dependent Claim
62 words
The apparatus as set forth in claim 20 , wherein said design rule processor merges true points, true endpoints and old points that were evaluated against said predetermined design rules at a previous predetermined interval with the true points, true endpoints and old points currently intersecting said scanline, and sorts the merged true points, true endpoints and old points in canonical order.
Claim 32
Dependent Claim
22 words
The apparatus as set forth in claim 27 , wherein said design rule processor deletes old points that are no longer valid.
Claim 33
Dependent Claim
29 words
The apparatus as set forth in claim 20 , wherein said design rule processor searches the most forward edge of coincident edges first for true points or true endpoints.
Claim 34
Dependent Claim
31 words
The apparatus as set forth in claim 20 , wherein said processor adds a virtual extension of predetermined value to selected true endpoints for flagging violations of said predetermined design rules.
Claim 35
Dependent Claim
48 words
The apparatus as set forth in claim 30 , wherein said design rule processor evaluates said plurality of true points and said plurality of true endpoints against said predetermined design rules using said virtual extensions of said selected true endpoints to flag violations of said predetermined design rules.
Claim 36
Dependent Claim
44 words
The apparatus as set forth in claim 20 , wherein said design rule processor determines if each of said selected true endpoints are true forward ending endpoints outside the edge of a bounded region, or a true backward ending endpoint inside a bounded region.
Claim 37
Dependent Claim
47 words
The apparatus as set forth in claim 20 , wherein said design rule processor uses at least two sets of predetermined design rules, each set of said predetermined design rules used at least once in evaluating said plurality of true points and said plurality of true endpoints.
Claim 38
Dependent Claim
39 words
The apparatus as set forth in claim 33 , wherein said processor selects a set of predetermined design rules for said design rule processor to use for evaluating said plurality of true points and said plurality of true endpoints.
Claim 39
Dependent Claim
35 words
The apparatus as set forth in claim 34 , wherein said design rule processor downloads said predetermined set of design rules prior to evaluating said plurality of true points and said plurality of true endpoints.
Claim 40
Dependent Claim
17 words
The apparatus as set forth in claim 20 , wherein said design rule processor discards repetitive errors.
Claim 41
Dependent Claim
37 words
The apparatus as set forth in claim 20 , wherein said design rule processor further comprises: an access circuit; a first memory; a second memory; a third memory; a merge/sorter; a rules checker; and an error memory.
Claim 42
Dependent Claim
23 words
The apparatus as set forth in claim 37 , wherein said access circuit allows said processor to interface with said design rule processor.
Claim 43
Dependent Claim
26 words
The apparatus as set forth in claim 37 , wherein said first memory stores said plurality of endpoints received from said processor via said bus circuit.
Claim 44
Dependent Claim
20 words
The apparatus as set forth in claim 37 , wherein said second memory stores the output of said rules checker.
Claim 45
Dependent Claim
17 words
The apparatus as set forth in claim 37 , wherein said second memory comprises a dual-port RAM.
Claim 46
Dependent Claim
18 words
The apparatus as set forth in claim 37 , wherein said second memory comprises a double buffered memory.
Claim 47
Dependent Claim
27 words
The apparatus as set forth in claim 37 , wherein said merge/sorter merges the points stored in said first memory with points stored in said second memory.
Claim 48
Dependent Claim
17 words
The apparatus as set forth in claim 37 , wherein said merge/sorter sorts points into canonical order.
Claim 49
Dependent Claim
24 words
The apparatus as set forth in claim 37 , wherein said rules checker evaluates said predetermined design rules against the output of said merge/sorter.
Claim 50
Dependent Claim
21 words
The apparatus as set forth in claim 37 , wherein said error memory stores design rule violations from said rules checker.
Claim 51
Dependent Claim
24 words
The apparatus as set forth in claim 37 , wherein said third memory is used for storage of intermediate data generated by said processor.
Claim 52
Dependent Claim
17 words
The apparatus as set forth in claim 37 , wherein said design rule processor is an FPGA.
Claim 53
Dependent Claim
17 words
The apparatus as set forth in claim 37 , wherein said design rule processor is an ASIC.
Claim 54
Independent Claim
118 words
An apparatus for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, including: a processor for transforming said integrated circuit mask layout into a plurality of endpoints, sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals; and a plurality of design rule processors for decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at said predetermined intervals, evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at said predetermined intervals along said scanline, flagging violations of said predetermined design rules, and compiling said violations for said predetermined design ruled.
Claim 55
Independent Claim
118 words
An apparatus for analysis of an integrated circuit mask layout against predetermined design rules using a scanline, including: a processor for transforming said integrated circuit mask layout into a plurality of endpoints, sweeping said scanline through said plurality of endpoints, pausing at predetermined intervals; and a plurality of design rule processors for decomposing said plurality of endpoints into a plurality of true points, a plurality of true endpoints and a plurality of old points at said predetermined intervals, evaluating said plurality of true points and said plurality of true endpoints against said predetermined design rules at said predetermined intervals along said scanline, flagging violations of said predetermined design rules, and compiling said violations for said predetermined design ruled.
Claim 56
Dependent Claim
39 words
The apparatus as set forth in claim 50 , wherein said processor divides said integrated circuit mask layout into a plurality of mask slices, and said plurality of design rule processors sweep said scanline across said mask slices simultaneously.
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-11-26 | 2005-05-28 | 2005-11-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-26 | 2009-05-28 | 2009-11-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-26 | 2013-05-28 | 2013-11-27 | $7700.00 | Window Closed / Lapsed |