# US 10,311,195 B2 · Incremental multi-patterning validation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,311,195 B2
- Document ID: US10311195B2
- Status: Granted
- Kind: B2
- Application number: 14/996,796
- Filed: 2016-01-15
- Published: 2017-07-20
- Granted: 2019-06-04
- Earliest claimed: 2016-01-15
- Assignees: Synopsys, Inc.
- Applicants: Synopsys, Inc.
- Inventors: Yuli Xue; Weiping Fang; John Robert Studders; Byungwook Kim
- Web page: https://patentgrep.com/patent/US10311195B2

## CPC

- G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36)
- G03F 1/00: Originals for photomechanical production of textured or patterned surfaces, e.g., masks, photo-masks, reticles; Mask blanks or pellicles therefor; Containers specially adapted therefor; Preparation thereof
- G03F 1/36: Masks having proximity correction features; Preparation thereof, e.g. optical proximity correction [OPC] design processes
- H10D 86/011: {comprising FinFETs}
- G06F 2119/18: Manufacturability analysis or optimisation for manufacturability
- H10D 86/01: Manufacture or treatment
- Y02P 90/02: Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G03F: PHOTOMECHANICAL PRODUCTION OF TEXTURED OR PATTERNED SURFACES, e.g. FOR PRINTING, FOR PROCESSING OF SEMICONDUCTOR DEVICES; MATERIALS THEREFOR; ORIGINALS THEREFOR; APPARATUS SPECIALLY ADAPTED THEREFOR; (phototypographic composing devices B41B; photosensitive materials or processes for photographic purposes G03C; electrophotography, sensitive layers or processes therefor G03G)
- H10D: INORGANIC ELECTRIC SEMICONDUCTOR DEVICES
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

A computer-implemented method for validating a design characterized by a multi-patterning layer is presented. The method includes receiving the multi-patterning layer in a memory of the computer when the computer is invoked to validate the design. The method further includes correcting, using the computer, a first error in a first shape of the multi-patterning layer in accordance with a first rule thereby forming a corrected layer. The method further includes incrementally validating, using the computer, a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer.

## Claims

### Claim 1

A computer-implemented method for validating a design characterized by a multi-patterning layer, the method comprising:
receiving the multi-patterning layer in a memory of the computer when the computer is invoked to validate the design, wherein the multi-patterning layer includes a first error in a first shape of the multi-patterning layer;
correcting, using the computer, the first error in accordance with a first rule thereby forming a corrected layer;
incrementally validating, using the computer, a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer, wherein the first portion includes the corrected first shape, wherein the first graph includes the first connected component, wherein the first portion is associated with the first connected component;
forming, using the computer, a second graph including the first connected component and a second connected component different from the first connected component;
selecting, using the computer, the first portion of the corrected layer; and
validating, using the computer, the selected first portion of the corrected layer without validating a second portion of the corrected layer associated with the second connected component.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the first error prevents decomposition of the multi-patterning layer into a plurality of colors.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the first portion includes each one of a first plurality of shapes in the corrected layer associated with the first connected component that includes a first vertex associated with the first shape.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1 further comprising:
cutting, using the computer, a second shape of the multi-patterning layer associated with an articulation point of the first graph thereby forming a second connected component different from the first connected component.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein the second shape is connected to a power or ground line in the design.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein selecting comprises:
determining a first area associated with a change between the multi-patterning layer and the corrected layer that corrects the first error;
increasing a size of the first area by a second rule thereby forming a second area;
selecting the first connected component associated with at least one of a first plurality of shapes of the multi-patterning data base that interact with the second area;
determining a third area in accordance with the selected first connected component, the first area, and the second area; and
selecting each one of the second plurality of shapes of the corrected layer that interact with the third area thereby forming the first portion of the corrected layer.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the first graph is the same as the second graph.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the first graph is different from the second graph.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, wherein forming the second graph comprises:
identifying, using the computer, an articulation point of the first graph; and
cutting, using the computer, a shape of the multi-patterning layer associated with the articulation point thereby forming a second shape associated with the first connected component and a third shape associated with the second connected component.

