# US 10,372,037 B2 · Constructing fill shapes for double-patterning technology

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

- Number: US 10,372,037 B2
- Document ID: US10372037B2
- Status: Granted
- Kind: B2
- Application number: 14/929,113
- Filed: 2015-10-30
- Published: 2017-05-04
- Granted: 2019-08-06
- Earliest claimed: 2015-10-30
- Assignees: Synopsys, Inc.
- Applicants: Synopsys, Inc.
- Inventors: Himanshu Sharma; Byungwook Kim; Virender Kashyap; Abhishek Khandelwal
- Web page: https://patentgrep.com/patent/US10372037B2

## CPC

- G03F 7/0035: {Multiple processes, e.g. applying a further resist layer on an already in a previously step, processed pattern or textured surface}
- G03F 1/68: Preparation processes not covered by groups G03F1/20 - G03F1/50
- G03F 1/70: Adapting basic layout or design of masks to lithographic process requirements, e.g., second iteration correction of mask patterns for imaging
- G03F 7/70466: {Multiple exposures, e.g. combination of fine and coarse exposures, double patterning or multiple exposures for printing a single feature (stitching G03F7/70475)}
- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- 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: 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for constructing a design characterized by a double patterning layer is presented. The method includes receiving the design in a memory of the computer when the computer is invoked to construct the design. The method further includes generating, using the computer, a multitude of fill shapes along a multitude of tracks associated with a multitude of net shapes. The multitude of fill shapes and the multitude of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer.

## Claims

### Claim 1

A computer-implemented method for constructing a design characterized by a double patterning layer, the method comprising:
receiving the design in a memory of the computer when the computer is invoked to construct the design, wherein the design includes a plurality of net shapes each previously routed in accordance with a netlist of the design;
generating, using the computer, a plurality of fill shapes along a plurality of tracks associated with the plurality of net shapes, wherein the plurality of fill shapes and the plurality of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer, wherein the plurality of fill shapes are not associated with the netlist of the design, wherein the plurality of fill shapes are present in at least one mask generated from the design when the at least one mask is prepared;
decomposing the plurality of net shapes into the two colors in accordance with a graph;
surrounding each decomposed net shape with a blocking region associated with a color of the two colors that corresponds to the color of the decomposed net shape to form a plurality of blocking regions; and
constructing the plurality of fill shapes in accordance with the plurality of blocking regions.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein constructing further includes constructing each one of the plurality of fill shapes along a different one of the plurality of tracks except wherever one of the plurality of blocking regions is associated with the same color as the color associated with the each one of the plurality of fill shapes.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein any immediately adjacent tracks of the plurality of tracks are assigned to alternating different colors of the two colors, wherein constructing further includes associating each one of the plurality of fill shapes with the same color as the color associated with the track of the plurality of tracks that the fill shape is disposed along.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein surrounding further includes sizing each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction along a longitudinal axis of the plurality of tracks by a value associated with a first shape to second shape constraint of the double patterning layer, wherein the first shape and the second shape are associated with the same color.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein surrounding further includes sizing each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction orthogonal to a longitudinal axis of the plurality of tracks by a value associated with a track pitch constraint of the double patterning layer.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the two colors include a first color and a second color different from the first color, wherein the plurality of tracks are each sequentially numbered and include a plurality of even numbered tracks and a plurality of odd numbered tracks, the method further comprising:
assigning, using the computer, the first color to the plurality of even numbered tracks; and
assigning, using the computer, the second color to the plurality of odd numbered tracks, thereby assigning any immediately adjacent tracks of the plurality of tracks to alternating different colors, when immediately adjacent tracks are not previously assigned to alternating different colors.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the
graph is characterized by having:
a plurality of vertices each associated with a different one of the plurality of net shapes; and
a plurality of edges each joining a pair of the plurality of vertices when an immediately adjacent pair of the plurality of net shapes associated with the pair of the plurality of vertices are constrained by the spacing constraint of the double patterning layer, the method further comprising:
selecting a selected one of the plurality of net shapes in accordance with a minimum width constraint of the double patterning layer, wherein the selected net shape is disposed along one of the plurality of tracks;
designating one of the plurality of vertices associated with the selected net shape to the color of the two colors that is associated with the color of the track upon which the selected net shape is disposed along;
decomposing the plurality of vertices in the graph into the two colors in accordance with the designated one of the plurality of vertices; and
assigning the two colors to the plurality of net shapes in accordance with the decomposed graph.

### Claim 8

A computer system operative to:
receive a design, characterized by a double patterning layer, in a memory of the computer when the computer is invoked to construct the design, wherein the design includes a plurality of net shapes each previously routed in accordance with a netlist of the design;
generate a plurality of fill shapes along a plurality of tracks associated with the plurality of net shapes, wherein the plurality of fill shapes and the plurality of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer, wherein the plurality of fill shapes are not associated with the netlist of the design, wherein the plurality of fill shapes are present in at least one mask generated from the design when the at least one mask is prepared;
decompose the plurality of net shapes into the two colors in accordance with a graph;
surround each decomposed net shape with a blocking region associated with a color of the two colors that corresponds to the color of the decomposed net shape to form a plurality of blocking regions; and
construct the plurality of fill shapes in accordance with the plurality of blocking regions.

### Claim 9 (depends on 8)

The computer system of claim 8 further operative to construct each one of the plurality of fill shapes along a different one of the plurality of tracks except wherever one of the plurality of blocking regions is associated with the same color as the color associated with the each one of the plurality of fill shapes.

