多圖樣微影技術(Multiple patterning lithography)已成為一種改善製程節點的有效技術。為了進一步地將製程節點減少至14奈米以下，使用了三個不同的光罩於三次獨立曝光的三圖樣微影技術(Triple patterning lithography)被提出。要應用三圖樣微影技術必須解決三圖樣佈局分割(Triple patterning decomposition)問題，也就是如何分散佈局圖樣(Layout patterns)至三個光罩上。由於分割問題的高度複雜性，如何在繞線階段考慮三圖樣微影成為一個主要的挑戰。另一方面，縫合(Stitch)，也就是被分解的圖樣接合的地方，會由於重疊誤差而導致產率的損失。因此在分解過程中應盡量減少縫合數。為了徹底消除縫合的重疊錯誤，我們著重於無縫合三圖樣微影感知繞線(Non-stitch triple-patterning-aware routing)，也就是繞線中不允許縫合的產生。在這篇論文中，我們觀察到相關最先進的三圖樣微影感知繞線研究在延伸至無縫合繞線時可能產生自我交錯線路(Self-crossing net)。而且他們的演算法可能會由於連續的顏色決定而降低性能。要解決這些問題，我們提出一個不會在繞線中產生自我交錯線路的圖模型，並使用修改後的加權衝突圖來考慮整體的著色。在所提出的圖模型與加權衝突圖的基礎上，我們提出第一個無縫合三圖樣微影的繞線演算法，其中包括兩個主要階段：（1）衝突圖預先著色(Conflict graph pre-coloring)和（2）基於預先著色結果的無縫合繞線(Pre-coloring-based non-stitch routing)。衝突圖預先著色是於繞線之前基於加權衝突圖來決定顏色的程序。基於預先著色結果的無縫合繞線即是在無縫合繞線時加上預先著色的結果。實驗結果表明，與延伸的最先進研究相比，我們的繞線演算法可以有效率地達到無顏色衝突且無縫合的繞線結果。

Multiple patterning lithography has become a promising technology to enhance the feature density of advanced process nodes. For sub-14 nanometer technologies and below, triple patterning lithography that uses three different photomasks for three separate exposures is required. To apply the triple patterning technology, the triple patterning layout decomposition problem has to be solved, which decomposes the layout patterns into three photomasks such that the distance between any pair of patterns on a mask is larger than a threshold value, the minimum coloring spacing. Because of the high complexity of the decomposition problem and the low decomposability of an arbitrary layout, considering the decomposition constraints during the routing stage becomes a critical step for realizing triple patterning lithography. In addition, stitches, where the split mask patterns combine, may cause yield loss because of the overlay errors among different masks. Thus, the number of stitches should be minimized during decomposition. In order to completely avoid stitch-induced yield loss, we focus on the non-stitch triple patterning-aware routing problem, where stitch insertion is not allowed. In this thesis, we first observe that directly extending the algorithms of a state-of-the-art triple patterning-aware routing work to non-stitch routing may generate self-crossing nets. Furthermore, their algorithms may degrade performance due to sequential color decision. To resolve these problems, we propose a graph model not producing self-crossing nets during routing and use a weighted conflict graph to globally consider the net coloring. Base on the model and the weighted conflict graph, we propose the first non-stitch triple patterning-aware routing scheme, which consists of two main stages: (1) conflict graph pre-coloring followed by (2) pre-coloring-based non-stitch routing. Conflict graph pre-coloring is a process that decides the colors of nets by considering the weighted conflict graph before routing. Pre-coloring-based non-stitch routing is a process that routes the nets without inserting stitches based on the pre-coloring result from the first stage. Compared with the extended algorithms of the state-of-the-art work, the experimental results show that our routing scheme can efficiently generate routing results without any stitch and coloring conflict for the generated benchmarks.

Acknowledgements iii
Abstract (Chinese) iv
Abstract vi
List of Tables x
List of Figures xi
Chapter 1. Introduction 1
1.1 Multiple Patterning Lithography . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Multiple Patterning-aware Routing . . . . . . . . . . . . . . . . . . . . . 4
1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Multiple Patterning Decomposition Related Work . . . . . . . . . 8
1.3.2 Multiple Patterning-aware Routing Related Work . . . . . . . . . 9
1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapter 2. Preliminaries 16
2.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 Con ict Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Pre-coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.3 Pre-coloring-based Triple Patterning-aware Non-stitch Routing . . 20
2.2 Routing Graph Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Chapter 3. The Non-stitch Triple Patterning-aware Routing Algo-
rithm 26
3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Potential Color Di erence Estimation and Con ict Graph Construction . 28
3.2.1 Global-routing-based Potential Color Di erence Estimation . . . . 29
3.2.2 Con ict Graph Construction . . . . . . . . . . . . . . . . . . . . . 30
3.3 Con ict Graph Pre-coloring Algorithm . . . . . . . . . . . . . . . . . . . 32
3.4 Pre-coloring-based Non-stitch Routing Algorithm . . . . . . . . . . . . . 34
3.5 Feedback Pre-coloring-based Non-stitch Routing Scheme . . . . . . . . . 37
Chapter 4. Experimental Results 41
4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Experimental Results and Comparison . . . . . . . . . . . . . . . . . . . 42
Chapter 5. Conclusions and Future Work 53
Bibliography 56

