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.
N1 - Funding Information:
This work was supported in part by the National Science Foundation under Grant CCF-1017516 and a grant from the Semiconductor Research Corporation.
Publisher Copyright:
© 2013 IEEE
PY - 2013/8
Y1 - 2013/8
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
U2 - 10.1109/TCAD.2013.2252054
DO - 10.1109/TCAD.2013.2252054
M3 - Journal article
SN - 0278-0070
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
IS - 8
M1 - 6558884
ER -