### Claim 10 (depends on 9)

The computer system of claim 9, wherein any immediately adjacent tracks of the plurality of tracks are assigned to alternating different colors of the two colors, the computer system further operative to associate each one of the plurality of fill shapes with the same color as the color associated with the track of the plurality of tracks that the fill shape is disposed along.

### Claim 11 (depends on 8)

The computer system of claim 8 further operative to size each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction along a longitudinal axis of the plurality of tracks by a value associated with a first shape to second shape constraint of the double patterning layer, wherein the first shape and the second shape are associated with the same color.

### Claim 12 (depends on 8)

The computer system of claim 8 further operative to size each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction orthogonal to a longitudinal axis of the plurality of tracks by a value associated with a track pitch constraint of the double patterning layer.

### Claim 13 (depends on 8)

The computer system of claim 8, wherein the two colors include a first color and a second color different from the first color, wherein the plurality of tracks are each sequentially numbered and include a plurality of even numbered tracks and a plurality of odd numbered tracks, computer system further operative to:
assign the first color to the plurality of even numbered tracks; and
assign the second color to the plurality of odd numbered tracks, thereby operative to assign any immediately adjacent tracks of the plurality of tracks to alternating different colors, when immediately adjacent tracks are not previously assigned to alternating different colors.

### Claim 14 (depends on 8)

The computer system of claim 8, wherein the
graph is characterized by having:
a plurality of vertices each associated with a different one of the plurality of net shapes; and
a plurality of edges each joining a pair of the plurality of vertices when an immediately adjacent pair of the plurality of net shapes associated with the pair of the plurality of vertices are constrained by the spacing constraint of the double patterning layer, the computer system further operative to:
select a selected one of the plurality of net shapes in accordance with a minimum width constraint of the double patterning layer, wherein the selected net shape is disposed along one of the plurality of tracks;
designate one of the plurality of vertices associated with the selected net shape to the color of the two colors that is associated with the color of the track upon which the selected net shape is disposed along;
decompose the plurality of vertices in the graph into the two colors in accordance with the designated one of the plurality of vertices; and
assign the two colors to the plurality of net shapes in accordance with the decomposed graph.

### Claim 15

A non-transitory computer-readable storage medium comprising instructions, which when executed by a computer, cause the computer to:
receive a design, characterized by a double patterning layer, in a memory of the computer when the computer is invoked to construct the design, wherein the design includes a plurality of net shapes each previously routed in accordance with a netlist of the design;
generate a plurality of fill shapes along a plurality of tracks associated with the plurality of net shapes, wherein the plurality of fill shapes and the plurality of net shapes are decomposable into two colors in accordance with a spacing constraint of the double patterning layer, wherein the plurality of fill shapes are not associated with the netlist of the design, wherein the plurality of fill shapes are present in at least one mask generated from the design when the at least one mask is prepared;
decompose the plurality of net shapes into the two colors in accordance with a graph;
surround each decomposed net shape with a blocking region associated with a color of the two colors that corresponds to the color of the decomposed net shape to form a plurality of blocking regions; and
construct the plurality of fill shapes in accordance with the plurality of blocking regions.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the computer to construct each one of the plurality of fill shapes along a different one of the plurality of tracks except wherever one of the plurality of blocking regions is associated with the same color as the color associated with the each one of the plurality of fill shapes.

### Claim 17 (depends on 16)

The non-transitory computer-readable storage medium of claim 16, wherein any immediately adjacent tracks of the plurality of tracks are assigned to alternating different colors of the two colors, wherein the instructions further cause the computer to associate each one of the plurality of fill shapes with the same color as the color associated with the track of the plurality of tracks that the fill shape is disposed along.

### Claim 18 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the computer to size each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction along a longitudinal axis of the plurality of tracks by a value associated with a first shape to second shape constraint of the double patterning layer, wherein the first shape and the second shape are associated with the same color.

### Claim 19 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the computer to size each one of the plurality of blocking regions such that each blocking region overlaps the associated decomposed net shape in a direction orthogonal to a longitudinal axis of the plurality of tracks by a value associated with a track pitch constraint of the double patterning layer.

### Claim 20 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the two colors include a first color and a second color different from the first color, wherein the plurality of tracks are each sequentially numbered and include a plurality of even numbered tracks and a plurality of odd numbered tracks, wherein the instructions further cause the computer to:
assign the first color to the plurality of even numbered tracks; and
assign the second color to the plurality of odd numbered tracks, thereby operative to assign any immediately adjacent tracks of the plurality of tracks to alternating different colors, when immediately adjacent tracks are not previously assigned to alternating different colors.

### Claim 21 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the
graph is characterized by having:
a plurality of vertices each associated with a different one of the plurality of net shapes; and
a plurality of edges each joining a pair of the plurality of vertices when an immediately adjacent pair of the plurality of net shapes associated with the pair of the plurality of vertices are constrained by the spacing constraint of the double patterning layer, the instructions further causing the computer to:
select a selected one of the plurality of net shapes in accordance with a minimum width constraint of the double patterning layer, wherein the selected net shape is disposed along one of the plurality of tracks;
designate one of the plurality of vertices associated with the selected net shape to the color of the two colors that is associated with the color of the track upon which the selected net shape is disposed along;
decompose the plurality of vertices in the graph into the two colors in accordance with the designated one of the plurality of vertices; and
assign the two colors to the plurality of net shapes in accordance with the decomposed graph.