由於下個世代的微影技術發展嚴重落後，多重圖案微影技術被視為最有展望能突破20 奈米限制的技術。自動對準多圖案微影技術(self-aligned multiple patterning)透過間隙壁(spacer)的保護，儘管在擷取光罩和核心光罩之間無法精確對準也不影響最終的佈局結果，因此特別適用於一維線路的製作。然而，利用傳統光學微影技術進行複雜度極高的擷取步驟將使擷取圖案嚴重失真。本論文第一個考慮雙微影蝕刻雙圖案微影技術(litho-etch-litho-etch double patterning lithography)應用於擷取光罩製造上的研究。給定一繞線佈局，我們首先利用深度優先搜尋演算法(depth first search)辨別所有的擷取圖案。為解決雙微影蝕刻雙圖案微影技術在擷取圖案上的奇數環狀衝突(odd cycle)，利用縫合(stitch)以增進擷取佈局的可分解性是必要的。不同於現有應用於線路之縫合辨別演算法，因擷取圖案上可同時存在水平與垂直縫合，縫合辨別將更為複雜。我們提出一系統性縫合辨別流程有效的找出合法的水平與垂直後選縫合位置。需要注意的是垂直縫合可能會損壞圖案的可印刷性，所以除非水平縫合無法解決該衝突，我們才會嘗試垂直的縫合。根據擷取圖案區塊彼此之間的衝突關係和候選縫合位置，我們建立了一擷取圖案衝突圖。根據此衝突圖，我們提出了一個考慮著色平衡的整數線性規劃演算法(Integer Linear Programming)找出一佈局分解結果並同時令著色衝突和縫合數目最小畫。實驗結果證明該演算法能有效的減少擷取光罩規範違反數量，以增進擷取光罩的可製造性。

Due to the delay of next generation lithography technologies, multiple patterning lithography technologies are still regarded as one of the most promising solutions for sub-20nm technology nodes. In self-aligned multiple patterning lithography, the misalignment between the trim mask and the mandrel mask does not a affect the printed target pattern due to the protection of spacers. Therefore, one-dimensional (1-D) wire layout structure will be more suitable to fabricate. However,the severe pattern distortion increases due to the complicated trim patterns are limited by the resolution of conventional optical lithography. In this thesis, we propose the first work that adopts litho-etch-litho-etch double patterning lithography(LELE-DPL) for the trim process. First, the depth first search algorithm will be adopted to find all the trim patterns in a given routing layout. In order to resolve an odd cycle, which is formed to the trim patterns for litho-etch-litho-etch double pattern-
ing lithography, the stitch is introduced to increase layout decomposition. Unlike the stitch finding algorithm has been used recently, the sophistic stitch could insert in both vertical and horizontal directions on trim patterns. Then, we propose a systematic flow to find both vertical and horizontal stitch locations without violation. Note that the rounding errors of wire segments cut by a vertical stitch could damage pattern printability, so only if horizontal stitches cannot resolve a conflict, we will try to insert a vertical stitch. Based on the conflict between each trim patterns and
the location of stitch candidates, the conflict for the trim process is constructed. According to the conflict graph, we propose an integer linear programming(ILP) formulation with color balancing consideration to simultaneously minimize coloring conflicts and inserted stitches. Experimental results demonstrate the effectiveness of the illegal trim patterns reduction and increases the trim patterns fabrication.

