自動對準雙圖案微影技術(self-aligned double patterning lithography)是目前20奈米以下的主要微影技術之一，在微影技術的發展下，尺寸微小化使得雙圖案微影技術的光罩失真太嚴重，因此我們需要良好的演算法將一密集的佈局圖案分配到兩個獨立的光罩上並且將電路合理化。在之前的研究中幾乎都是在雙微影蝕刻雙圖案微影技術(litho-etch-litho-etch double patterning lithography)上做探討，然而在自動對準雙圖案微影技術下，針對二維佈局的佈局分解變得更為複雜，原生衝突(native conflict) 變得更難解決進而需要導線擾動(wire perturbation) 來幫助自動對準雙圖案微影技術的佈局合法化。本論文中，我們提出了一個有效減少圖形失真的導線擾動演算法，首先根據導線的形狀與長度來計算其在衝突圖的節點權重，再依據權重的大小進行佈局分解(layout decomposition)，將佈局圖案分配為核心圖案(mandrel pattern)或二次圖案(secondary pattern)，使得合法過的過程中可以有效得減少額外輔助核心圖形(assist mandrel pattern)的使用以及較易失真圖形的出現。接著使用一基於線性規劃(linear programming)的導線擾動演算法將佈局分解後的衝突合法化。實驗結果顯示我們事先多考慮導線的複雜度能夠有效的減少輔助圖形的使用以及失真圖形的數量並且最佳化導線位移與面積。

Self-aligned double patterning (SADP) is a leading lithography technology for sub-20 nm process nodes. For two-dimensional features, decomposability is hard to be guaranteed for an arbitrary layout. Overlay error problem becomes more important in layout manufacturability. And due to the lithography technologies, misalignment of mask become a critical problem in yield and circuit reliability. Therefore, SADP-aware layout legalization must be the first performed prior to realizing a design with SADP. This paper presents an efficient wire perturbation algorithm considering overlay error minimization. We first perform layout decomposition by considering pattern complexity such that the assist mandrel addition for forbidding overlay and overlay-sensitive pattern edges by trim mask can be minimized. Then, a linear programming (LP)-based wire perturbation algorithm is proposed. LP formulation resolve the design rule problem and minimize the pattern displacement, area. Experimental results show that our approach can effectively legalize layouts with less total wire displacement and fewer overlay-sensitive pattern edges.