[1] Y.-J. Chang, Y.-T. Lee, and T.-C. Wang. NTHU-Route 2.0: a fast and stable global router. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 338 343. IEEE, 2008.
[2] M. Cho, Y. Ban, and D. Z. Pan. Double patterning technology friendly detailed routing. In Proceedings of IEEE/ACM International Conference on Computer Aided Design, pages 506 511. IEEE, 2008.
[3] M. Cho and D. Z. Pan. BoxRouter: a new global router based on box expansion and progressive ilp. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(12):2130 2143, 2007.
[4] C. Cork, J.-C. Madre, and L. Barnes. Comparison of triple-patterning decomposition algorithms using aperiodic tiling patterns. In Photomask and NGL Mask Technology XV, pages 702839 702839. International Society for Optics
and Photonics, 2008.
[5] K.-R. Dai, C.-H. Lu, and Y.-L. Li. GRPlacer: Improving routability and wirelength of global routing with circuit replacement. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 351 356. ACM,
2009.
[6] S.-Y. Fang, Y.-W. Chang, and W.-Y. Chen. A novel layout decomposition algorithm for triple patterning lithography. In Proceedings of ACM/IEEE Design Automation Conference, pages 1185 1190. ACM, 2012.
[7] S.-Y. Fang, S.-Y. Chen, and Y.-W. Chang. Native-con ict and stitch-aware wire perturbation for double patterning technology. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(5):703 716,
2012.
[8] J. Finders, M. Dusa, B. Vleeming, H. Megens, B. Hepp, M. Maenhoudt, S. Cheng, and T. Vandeweyer. Double patterning for 32nm and below: an update. In Advanced Lithography, pages 692408 692408. International Society
for Optics and Photonics, 2008.
[9] A. Frieze and M. Jerrum. Improved approximation algorithms for maxk-cut and max bisection. Algorithmica, 18(1):67 81, 1997.
[10] X. Gao and L. Macchiarulo. Enhancing double-patterning detailed routing with lazy coloring and within-path con ict avoidance. In Proceedings of ACM/IEEE Design, Automation and Test in Europe, pages 1279 1284. European Design
and Automation Association, 2010.
[11] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simpli ed NP-complete problems. In Proceedings of ACM Symposium on Theory of Computing, pages 47 63. ACM, 1974.
[12] D. R. Gaur, R. Krishnamurti, and R. Kohli. The capacitated max k-cut problem. Mathematical Programming, 115(1):65 72, 2008.
[13] R. S. Ghaida, K. B. Agarwal, S. R. Nassif, X. Yuan, L. W. Liebmann, and P. Gupta. Layout decomposition and legalization for double-patterning technology. IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, 32(2):202 215, 2013.
[14] M. X. Goemans and D. Williamson. Approximation algorithms for MAX-3-CUT and other problems via complex semide nite programming. In Proceedings of ACM Symposium on Theory of Computing, pages 443 452. ACM, 2001.
[15] X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. F. Young. Ripple: an e ective routability-driven placer by iterative cell movement. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 74 79. IEEE Press, 2010.
[16] M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang. Routability-driven analytical placement for mixed-size circuit designs. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 80 84. IEEE Press,
2010.
[17] J. Hu, J. A. Roy, and I. L. Markov. Completing high-quality global routes. In Proceedings of ACM International Symposium on Physical Design, pages 35 41.
ACM, 2010.
[18] ITRS. International technology roadmap for semiconductors, lithography, 2012.
[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, pages 465 472. IEEE Press, 2008.
[20] A. B. Kahng, C.-H. Park, X. Xu, and H. Yao. Layout decomposition approaches for double patterning lithography. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 29(6):939 952, 2010.
[21] M.-C. Kim, J. Hu, D.-J. Lee, and I. L. Markov. A SimPLR method for routability-driven placement. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 67 73. IEEE, 2011.
[22] J. Kuang and E. F. Young. An e cient layout decomposition approach for triple patterning lithography. In Proceedings of ACM/IEEE Design Automation Conference, page 69. ACM, 2013.
[23] Y.-L. Li, H.-Y. Chen, and C.-T. Lin. NEMO: A new implicit-connection-graph-based gridless router with multilayer planes and pseudo tile propagation. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(4):705 718, 2007.
[24] Y.-H. Lin and Y.-L. Li. Double patterning lithography aware gridless detailed routing with innovative con ict graph. In Proceedings of ACM/IEEE Design Automation Conference, pages 398 403. ACM, 2010.
[25] Y.-H. Lin, B. Yu, D. Z. Pan, and Y.-L. Li. TRIAD: A triple patterning lithography aware detailed router. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 123 129. IEEE, 2012.
[26] A.-f. Ling. A VNS metaheuristic with stochastic steps for max 3-cut and max 3-section. Mathematical Problems in Engineering, 2012, 2012.
[27] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao. Multi-threaded collision-aware global routing with bounded-length maze routing. In Proceedings of ACM/IEEE Design Automation Conference, pages 200 205. ACM, 2010.
[28] W.-H. Liu, Y.-L. Li, and C.-K. Koh. A fast maze-free routing congestion estimator with hybrid unilateral monotonic routing. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 713 719. ACM,
2012.
[29] W.-H. Liu, Y. Wei, C. Sze, C. J. Alpert, Z. Li, Y.-L. Li, and N. Viswanathan. Routing congestion estimation with real design constraints. In Proceedings of ACM/IEEE Design Automation Conference, page 92. ACM, 2013.
[30] J. Lou, S. Thakur, S. Krishnamoorthy, and H. S. Sheng. Estimating routing congestion using probabilistic analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(1):32 41, 2002.
[31] K. Lucas, C. Cork, B. Yu, G. Luk-Pat, B. Painter, A. Miloslavsky, and D. Z. Pan. Triple patterning in 10nm node metal lithography. 2012.
[32] K. Lucas, C. Cork, B. Yu, G. Luk-Pat, B. Painter, and D. Z. Pan. Implications of triple patterning for 14nm node design and patterning. In Proc. SPIE, volume 8327, page 832703, 2012.
[33] Q. Ma, H. Zhang, and M. D. Wong. Triple patterning aware routing and its comparison with double patterning aware routing in 14nm technology. In Proceedings of ACM/IEEE Design Automation Conference, pages 591 596. ACM,
2012.
[34] L. McMurchie and C. Ebeling. PathFinder: a negotiation-based performance-driven router for fpgas. In Proceedings of ACM International Symposium on Field-programmable Gate Arrays, pages 111 117. ACM, 1995.
[35] M. M. Ozdal and M. D. Wong. Archer: a history-based global routing algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, 28(4):528 540, 2009.
[36] M. Pan and C. Chu. FastRoute: a step to integrate global routing into placement. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 464 471. ACM, 2006.
[37] M. Pan and C. Chu. IPR: an integrated placement and routing algorithm. In Proceedings of ACM/IEEE Design Automation Conference, pages 59 62. ACM, 2007.
[38] J. A. Roy and I. L. Markov. Seeing the forest and the trees: Steiner wirelength optimization in placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(4):632 644, 2007.
[39] J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, and I. L. Markov. CRISP: congestion reduction by iterated spreading during placement. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 357
362. IEEE, 2009.
[40] H. Shojaei, A. Davoodi, and J. T. Linderoth. Congestion analysis for global routing via integer programming. In Proceedings of IEEE/ACM International
Conference on Computer-Aided Design, pages 256 262. IEEE Press, 2010.
[41] J. Sun, Y. Lu, H. Zhou, and X. Zeng. Post-routing layer assignment for double patterning. In Proceedings of IEEE/ACM Asia and South Paci c Design Automation Conference, pages 793 798. IEEE Press, 2011.
[42] H. Tian, H. Zhang, Q. Ma, Z. Xiao, and M. D. Wong. A polynomial time triple patterning algorithm for cell based row-structure layout. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 57
64. IEEE, 2012.
[43] K. Tsota, C.-K. Koh, and V. Balakrishnan. Guiding global placement with wire density. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 212 217. IEEE Press, 2008.
[44] J. Westra, C. Bartels, and P. Groeneveld. Probabilistic congestion prediction. In Proceedings of ACM International Symposium on Physical Design, pages 204 209. ACM, 2004.
[45] Y. Xu and C. Chu. GREMA: graph reduction based e cient mask assignment for double patterning technology. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 601 606. IEEE, 2009.
[46] Y. Xu and C. Chu. A matching based decomposer for double patterning lithography. In Proceedings of ACM International Symposium on Physical Design, pages 121 126. ACM, 2010.
[47] 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 Proceedings of IEEE/ACM Asia and South Paci c Design Automation Conference, pages 637 644. IEEE, 2010.
[48] B. Yu, K. Yuan, B. Zhang, D. Ding, and D. Z. Pan. Layout decomposition for triple patterning lithography. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 1 8. IEEE, 2011.
[49] K. Yuan, K. Lu, and D. Z. Pan. Double patterning lithography friendly detailed routing with redundant via consideration. In Proceedings of ACM/IEEE Design Automation Conference, pages 63 66. IEEE, 2009.
[50] K. Yuan and D. Z. Pan. WISDOM: Wire spreading enhanced decomposition of masks in double patterning lithography. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 32 38. IEEE, 2010.
[51] K. Yuan, J.-S. Yang, and D. Z. Pan. Double patterning layout decomposition for simultaneous con ict and stitch minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 29(2):185 196, 2010.
[52] W. Zhu and C. Guo. A local search approximation algorithm for max-k-cut of graph and hypergraph. In Proceedings of IEEE International Symposium on Parallel Architectures, Algorithms and Programming, pages 236 240. IEEE,2011.