### Claim 10

A computer system operative to:
receive a multi-patterning layer of a design in a memory of the computer when the computer is invoked to validate the design, wherein the multi-patterning layer includes a first error in a first shape of the multi-patterning layer;
correct the first error in accordance with a first rule thereby forming a corrected layer;
incrementally validate a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer, wherein the first portion includes the corrected first shape, wherein the first graph includes the first connected component, wherein the first portion is associated with the first connected component
form a second graph including the first connected component and a second connected component different from the first connected component;
select the first portion of the corrected layer; and
validate the selected first portion of the corrected layer without validating a second portion of the corrected layer associated with the second connected component.

### Claim 11 (depends on 10)

The computer system of claim 10, wherein the first error prevents decomposition of the multi-patterning layer into a plurality of colors.

### Claim 12 (depends on 10)

The computer system of claim 10, wherein the first portion includes each one of a first plurality of shapes in the corrected layer associated with the first connected component that includes a first vertex associated with the first shape.

### Claim 13 (depends on 10)

The computer system of claim 10 further operative to:
cut a second shape of the multi-patterning layer associated with an articulation point of the first graph thereby forming a second connected component different from the first connected component.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein the second shape is connected to a power or ground line in the design.

### Claim 15 (depends on 10)

The computer system of claim 10 further operative to:
determine a first area associated with a change between the multi-patterning layer and the corrected layer that corrects the first error;
increase a size of the first area by a second rule thereby forming a second area;
select the first connected component associated with at least one of a first plurality of shapes of the multi-patterning data base that interact with the second area;
determine a third area in accordance with the selected first connected component, the first area, and the second area; and
select each one of the second plurality of shapes of the corrected layer that interact with the third area thereby forming the first portion of the corrected layer.

### Claim 16 (depends on 10)

The computer system of claim 10 further operative to:
identify an articulation point of the first graph; and
cut a shape of the multi-patterning layer associated with the articulation point thereby forming a second shape associated with the first connected component and a third shape associated with the second connected component.

### Claim 17

A non-transitory computer-readable storage medium comprising instructions, which when executed by a computer, cause the computer to:
receive a multi-patterning layer of a design in a memory of the computer when the computer is invoked to validate the design, wherein the multi-patterning layer includes a first error in a first shape of the multi-patterning layer;
correct the first error in accordance with a first rule thereby forming a corrected layer;
incrementally validate a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer, wherein the first portion includes the corrected first shape, wherein the first graph includes the first connected component, wherein the first portion is associated with the first connected component;
form a second graph including the first connected component and a second connected component different from the first connected component;
select the first portion of the corrected layer; and
validate the selected first portion of the corrected layer without validating a second portion of the corrected layer associated with the second connected component.

### Claim 18 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the first error prevents decomposition of the multi-patterning layer into a plurality of colors.

### Claim 19 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the first portion includes each one of a first plurality of shapes in the corrected layer associated with the first connected component that includes a first vertex associated with the first shape.

### Claim 20 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the instructions further cause the computer to:
cut a second shape of the multi-patterning layer associated with an articulation point of the first graph thereby forming a second connected component different from the first connected component.

### Claim 21 (depends on 20)

The non-transitory computer-readable storage medium of claim 20, wherein the second shape is connected to a power or ground line in the design.

### Claim 22 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the instructions further cause the computer to:
determine a first area associated with a change between the multi-patterning layer and the corrected layer that corrects the first error;
increase a size of the first area by a second rule thereby forming a second area;
select the first connected component associated with at least one of a first plurality of shapes of the multi-patterning data base that interact with the second area;
determine a third area in accordance with the selected first connected component, the first area, and the second area; and
select each one of the second plurality of shapes of the corrected layer that interact with the third area thereby forming the first portion of the corrected layer.

### Claim 23 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the instructions further cause the computer to:
identify an articulation point of the first graph; and
cut a shape of the multi-patterning layer associated with the articulation point thereby forming a second shape associated with the first connected component and a third shape associated with the second connected component.