[1] B. Yu, and D.Z. Pan "Layout decomposition for quadruple patterning lithography and beyond," in Proceedings of ACM/EDAC/IEEE Design Automation
Conference (DAC) , pp. 1-6, 2014.
[2] S. Natori, S. Yamauchi, A. Hara, M. Yamato, and H. Yaegashi, "Innovative
solutions on 193 immersion-based self-aligned multiple patterning," in Proceedings of SPIE, vol. 9051, pp. 90511E, 2014.
[3] J. Yu, W. Xiao, W. Kang, and Y. Chen "Understanding the critical challenges of self-aligned octuple patterning," in Proceedings of SPIE, vol. 9052, pp. 90521P, 2014.
[4] C. Kodama, H. Ichikawa, K. Nakayama, T. Kotani, S. Nojima, S. Mimotogi,
and A. Takahashi, "Self-aligned double and quadruple patterning-aware grid
routing with hotspots control," in Proceedings of Asia and South Pacific Design
Automation Conference (ASP-DAC), pp. 267-272,2013.
[5] F. Nakajima, C. Kodama, H. Ichikawa, K. Nakayama, S. Nojima, and T. Kotani,
Self-aligned quadruple patterning-aware routing, in Proceedings of SPIE, vol.
9053, pp. 90530C, 2014.
[6] L. Liebmann, L. Pileggi, J. Hibbeler, V. Rovner, T. Jhaveri, and G. Northrop, "Simplify to survive, prescriptive layouts ensure pro table scaling to 32nm and beyond," in Proceedings of SPIE, vol. 7275, pp. 72750A, 2009.
[7] S.-Y. Fan,Y.-W. Chang, and W.-Y. Chen, "A novel layout decomposition algorithm for triple patterning lithography," in Proceedings of ACM/EDAC/IEEE
Design Automation Conference (DAC) , pp. 1181-1186, 2012.
[8] S.-Y. Fang, S.-Y Chen, and Y.-W. Chang, "Native-Conflict and Stitch-Aware
Wire Perturbation for Double Patterning Technology," in Proceedings of IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems ,
pp. 703-716, 2012.
[9] R.S. Ghaida, K.B. Agarwal, S.R. Nassif, X. Yuan, L.W. Liebmann, and
P. Gupta, "O(n) layout-coloring for multiple-patterning lithography and
conflict-removal using compaction," in Proceedings of IEEE International Conference on IC Design and Technology (ICICDT) , pp. 1-4, 2012.
[10] Y. Du, H. Zhang, M.D.F. Wong, and K.-Y. Chao, "Hybrid lithography optimization with E-Beam and immersion processes for 16nm 1D gridded design,"
in Proceedings of Asia and South Pacific Design Automation Conference (ASP-
DAC), pp. 707-712, 2012.
[11] S.-Y. Fang, "Cut mask optimization with wire planning in self-aligned multiple patterning full-chip routing," in Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 396-401, 2015.
[12] B. Yu, Y.-H. Lin, G. Luk-Pat, D. Ding, K. Lucas, and D.Z. Pan "A high-
performance triple patterning layout decomposer with balanced density," in
Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD) , pp. 163-169, 2013.
[13] H. Tian, H. Zhang, Q. Ma, Z. Xiao, and M.D.F. Wong, "A polynomial time
triple patterning algorithm for cell based row-structure layout," in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD) , pp. 57-64, 2012.
[14] H. Tian, H. Zhang, Q. Ma, and M.D.F. Wong, "Color balancing for triple patterning lithography with complex designs," in Proceedings of SPIE , vol. 8880, 2013.
[15] K. Lucas, C. Cork, B. Yu, G. Luk-Pat, B. Painter, and D.Z. Pan. "Implications of triple patterning for 14 nm node design and patterning," in Proceedings of SPIE , vol. 8327, 2012.
[16] J.-S. Yang, K. Lu, M. Cho, K. Yuan, and D.Z. Pan. "A new graph-theoretic,
multi-objective layout decomposition framework for double patterning lithography," in Asia and South Pacific Design Automation Conference (ASP-DAC)
, pp. 637-644, 2010.
[17] Z. Chen, H. Yao, Y. Cai "SUALD:Spacing uniformity-aware layout decomposition in triple patterning lithography," in International Symposium on Quality Electronic Design (ISQED) , pp. 566-572, 2013.
[18] L.W. Liebmann "Resolution enhancement techniques in optical lithography:
It's not just a mask problem," in Proceedings of SPIE , vol. 4409, 2001.
[19] A.B. Kahng, C.H. Park, X. Xu, and H. Yao, "Layout decomposition for double
patterning lithography," in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD) , pp. 465-472, 2008.
[20] A.B. Kahng, C.H. Park, X. Xu, and H. Yao, "Layout decomposition for double
patterning lithography," in Proceedings of IEEE Transactions on Computer-
Aided Design of Integrated Circuits and Systems , pp. 939-952, 2010.
[21] Y. Xu, and C. Chu, A matching based decomposer for double patterning
lithography, in Proceedings of ACM International Symposium on Physical De-
sign (ISPD) , pp. 121 126, 2010.
[22] H. Yao, Y. Cai, and W. Zhao, "A matching based decomposer for double
patterning lithography," in Proceedings of IEEE International Conference on
Solid-State and Integrated Circuit Technology (ICSICT) , pp. 1-4, 2012.
[23] K. Yuan, J.-S. Yang, and D. Pan, "Double patterning layout decomposition
for simultaneous conflict and stitch minimization," in Proceedings of IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems
, pp. 185-196, 2010.
[24] I.-J. Liu, S.-Y. Fang, and Y.-W. Chang, "Overlay-aware detailed routing for self-aligned double patterning lithography using the cut process," Proc. DAC, pp. 1-6, 2014.
[25] 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.
[26] Z. Xiao, Y. Du,H. Zhang, and M.D.F. Wong, "A polynomial time exact algo-
rithm for self-aligned double patterning layout decomposition," in Proceedings
of ACM international symposium on International Symposium on Physical De-
sign, pp. 17-24, 2012.