# US 8,751,974 B2 · Layout decomposition for double patterning lithography

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

- Number: US 8,751,974 B2
- Document ID: US8751974B2
- Status: Granted
- Kind: B2
- Application number: 13/766,349
- Filed: 2013-02-13
- Published: 2013-06-20
- Granted: 2014-06-10
- Earliest claimed: 2009-09-29
- Assignees: The Regents of the University of California
- Applicants: The Regents of the University of California
- Inventors: Andrew B. Kahng; Hailong Yao
- Web page: https://patentgrep.com/patent/US8751974B2

## CPC

- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G03F 1/70: Adapting basic layout or design of masks to lithographic process requirements, e.g., second iteration correction of mask patterns for imaging
- G06F 30/00: Computer-aided design [CAD]
- 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)

## Abstract

The invention provides systems and methods for layout decomposition to produce exposure layouts that can be used to perform double patterning lithography (DPL). Preferred embodiment methods of the invention are executed by a computer and provide alternate methods for layout decomposition for double patterning lithography (DPL) using integer linear programming (ILP) formulations. Embodiments of the invention meet a key optimization goals, which is to reduce the total cost of layout decomposition, considering the abovementioned aspects that contribute to cost of prior conventional DPL techniques. Embodiments of the invention provide integer linear programming (ILP), phase conflict detection (PCD) and node election bipartization (NBD) formulations for the optimization of DPL layout decomposition, with a process-aware cost function that avoids small jogging line-ends, and maximizes overlap at dividing points of polygons. The cost function can also make preferential splits at landing pads, junctions and long runs.

## Claims

### Claim 1

A layout decomposition method to produce exposure layouts for double patterning lithography from an initial layout, the method comprising steps of:
accepting an initial double patterning lithography polygonal layout;
fracturing features in the polygonal layout into a rectangular layout set of non-overlapping rectangular features;
constructing a conflict graph over the rectangular features, wherein nodes in the conflict graph identify rectangular features having conflicting edges that are less than predetermined minimum coloring spacing distance and rectangular features having touching edges;
conducting node splitting to split rectangular features identified as conflicting according to the conflict graph;
updating the conflict graph to generate new nodes;
computing overlap lengths between touching rectangular features;
conducting, by using a computer, coloring of the rectangular features to obtain a coloring solution that is a two-colorable solution for rectangles identified in the updated conflict graph, wherein said coloring minimizes a weighted sum of the number of design changes, cuts, design rule violations and overlap lengths.

### Claim 2 (depends on 1)

The layout decomposition method of claim 1, wherein said conducting conducts coloring according to:
Minimize
⁢
:
∑
⁢
y
i
,
j
·
(
β
+
γ
/
o
i
,
j
)
+
∑
⁢
λ
·
z
i
,
j
Subject
⁢
⁢
to
⁢
:
⁢
{
2
⁢
x
i
-
x
j
-
x
k
≤
1
x
j
+
x
k
-
2
⁢
x
i
≤
1
⁢
∀
e
i
,
j
t
,
e
i
,
k
t
⁢
⁢
and
⁢
⁢
l
i
<
FS
min
(
6
)
x
i
=
x
j
⁢
∀
e
i
,
j
t
⁢
⁢
and
⁢
⁢
l
i
<
FS
min
(
7
)
x
i
=
x
j
⁢
∀
e
i
,
j
t
⁢
⁢
and
⁢
⁢
o
i
,
j
<
OM
(
8
)
{
x
i
-
x
j
≤
y
i
,
j
x
j
-
x
i
≤
y
i
,
j
⁢
∀
e
i
,
j
t
⁢
⁢
and
⁢
⁢
o
i
,
j
≥
OM
(
9
)
{
x
i
+
x
j
-
1
≤
z
i
,
j
1
-
x
i
-
x
j
≤
z
i
,
j
⁢
∀
e
i
,
j
c
(
10
)
wherein xi and xj are binary variables (0/1) for the colors of rectangles ri and rj, and yi,j is a binary variable for touching edges eti,jεET, i.e., for any pair of touching rectangular features ri and rj; and
wherein li and lj are the lengths of the rectangle edges of ri and rj which are opposite to the touching edge between ri and rj, oi,j(=oj,i) is the overlap length between nodes ni and nj, and α, β, and γ are user-defined parameters to weight the different optimization objectives;
wherein FSmin is a minimum feature size;
wherein OM is a required overlap margin;
and wherein zi,j defines the relative coloring status of conflict edge eci,jεEC, such that zi,j=0 when xi≠xj, while zi,j=1 when xi≠xj.

### Claim 3 (depends on 2)

The layout decomposition method of claim 2, wherein:
in Eq (6) of claim 2, if the size of rectangle ri is less than the minimum feature size and ri touches rectangles rj and rk on two sides, then ri should be assigned the same color as one or both of rj and rk;
in Eq (7) of claim 2, if the size of rectangle ri is less than the minimum feature size and ri only touches rectangle rj, then ri is assigned the same color as rj to avoid a design rule violation;
in Eq (8) of claim 2, if the overlap length between touching rectangles ri and rj is less than the required overlap margin, then ri and rj are assigned the same color;
in Eq (9) of claim 2, when the overlap length oi,j between a pair of touching rectangles ri and rj is greater than the required overlap margin OM, a cost γ/oi,j is incurred when ri and rj are assigned different colors (xi≠xj), i.e., yi,j=1;
in Eq (10) of claim 2, a cost λ is incurred for a conflict edge eci,j if ri and rj are assigned the same color (xi=xj), i.e., zi,j=1;
wherein β, γ and λ are user-specified parameters for balancing objectives, with a larger β corresponding to more emphasis on the minimization of the number of line-ends; a larger γ corresponding to more improvement of overlap length, and a larger λ corresponding to more emphasis on the minimization of the number of design changes.

### Claim 4 (depends on 1)

The layout decomposition method of claim 1, further comprising providing the coloring solution to an optical lithography system and performing optical lithography.

### Claim 5 (depends on 1)

The layout decomposition method of claim 1, wherein said constructing and node splitting maximize overlap lengths between pairs of touching rectangles.

### Claim 6 (depends on 1)

The layout decomposition method of claim 1, wherein said constructing and node splitting minimize the number of cuts between touching rectangles assigned to different colors.

### Claim 7 (depends on 1)

The layout decomposition method of claim 1, wherein said conducting conducts coloring according to a phase conflict detection that assigns a cost to conflict edges in the conflict graph to ensure that a minimum number of conflict edges will be deleted.

### Claim 8 (depends on 7)

The layout decomposition method of claim 7, wherein a cost is assigned to touching edges in view of design rule violations and/or minimum required overlap lengths.

### Claim 9 (depends on 1)

The layout decomposition method of claim 1, wherein said conducting conducts coloring according to a node deletion bipartization, wherein new nodes are created to establish new feature edges as a substitute for touching edges and node deletion bipartization is conducted in which only new nodes can be deleted to obtain the coloring solution.

### Claim 10 (depends on 1)

The layout decomposition method of claim 1, further comprising providing the coloring solution to an optical lithography system and performing optical lithography.

### Claim 11 (depends on 1)

The layout decomposition method of claim 1, applied in a double patterning layout design system to modify a mask design layout to be used to conduct lithography, the tool being executed by a computer system and including code for conducting the method steps.