A polynomial time exact algorithm for self-aligned double patterning layout decomposition

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, 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 14nm. 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 few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. 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)
Title of host publicationISPD'12 - Proceedings of the 2012 International Symposium on Physical Design
Pages17-24
Number of pages8
DOIs
StatePublished - May 1 2012
Event2012 ACM International Symposium on Physical Design, ISPD'12 - Napa, CA, United States
Duration: Mar 25 2012May 28 2012

Publication series

NameProceedings of the International Symposium on Physical Design

Other

Other2012 ACM International Symposium on Physical Design, ISPD'12
CountryUnited States
CityNapa, CA
Period3/25/125/28/12

Fingerprint

Lithography
Polynomials
Decomposition
Inductive logic programming (ILP)

Keywords

  • Layout decomposition
  • Polynomial time algorithm
  • Self-aligned double patterning

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Xiao, Z., Du, Y., Zhang, H., & Wong, M. D. F. (2012). A polynomial time exact algorithm for self-aligned double patterning layout decomposition. In ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design (pp. 17-24). (Proceedings of the International Symposium on Physical Design). https://doi.org/10.1145/2160916.2160922

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

ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design. 2012. p. 17-24 (Proceedings of the International Symposium on Physical Design).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Xiao, Z, Du, Y, Zhang, H & Wong, MDF 2012, A polynomial time exact algorithm for self-aligned double patterning layout decomposition. in ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design. Proceedings of the International Symposium on Physical Design, pp. 17-24, 2012 ACM International Symposium on Physical Design, ISPD'12, Napa, CA, United States, 3/25/12. https://doi.org/10.1145/2160916.2160922
Xiao Z, Du Y, Zhang H, Wong MDF. A polynomial time exact algorithm for self-aligned double patterning layout decomposition. In ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design. 2012. p. 17-24. (Proceedings of the International Symposium on Physical Design). https://doi.org/10.1145/2160916.2160922
Xiao, Zigang ; Du, Yuelin ; Zhang, Hongbo ; Wong, Martin D F. / A polynomial time exact algorithm for self-aligned double patterning layout decomposition. ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design. 2012. pp. 17-24 (Proceedings of the International Symposium on Physical Design).
@inproceedings{cd0dd37c45f341c3ae4e1c331d3d62eb,
title = "A polynomial time exact algorithm for self-aligned double patterning layout decomposition",
abstract = "Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, 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 14nm. 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 few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. 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 = "Layout decomposition, Polynomial time algorithm, Self-aligned double patterning",
author = "Zigang Xiao and Yuelin Du and Hongbo Zhang and Wong, {Martin D F}",
year = "2012",
month = "5",
day = "1",
doi = "10.1145/2160916.2160922",
language = "English (US)",
isbn = "9781450311670",
series = "Proceedings of the International Symposium on Physical Design",
pages = "17--24",
booktitle = "ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design",

}

TY - GEN

T1 - A polynomial time exact algorithm for self-aligned double patterning layout decomposition

AU - Xiao, Zigang

AU - Du, Yuelin

AU - Zhang, Hongbo

AU - Wong, Martin D F

PY - 2012/5/1

Y1 - 2012/5/1

N2 - Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, 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 14nm. 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 few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. 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-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, 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 14nm. 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 few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. 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 - Layout decomposition

KW - Polynomial time algorithm

KW - Self-aligned double patterning

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

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

U2 - 10.1145/2160916.2160922

DO - 10.1145/2160916.2160922

M3 - Conference contribution

AN - SCOPUS:84860235851

SN - 9781450311670

T3 - Proceedings of the International Symposium on Physical Design

SP - 17

EP - 24

BT - ISPD'12 - Proceedings of the 2012 International Symposium on Physical Design

ER -