臺灣博碩士論文加值系統

標準元件為數位IC中所廣泛使用的基本元件，因此IC的效能大部分取決於標準元件的效能，而隨著製程演進，電子元件持續微縮，造成設計規範亦趨複雜，在複雜的設計規範限制之下，標準元件佈局圖自動化設計工具中的繞線演算法難以在繞線的同時考量到複雜的設計規範，因此如何在繞線結束後的後繞線階段有效的修正違反設計規範的標準元件成為一大挑戰。本篇論文所考慮的複雜設計規範主要特點為規範了多個物件之間的關係，因此設計規範會隨著目標物件與周圍物件的關係改變而變化，另外也同時考慮了在先進製程中常使用的雙重曝光光刻(Double Patterning Lithography)技術相關的設計規範。本篇論文將先針對基於鰭式電晶體(FinFET)架構的先進製程中常會出現的複雜設計規範以及雙重曝光光刻技術相關的設計規範加以介紹，而後對於已完成繞線但違反設計規範驗證(Design rule check, DRC)的標準元件提出一套基於整數線性規劃的後繞線優化架構，並且藉由加入冗餘的via以提升佈局圖流通的電流量進而提升標準元件的效能。根據實驗結果，經過本篇提出的後繞線優化架構之後，348顆無法通過設計規範驗證的標準元件中100%可以通過設計規範驗證。

Standard cells are basic components in digital IC designs, and they play an important role to determine the performance of a digital IC. With the continuous progresses of technology nodes, the feature size continues to shrink. Due to the design for manufacturing (DFM) considerations, the design rules become more complicated. This makes it much harder for cell routing algorithm to consider complex design rules during routing, which drastically increases the difficulty of developing automated cell layout synthesis tools. Therefore, how to effectively fix design rules in post-routing optimization stage becomes a great challenge. The complex design rules considered in this paper mainly specify the relationship among multiple objects. Along with the variety of design specification, the relationship among the target object and the surrounding objects changes. In addition, design rules related to double patterning lithography used in the advanced process are also considered simultaneously. We first introduce the complex design rules and the lithography rules, which can often be found in advanced processes of the FinFET architecture. A post-routing optimization framework based on linear integer programming are then proposed. The framework is applied to optimize the cell layouts routed without considering several common complex design rules. Furthermore, it also improves cell performance through adding redundant vias to increase the current flowing through a cell. The results examined with design rule check (DRC) show that proposed post-routing algorithm apply on 348 cells and 100% cells can obtain violation-free result.

摘要 i
ABSTRACT ii
Acknowledgement iii
Contents iv
List of Figures v
List of Tables vi
Chapter 1. Introduction 1
Chapter 2. Preliminary 3
2.1 Layout Structure 3
2.1.1 Metal 0 Layer 4
2.2 Design Rules 5
2.3 Double Patterning Lithography 9
2.4 Synthesis Flow 11
2.4 Design Challenges 13
2.6 Problem Formulation 14
Chapter 3. Methodology 15
3.1 Polygon-to-Rectangle Conversion 17
3.2 Re-Direction on Metal-0 Layer 18
3.3 MIS-Based Enclosure Type Selection 19
3.3.1 Enclosure Candidate Enumeration and Redundant Removal 20
3.3.2 Assign Cost to Each Candidate 21
3.3.3 MIS-Based Concurrent Via Enclosure-Type Selection 23
3.4 Two-Colorable DP Conflict Graph 24
3.4.1 Edge Removal 26
3.5 Wire Plowing 28
3.5.1 ILP Formulation 30
3.5.2 Horizontal Wire Plowing 35
3.5.3 Vertical Wire Plowing 36
3.6 Metal Area Expansion 40
3.7 Post-Refinement Stage 41
3.8 Redundant Diffusion Via0 Insertion 43
Chapter 4. Experiments 44
Chapter 5. Conclusion 51
References 52

[1] K. Bhanushali and W. R. Davis. FreePDK15: An Open-Source Predictive Process Design Kit for 15nm FinFET Technology. In Proc. of Int’l Symp. on Physical Design (ISPD), 2015.
[2] Martins, Mayler, et al. "Open cell library in 15nm FreePDK technology." Proceedings of the 2015 Symposium on International Symposium on Physical Design. ACM, 2015.
[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] Hsueh-Ju Lu et al, “Practical ILP-Based Routing of Standard Cells,” in Proc. of IEEE DATE, pp. 245-248, 2016.
[11] Cremer, Pascal, et al. "Automatic cell layout in the 7nm era." Proceedings of the 2017 ACM on International Symposium on Physical Design. ACM, 2017.
[12] 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.
[13] Kevin D. Gourley and Douglas M. Green, "A Polygon-to-Rectangle Conversion Algorithm," In Proc. IEEE Computer Graphics and Applications, vol. 3, issue. 1, pp. 31-36, Jan, 1983.
[14] Hong-Yan Su et al, “A Robust Standard Cell Layout Synthesis and Verification Framework for Advanced Technology Nodes”, phd thesis, NCTU EDA Laboratory, 2017.
[15] Ching-Ho Chen et al, “Standard Cell Layout Optimization Considering Complex Design Rules for Advanced Technology Nodes”, master thesis, NCTU EDA Laboratory, 2017.
[16] Wong, Le et al, “A High-Quality Maze Routing Algorithm with Adjustable Gridlines for Standard Cell Synthesis”, master thesis, NCTU EDA Laboratory, 2017.
[17] Pan, David Z., Bei Yu, and Jhih-Rong Gao. "Design for manufacturing with emerging nanolithography." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32.10 (2013): 1453-1472.
[18] F. L. Heng, Z. Chen, and G. Tellez, “A VLSI artwork legalization technique based on a new criteria of minimum layout perturbation,” in Proc. ISPD, 1997.
[19] Wei, Ying-Chi et al, “Detailed Routing Considering Dynamic End-End Spacing Rules for Advanced Technology Nodes”, master thesis, NCTU EDA Laboratory, 2017.
[20] "GNU Project", GNU Linear Programming Kit, Jan. 2017, [online] Available: https://www.gnu.org/software/glpk/.
[21] Jonathan L. Gross , Jay Yellen, Graph Theory and Its Applications, Second Edition (Discrete Mathematics and Its Applications), Chapman & Hall/CRC, 2005.
[22] C. Bencher, Y. Chen, H. Dai, et al. 22nm half-pitch patterning by CVD spacer self-alignment double patterning (SADP). In Proc. of SPIE Advanced Lithography. Int’l Soc. for Optics and Photonics, 2008.
[23] D. Hisamoto et al, "FinFET—A Self-Aligned Double-Gate MOSFET Scalable to 20 nm," in Proc. of IEEE Transactions on Electron Devices, vol. 47, Issue 12, pp. 2320-2325, 2000.