由於下一代微影技術的延遲，對於現今10 奈米的製程節點，多
圖樣微影技術仍然是突破微影極限的主要方案。在本篇論文中，我們
提出一個保證連通層可分解性之三圖樣微影感知的細部繞線器。在此
研究中，繞線器並不同時執行繞線和電路圖案著色以讓提供最大的繞
線彈性。為了保證佈局可分解性，我們證明在衝突圖中只避免K4 的
產生是不夠的。因此在我們的繞線流程中，我們利用同構圖的概念，
建構一個不可被三著色圖庫。由於這個同構圖演算法的高複雜性，我
們使用多種圖形簡化技術和提出平面分割方法，以加速繞線執行時間。
最後使用以整數線性規畫為基礎的佈局分解演算法，來證明我們的繞
線器可保證佈局可分解。實驗結果驗證了我們所提出的繞線演算法的
必要性和有效性。

For sub-10 nanometer technology nodes, multiple patterning technologies are still the major solutions for pushing the limit of lithography due to the delay of next generation lithography technologies. In this thesis, we propose a triple patterning lithography (TPL)-aware router that guarantees the layout decomposability of via layers. In the research, the router does not perform simultaneous routing and coloring to maximize routing flexibility. To guarantee layout decomposability, we show that considering $K4$ forbidance in the conflict graph alone is not sufficient. We therefore adopt the idea of graph isomorphism and construct a 3-uncolorable graph library in our routing flow. To tackle the high complexity of the graph isomorphism algorithm, we use several graph reduction techniques and propose a via plane division method to minimize the runtime overhead. Finally, an optimal integer linear programming (ILP)-based layout decomposition algorithm is used to show that layout decomposability is ensured by our router. Experimental results show the necessity and effectiveness of our router.

[1] 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, pp.506-511, 2008.
[2] 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, pp.702839-702839, 2008.
[3] S.-Y. Fang, Y.-W. Chang, and W.-Y. Chen. A novel layout decomposition algorithm for triple patterning lithography. Proceedings of ACM/IEEE Design Automation Conference, pp.1185-1190, 2012.
[4] S.-Y. Fang, S.-Y. Chen, and Y.-W. Chang. Native-conflict and stitch-aware wire perturbation for double patterning technology. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.703--716, 2012.
[5] 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, pp.692408--692408, 2008.
[6] 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. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.202--215, 2013.
[7] P. Y. Hsu, and Y. W Chang. Non-stitch triple patterning-aware routing based on conflict graph pre-coloring. In Asia and South Pacific Design Automation Conference, pp.390--395, 2015.
[8] C.-C.~Huang, H.-Y.~Lee, B.-Q.~Lin, S.-W.~Yang, C.-H.~Chang, S.-T.~Chen, and Y.-W.~Chang, Detailed-routability-driven analytical placement for mixed-size designs with technology and region constraints, In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.508--513, 2015.
[9] 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 , pp.465--472, 2008.
[10] 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, pp.939--952, 2010.
[11] J. Kuang and E. F. Young. An efficient layout decomposition approach for triple patterning lithography. In Proceedings of ACM/IEEE Design Automation Conference, pp.69, 2013.
[12] 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, pp.123--129, 2012.
[13] Z. Liu, C. Liu, and F. Y. Young. An effective triple patterning aware grid-based detailed routing approach. In Automation Test in Europe Conference Exhibition (DATE) , pp.1641--1646, 2015.
[14] 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.
[15] 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, vol.8327, pp.832703, 2012.
[16] 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, pp.591--596, 2012.
[17] R. F. Pease and S. Y. Chou. Lithography and other patterning techniques for future electronics. In Proceedings of IEEE, pp.~248–-270, 2008.
[18] B. W. Smith, Y. Fan, M. Slocum, and L. Zavyalova. 25nm Immersion Lithography at a 193nm Wavelength. In Proc. SPIE, pp.141--147, 2005.
[19] 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, pp.57--64, 2012.
[20] Y. Xu and C. Chu. A matching based decomposer for double patterning lithography. In Proceedings of ACM International Symposium on Physical Design, pp.121--126, 2010.
[21] Y. Xu and C. Chu. GREMA: graph reduction based efficient mask assignment for double patterning technology. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.601--606, 2009.
[22] 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 Pacific Design Automation Conference, pp.637--644, 2010.
[23] 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, pp.1--8, 2011.
[24] 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, pp.63--66, 2009.
[25] K. Yuan, J.-S. Yang, and D. Z. Pan. Double patterning layout decomposition for simultaneous conflict and stitch minimization. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.8323, pp.~185--196, 2010.
[26] IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[27] Cadence SoC Encounter. http://www.cadence.com/
[28] I.~S.~Bustany, D.~Chinnery, J.~R.~Shinnerl, and V.~Yutsis, 2015 benchmarks with fence regions and routing blockages for detailed-routing-driven placement, in Proceedings of ACM International Symposium on Physical Design, pp.157--164, 2015.
[29] International Technology Roadmap for Semiconductors (ITRS). http://www.itrs.net/
[30] The Graph Isomorphism Algorithm. http://www.dharwadker.org/tevet/isomorphism/