A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition

Zigang Xiao, Yuelin Du, Hongbo Zhang, Martin D.F. Wong

Research output: Contribution to journalArticle

Abstract

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

Original languageEnglish (US)
Article number6558884
Pages (from-to)1228-1239
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume32
Issue number8
DOIs
StatePublished - Aug 5 2013

Fingerprint

Lithography
Polynomials
Decomposition
Inductive logic programming (ILP)

Keywords

  • Computer-aided design
  • design for manufacturability
  • electronic design automation
  • layout decomposition
  • polynomial time algorithm
  • self-aligned double patterning

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition. / Xiao, Zigang; Du, Yuelin; Zhang, Hongbo; Wong, Martin D.F.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 32, No. 8, 6558884, 05.08.2013, p. 1228-1239.

Research output: Contribution to journalArticle

@article{30117ba361e8464fa42a48c449bda3cf,
title = "A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition",
abstract = "Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.",
keywords = "Computer-aided design, design for manufacturability, electronic design automation, layout decomposition, polynomial time algorithm, self-aligned double patterning",
author = "Zigang Xiao and Yuelin Du and Hongbo Zhang and Wong, {Martin D.F.}",
year = "2013",
month = "8",
day = "5",
doi = "10.1109/TCAD.2013.2252054",
language = "English (US)",
volume = "32",
pages = "1228--1239",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

TY - JOUR

T1 - A polynomial time exact algorithm for overlay-resistant self-aligned double patterning (SADP) layout decomposition

AU - Xiao, Zigang

AU - Du, Yuelin

AU - Zhang, Hongbo

AU - Wong, Martin D.F.

PY - 2013/8/5

Y1 - 2013/8/5

N2 - Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

AB - Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

KW - Computer-aided design

KW - design for manufacturability

KW - electronic design automation

KW - layout decomposition

KW - polynomial time algorithm

KW - self-aligned double patterning

UR - http://www.scopus.com/inward/record.url?scp=84880877800&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880877800&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2013.2252054

DO - 10.1109/TCAD.2013.2252054

M3 - Article

AN - SCOPUS:84880877800

VL - 32

SP - 1228

EP - 1239

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 8

M1 - 6558884

ER -