TY - GEN
T1 - Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time
AU - Xiao, Zigang
AU - Du, Yuelin
AU - Tian, Haitong
AU - Wong, Martin D.F.
PY - 2013
Y1 - 2013
N2 - Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.
AB - Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.
UR - http://www.scopus.com/inward/record.url?scp=84893355134&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893355134&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2013.6691094
DO - 10.1109/ICCAD.2013.6691094
M3 - Conference contribution
AN - SCOPUS:84893355134
SN - 9781479910717
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 32
EP - 39
BT - 2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers
T2 - 2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013
Y2 - 18 November 2013 through 21 November 2013
ER -