[1] Y. Ban, K. Lucas, and D. Pan, \Flexible 2D layout decomposition framework
for spacer-type double pattering lithography," in Proceedings of ACM/IEEE
Design Automation Conference (DAC), pp. 789{794, 2011.
[2] R. S. Ghaida, K.-B. Agarwal, S.-R. Nassif, X. Yuan, L.-W. Liebmann, and
P. Gupta \Layout Decomposition and Legalization for Double-Patterning Tech-
nology," in IEEE Transactions on Computer-Aided Design of Integrated Cir-
cuits and Systems (TCAD), VOL. 32, NO. 2, FEBRUARY 2013.
[3] M. Mirsaeedi, J. A. Torres, and M. H. Anis \Litho-friendly decomposi-
tion method for self-aligned double patterning," in IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems (TCAD), VOL. 32,
NO. 2, FEBRUARY 2013.
[4] Z. Xiao, Y. Du, H. Tian, and M. D. F.Wong, \Optimally minimizing overlay vi-
olation in self-aligned double patterning decomposition for row-based satndard
cell layout in polynomial time," in Proceedings of IEEE/ACM International
Conference on Computer-Aided Design (ICCAD), pp. 32{39 2013.
[5] Y. Du, Q. Ma, H. Song, J. Shiely, G. Luk-Pat, A. Miloslavsky, and
M. D. F. Wong, \Spacer-is-dielectric-compliant detailed routing for self-aligned
double patterning lithography," in Proceedings of ACM/IEEE Design Automa-
tion Conference (DAC), pp. 1{6, 2013.
36
37
[6] Szu-Yu Chen and Yao-Wen Chang, `Native-Con
ict-Aware Wire Perturbation
for Double Patterning Technology," in Proceedings of IEEE/ACM International
Conference on Computer-Aided Design (ICCAD), pp. 556{561, 2010.
[7] S.-Y. Fang, Y.-W. Chang, and W.-Y. Chen, \A novel layout decomposition
algorithm for triple patterning lithography," in Proceedings of ACM/IEEE De-
sign Automation Conference (DAC), pp. 1181{1186, San Francisco, CA, June
2012.
[8] J.-R. Gao, B. Yu, and D. Z. Pan, \Self-aligned double patterning layout decom-
position with complementary e-beam lithography," in Proc. ASPDAC, pp. 143{
148, 2014.
[9] Y. Ban, A. Miloslavsky, K. Lucas, S.-H. Choi, C.-H. Park, and D. Z. Pan, \Lay-
out Decomposition of Self-Aligned Double Patterning for 2D Random Logic
Patterning," in Design for Manufacturability through Design-Process Integra-
tion V (SPIE), April 04, 2011.
[10] M. Mirsaeedi, J. A. Torres, and M. H. Anis, \Self-aligned double patterning
(SADP) layout decomposition" in Quality Electronic Design (ISQED), 14-16
March 2011.
[11] Y. Du, Q. Ma, H. Song, J. Shiely, G. Luk-Pat, A. Miloslavsky, and M. D.
F. Wong, \Spacer-is-dielectric-compliant detailed routing for self-aligned dou-
ble patterning lithography," in Proceedings of ACM/IEEE Design Automation
Conference (DAC), pp. 1{6, May 29 2013-June 7 2013.
[12] Z. Xiao, Y. Du, H. Zhang, and M. D. F. Wong, \A polynomial time exact
algorithm for self-aligned double patterning layout decomposition," in IEEE
38
Transactions on Computer-Aided Design of Integrated Circuits and Systems
(TCAD), pp. 1228{1239, Aug. 2013.
[13] H. Zhang, Y. Du, M. D. F. Wong, and R. Topaloglu, \Self-aligned double
patterning decomposition for overlay minimization and hot spot detection," in
Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 71{76,
2011.
[14] H. Zhang, Y. Du, M. D. F. Wong, R. Topaloglu, and W. Conley, \E ective de-
composition algorithm for self-aligned double patterning lithography," in Proc.
(SPIE), 2011.
[15] F. L. Heng, Z. Chen, and G. Tellez, \A VLSI artwork legalization technique
based on a new criteria of minimum layout perturbation," in Proc. ACM/IEEE,
pp. 116-121, Apr. 1997.
[16] X. Yuan, K. W. McCullen, F.-L. Heng, R. F. Walker, J. Hibbeler, R. J. Allen,
and R. R. Narayan, \Technology migration technique for designs with strong
RET-driven layout restrictions," in Proc. ACM/IEEE, pp. 175{182, 2005.
[17] I.-J. Liu, S.-Y. Fang, and Y.-W. Chang, \Overlay-aware detailed routing for
self-aligned double patterning lithography using the cut process," in Proceedings
of ACM/IEEE Design Automation Conference (DAC), pp. 1{6, 2014.
[18] Y. Ma, J. Sweis, H. Yoshida, Y. Wang, J. Kye, and H. J. Levinson, \Selfaligned
double patterning (SADP) compliant design
ow," in Proc. SPIE, vol. 8327.
2012,
[19] T.-B. Chiou, R. Socha, H. Chen, L. Chen, S. Hsu, P. Nikolsky, A. van Oosten,
and A. C. Chen, \Development of Layout Split Algorithms and Printability
39
Evaluation for Double Patterning Technology," in Proc. SPIE, vol. 6924, March
2008.
[20] A. van Oosten, P. Nikolsky, J. Huckabay, R. Goossens, and R. Naber. Pattern
split rules! \A feasibility study of rule based pitch decomposition for double
pat- terning," in Proc. SPIE, vol. 6730, 2007.
[21] K. Yuan and D. Z. Pan, \WISDOM: Wire spreading enhanced decomposi-
tion of masks in double patterning lithography," in IEEE/ACM International
Conference on Computer-Aided Design, vol. 8323, pp. 32{38, 2010.
[22] K. Yuan, J.-S. Yang, and D. Z. Pan, \Double patterning layout decomposi-
tion for simultaneous con ict and stitch minimization," in Proc. ACM/ISPD,
pp. 107{114, 2009.
[23] C.-H. Hsu, Y.-W. Chang, and S. R. Nassif, \Simultaneous layout migration
and decomposition for double patterning technology," in IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems(TCAD), pp. 284{
294, 2011.
[24] A.-B. Kahng, C.-H. Park, X. Xu and H. Yao, \Layout decomposition
approaches for double patterning lithography," in IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems(TCAD), pp. 939{
952, 2010.
[25] IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/
integration/optimization/cplex-optimizer/
[26] International Technology Roadmap for Semiconductors (ITRS).
http://www.itrs.net/