隨著製程不斷演進，基於可製造性的考量在積體電路設計的限制也變得更加大量且複雜。其中標準元件為組成電路的基礎，因此設計高品質的標準元件有助於產生更優良的電路。既有的標準元件佈局繞線演算法中廣泛使用格點式繞線，產生在格點上的金屬線段(on-grid metal)。然而，由可製造性設計規範帶來的繞線空間變小以及限制增加，不可避免必須使用一些偏離格線的金屬線段(off-grid metal)以有效爭取可用的繞線資源。本篇論文中我們提出一個可移動式格點的迷宮繞線演算法，對於標準元件可以同時兼容on-grid與off-grid的金屬線段進行繞線。實驗結果透過電路佈局驗證及設計規則驗證判斷成敗，其顯示使用可以移動式格點的繞線方法可以使15.3%的標準元件佈局由失敗改善為成功，同時在Metal 1與Metal 2有1.7% 及 11.1% 的線長改善，並改進標準元件品質。

With the advance of technology nodes, complex and huge numbers of design rules are developed to restrict integrated circuit (IC) designs under the considerations of design for manufacturability (DFM). Standard cells are the basic components of IC designs, and highly impact the quality of IC designs. Recently, grid-based routing is widely adopted in standard cell routing. However, off-grid routing is still necessary to solve design rule violations due to limited routing resource and increasing DFM restriction. In this paper we propose a maze routing algorithm with adjustable gridlines that can be on-gird and off-grid wires to complete high quality routing. The results examined by LVS and design rule check (DRC) show that proposed routing algorithm can increase success rate by 15.3%, improve Metal 1 and Metal 2 wirelength by 1.7% and 11.1%, and improve the standard cell quality.

摘要 I
ABSTRACT II
Acknowledgement III
Contents IV
圖表目錄 V
表格目錄 VII
Chapter 1. Introduction 1
Chapter 2. Preliminary 4
2.1 Cell Layout Structure 4
2.2 Problem Formulation 8
2.3 Design Rules 9
2.4 Cell Layout Synthesis Flow 10
Chapter 3. Maze Routing with Adjustable Gridlines Mechanism 11
3.1 Adjustable Routing Grid Model 13
3.2 Pin Metal Switching Strategy 21
3.3 Routing Cost Model 26
3.4 Post Maze Routing Optimization 34
Chapter 4. Experiments 35
Chapter 5. Conclusion 40
References 41

[1] F. Rubin et al, “The Lee Path Connection Algorithm,” in IEEE Transactions on Computers 100(9), pp. 907 – 914, 1974.
[2] Tejas Jhaveri et al, "Co-Optimization of Circuits, Layout and Lithography for Predictive Technology Scaling Beyond Gratings," in IEEE Trans. CAD, vol. 29, Issue 4, pp. 509-527, 2010.
[3] Kaushik Vaidyanathan et al, "Sub-20 nm Design Technology Co-Optimization for Standard Cell Logic," in IEEE/ACM ICCAD, 2014.
[4] Nikolai Ryzhenko et al, "Physical Synthesis onto a Layout Fabric with Regular Diffusion and Polysilicon Geometries," in Proc. of the 48th ACM/IEEE DAC, 2011.
[5] Charles J. Poirier, “Excellerator: Custom CMOS Leaf Cell Layout Generator,” in IEEE Trans. CAD, vol. 8, Issue 7, pp. 744-755, 1989.
[6] Mohan Guruswamy et al, "CELLERITY: A Fully Automatic Layout Synthesis System for Standard Cell Libraries," in Proc. of the 34th DAC, pp. 327-332, 1997.
[7] N. Ryzhenko et al, “Standard Cell Routing via Boolean Satisfiability,” in Proc. of the 48th ACM/IEEE DAC, pp. 603-612, 2012.
[8] Stefan Hougardy et al, "BonnCell: Automatic Layout of Leaf Cells," in Proc. of the 18th ASP-DAC, pp. 453-460, 2013.
[9] J. Cortadella et al, "A Boolean Rule-Based Approach for Manufacturability-Aware Cell Routing," in IEEE Trans. CAD, vol. 33, Issue 3, pp. 409-422, 2014.
[10] K. Vaidyanathan et al, "Sub-20 nm Design Technology Co-Optimization for Standard Cell Logic," in IEEE/ACM ICCAD, pp. 124-131, 2014.
[11] Hsueh-Ju Lu et al, “Practical ILP-Based Routing of Standard Cells,” in Proc. of IEEE DATE, pp. 245-248, 2016.
[12] Wei, Ying-Chi et al, “Detailed Routing Considering Dynamic End-End Spacing Rules for Advanced Technology Nodes”, master thesis, NCTU EDA Laboratory, 2017.
[13] Hong-Yan Su et al., "Pin Accessibility Evaluating Model for Improving Routability of VLSI Designs," In proc. of IEEE SOCC, 2017.
[14] Xu, Xiaoqing, et al. "PARR: Pin-Access Planning and Regular Routing for Self-Aligned Double Patterning." ACM TODAES, vol. 21, Issue 3, pp. 42, 2016.
[15] Li, Yih-Lang et al. "NEMO: A new implicit-connection-graph-based gridless router with multilayer planes and pseudo tile propagation." IEEE Trans. CAD, pp. 705-718, 2007.
[16] M. Sato et al, “A fast line-search method based on a tile plane,” in Proc. IEEE Trans. CAD, pp. 588–591, 1987.
[17] A. Margarino et al, “A tile-expansion router,” IEEE Trans. CAD, vol. CAD-6, no. 4, pp. 507–517, 1987.
[18] C.-C. Tsai et al, “An H–V alternating router,” Trans. CAD, vol. 11, no. 8, pp. 976–991, 1992.
[19] J. Dion et al, “Contour: A tile-based gridless router,” Digital, Western Research Laboratory, 1995.
[20] H.-P. Tseng et al, “A gridless multilayer router for standard cell circuits using CTM cells,” IEEE Trans. CAD, vol. 18, no. 10, pp. 1462–1479, Oct. 1999.
[21] A. Hetzel et al, “A sequential detailed router for huge grid graphs,” in Proc. IEEE Des. Autom. Test Eur., pp. 332–338, 1998.
[22] J. Cong et al, “An implicit connection graph maze routing algorithm for ECO routing,” in Proc. Int. Conf. Comput.-Aided Des., pp. 163–167, 1999.
[23] J. Cong et al, “DUNE: A multilayer gridless routing system,” IEEE Trans. CAD, vol. 20, no. 5, pp. 633–646, 2001.