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.
N1 - Funding Information:
This work was partially supported by the National Science Foundation under grant CCF-1017516 and a grant from the semiconductor Research Corporation (SRC).
Publisher copyright:
© 2012 ACM
PY - 2012/3/25
Y1 - 2012/3/25
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
U2 - 10.1145/2160916.2160922
DO - 10.1145/2160916.2160922
M3 - Conference proceeding
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
A2 - Hu, Jiang
PB - Association for Computing Machinery (ACM)
T2 - 2012 ACM International Symposium on Physical Design, ISPD'12
Y2 - 25 March 2012 through 28 May 2012
ER -