臺灣博碩士論文加值系統

標準元件為數位IC中被大量使用的基本元件，其效能將大幅的影響IC的最終效能與品質，因此，標準元件一般均經過人工盡可能最佳化以便提高效能。然而，不同IC有著不同的設計目標，例如以時序或功耗為主的設計目標，標準元件庫的優化方向自然必須隨著不同的設計目標調整。另一方面，製程演進及尺寸的微縮造成的複雜設計規範以及所衍伸而來的可製造性設計(DFM)考量讓標準元件的設計日趨複雜，也因而嚴重的增加了設計並優化標準元件時的負擔及所需時間。因此，我們需要發展標準元件佈局圖的自動化設計以簡化設計先進製程標準元件庫的負擔及所需的設計時間。
近年，為了簡化設計的負擔而提出的限縮設計規範(RDR)基於”規律性”這項主要概念來簡化所需考量的設計規範並同時維持住IC的設計品質，因此基於RDR，我們得以在設計的過程中有較多的餘裕考量可製造性設計。然而，RDR的基本概念為規律性設計，這也近一步侷限了設計時的自由度，也因此自動化設計的工具得以利用這些規律性產出足以披敵人工設計並最佳化的佈局圖，這也促進了近年來開發標準元件佈局圖的自動化工具。
在這篇論文中，我們將提出一個考量先進製程中複雜設計規範的標準元件佈局合成架構。首先，我們在電晶體排列問題中採用了基於動態規劃的方法可以同時最佳化標準元件所需的面積以及標準元件內繞線時可繞度。同時，我們也提出了類樂高的方法可以高效的解決不同電晶體摺疊形式的問題。隨後，我們提出了一個快速且精準的繞線規畫演算法，藉此精確的繞線規劃我們得以在之後的繞線中參考繞線規劃的結果快速地完成繞線、避免違反設計規範並且減少所需的繞線資源。在實驗中我們採用了業界的28奈米製程並且產生了超過1000顆的標準元件佈局圖，同時，與業界28奈米製程的標準元件庫相比，我們所產生的標準元件其效能可媲美業界的標準元件庫。另一方面，在設計標準元件庫時由於必須考量其後將被用於IC設計，標準元件的輸出入接點(IO pin)必須有利於實體設計階段的繞線，為此，我們提出了一個可準確評估標準元件輸出入接點易接觸程度(accessibility)的模型，由實驗可證實經由我們的模型評估後具有較佳的易接觸程度的標準元件其在之後的實體設計階段時也具有較佳的繞線結果，例如較短的線長。最後，我們提出了多階層(multi-layer)且完全比對(exact matching)的佈局圖形偵測架構。因此我們可在基於標準元件設計的佈局圖中搜尋是否存在對製造過程不友善的特定圖形，藉此，我們可在較早的階段計即排除此類有製造上疑慮的設計問題。

Standard cells are basic and extensively used components in digital IC designs. They are optimized manually to realize high design quality. Several standard cell libraries have been developed based on different objectives such as delay or power consumption for satisfying the associated VLSI design objectives. However, as feature sizes continue to shrink, complex design rules that arise owing to design for manufacturing (DFM) considerations complicate the design of standard cell layouts and therefore substantially increase the layout designer’s burden and hinders the design process. Automated cell layout synthesis can overcome these problems.
In recent years, restricted design rule (RDR) has been proposed to reduce the set of design rules while maintaining design quality by using the key concept of regularity. With the RDR concept, we can easily address DFM concerns in cell layout designs without sacrificing design quality. However, regularity restricts the design freedom and thus layout designers have less room for improving the layout quality; this has hastened the development of automated cell layout synthesis because regularity enables automated synthesized layouts to have similar or even better design qualities compared with manual designs and requires less design time.
In this thesis, we present a robust standard cell layout synthesis framework that considers complex design rules in advanced technology nodes. A dynamic programming–based transistor placement algorithm is proposed to simultaneously consider the cell area and the routability of within-cell routing. Then, a LEGO-like assembling method is adopted to efficiently and effectively overcome the challenge of different folding styles. Next, a fast and accurate routing planning is used to estimate the available and required routing resources and to then provide a rough routing result considering complex design rules. This routing planning can then guide the router to find a routing result that minimizes the required routing resource. This framework successfully synthesizes more than 1000 standard cells with competitive qualities relative to commercial cell libraries under commercial 28-nm technology nodes. Next, we develop a pin accessibility evaluation model for standard cell layouts. Cell layout designers can use this accurate estimation model to optimize the pin accessibilities of cell layouts in order to optimize the routability of VLSI designs. Our experimental results indicate that VLSI design with higher pin accessibility can provide better routing results in terms of total wirelength and via count. Finally, an exact multilayer pattern matching method is proposed to detect lithography-unfriendly patterns on standard cell–based designs. Manufacturing problems can accordingly be investigated and resolved in the early design stage.

摘要 I
ABSTRACT III
Acknowledgement V
Table of Contents VI
List of Tables XIII
Chapter 1. Cell Layout Structure and Complex Design Rules 1
1.1 Layout Structure 2
1.2 Folding Styles and Their Effects 3
1.3 Design Challenges from Complex Design Rules 6
1.4 IO Pin Accessibility for Routing of VLSI Designs 9
1.5 Cell Layout Synthesis Basis 12
1.6 Literature Review 13
1.6.1 Overview of Cell Layout Synthesis 13
1.6.2 Overview of Cell Layout’s IO Pin Accessibility 19
1.6.3 Overview of Process Hotspot Recognition 21
1.7 Chapter Overviews and Contributions 22
Chapter 2. Routability-Aware Transistor Placement 25
2.1 Introduction 25
2.2 Problem Definitions 26
2.3 Routability-Aware DP-Based Transistor Placement 27
2.3.1 Routability-Aware Transistor Placement Considering Transmission Gate 30
2.4 LEGO-Like Placement for High-Driving Cells 33
2.5 Experimental Results 35
Chapter 3. Cell-Height–Aware Routing Considering Complex Design Rules 40
3.1 Introduction 40
3.2 Problem Definition 41
3.3 Routing Resource-Related Cell Structure Factors 41
3.4 Routing Flow 44
3.5 Resource-Aware Routing-Track Generation 45
3.6 M2- and PGRE-Aware Routing-Resource Estimation 48
3.7 CIAPR 51
3.7.1 Concurrent Track Assignment 52
3.7.2 Concurrent IOPM Allocation and Track Assignment 55
3.7.3 Variable-Width Pattern Routing 56
3.7.4 Vertical-Column Allocation 57
3.7.5 Greedy-Based Minimum-Cost MIS Solver 59
3.8 Negotiation-Based Maze Routing 60
3.9 Post-Routing Optimization 61
3.10 Cell Synthesis Results 64
Chapter 4. Pin Accessibility Estimation Model for Improving Routability of VLSI Designs 72
4.1 Introduction 72
4.2 Model to Estimate Pin Accessibility 73
4.2.1 Pin Accessibility Computation for M1 Layer 73
4.2.2 Pin Accessibility Computation for M2 Layer 76
4.3 Example of Pin Accessibility Computation 78
4.4 Experimental Results 81
4.4.1 Evaluation Setup 81
4.4.2 Experimental Result 81
Chapter 5. Fast and Exact Multilayer Pattern Matching for DFM-Aware Layout Designs 84
5.1 Introduction 84
5.2 Problem Definition 85
5.3 Preliminary – Single-Layer Pattern Matching with EPE 86
5.3.1 Design Concept 86
5.3.2 Single-Polygon Matching 87
5.3.3 Space Graph Construction 88
5.4 Multilayer Extension 89
5.4.1 Via Insertion 89
5.4.2 Multilayer Pattern Matching 90
5.5 Experimental Results 93
5.6 Complex Rule Violation Identification with Exact Pattern Matching 97
Chapter 6. Conclusions and Future Works 99
References 102

[1] T. Jhaveri et al, "Co-Optimization of Circuits, Layout and Lithography for Predictive Technology Scaling Beyond Gratings," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, Issue 4, pp. 509-527, 2010.
[2] Aseem Agarwal et al, “Circuit Optimization Using Statistical Static Timing Analysis,” in Proc. of the 42nd ACM/IEEE Design Automation Conference, pp. 321-324, 2005.
[3] Takao Uehara and William M. Vancleemput, "Optimal Layout of CMOS Functional Arrays," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. C-30, Issue 5, pp. 305-312, 1981.
[4] Robert L. Maziasz and John P. Hayes, “Layout Optimization of CMOS Functional Cells,” in Proc. of the 24th ACM/IEEE Design Automation Conference, 1987.
[5] Y.-J. Kwon, and C.-M. Kyung, "A Fast Heuristics for Optimal CMOS Functional Cell Layout Generation," in Proc. of IEEE International Symposium on Circuits and Systems, 1988.
[6] C. J. Poirier, “Excellerator: Custom CMOS Leaf Cell Layout Generator,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, Issue 7, pp. 744-755, 1989.
[7] Y.-C. Hsieh et al, “LiB: A Cell Layout Generator,” in Proc. of the 48th ACM/IEEE Design Automation Conference, 1990.
[8] C.-Y. Hwang et al, "A Fast Transistor-Chaining Algorithm for CMOS Cell Layout," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, Issue 7, pp. 781-786, 1990.
[9] Mohan Guruswamy et al, "CELLERITY: A Fully Automatic Layout Synthesis System for Standard Cell Libraries," in Proc. of the 34th ACM/IEEE Design Automation Conference, pp. 327-332, 1997.
[10] Jaewon Kim and S. M. Kang, “An Efficient Transistor Folding Algorithm for Row-Based CMOS Layout Design,” in Proc. of the 34th ACM/IEEE Design Automation Conference, pp. 456-459, 1997.
[11] A. Gupta and J.P. Hayes, “Optimal 2-D Cell Layout with Integrated Transistor Folding,” in Proc. of IEEE/ACM International Conference on Computer Aided Design, pp. 128-138, 1998.
[12] 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.
[13] Luca Macchiarulo, Luca Benini, and Enrico Macii, "On-the-Fly Layout Generation for PTL Macrocells," in Proc. of IEEE Design, Automation and Test in Europe, pp. 546-551, 2001.
[14] Maciej Ciesielski, Serkan Askar, and Samuel Levitin, "Analytical Approach to Layout Generation of Datapath Cells," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, Issue 12, pp. 1480-1488, 2002.
[15] L. Mathew et al, "CMOS Vertical Multiple Independent Gate Field Effect Transistor (MIGFET)," in Proc. of IEEE International SOI Conference, 2004.
[16] Cristiano Lazzari et al, "A New Transistor-Level Layout Generation Strategy for Static CMOS Circuits," in Proc. of IEEE International Conference on Electronics, Circuits and Systems, 2006.
[17] Adriel Ziesemer, and Cristiano Lazzar, "Transistor Level Automatic Layout Generator for Non-Complementary CMOS Cells," in Proc. of International Conference on Very Large Scale Integration, 2007.
[18] Wei Lu, Ping Xie, and Charles M. Lieber, "Nanowire Transistor Performance Limits and Applications," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 55, Issue 11, pp. 2859-2876, 2008.
[19] Hoon Cho et al, "A Low-Power, Highly Scalable, Vertical Double-Gate MOSFET Using Novel Processes," in IEEE Transactions on Electron Devices, vol. 55, Issue 2, pp. 632-639, 2008.
[20] B. Yang et al, "Vertical silicon-nanowire formation and gate-all-around MOSFET," in IEEE Electron Device Letters, vol. 29, Issue 7, pp. 791-794, 2008.
[21] M. Rostami, and K. Mohanram, "Novel dual-Vth independent-gate FinFET circuits," in Proc. of the 15th Asia and South Pacific Design Automation Conference, pp. 867-872, 2010.
[22] Ho. Zhang, Martin D.F. Wong, and K.-Y. Chao, "On Process-Aware 1-D Standard Cell Design," in Proc. of the 15th Asia and South Pacific Design Automation Conference, pp. 838-842, 2010.
[23] N. Ryzhenko and S. Burns, "Physical Synthesis onto a Layout Fabric with Regular Diffusion and Polysilicon Geometries," in Proc. of the 48th ACM/IEEE ACM/IEEE Design Automation Conference, pp. 83-88, 2011.
[24] S. Sinha et al, "Exploring Sub-20nm FinFET Design with Predictive Technology Models," in Proc. of the 48th ACM/IEEE Design Automation Conference, pp. 283-288, 2012.
[25] N. Ryzhenko and S. Burns, “Standard Cell Routing via Boolean Satisfiability,” in Proc. of the 48th ACM/IEEE Design Automation Conference, pp. 603-612, 2012.
[26] Stefan Hougardy et al, "BonnCell: Automatic Layout of Leaf Cells," in Proc. of the 18th Asia and South Pacific Design Automation Conference, pp. 453-460, 2013.
[27] Rasit O. Topaloglu, "Design with FinFETs: Design Rules, Patterns, and Variability," in Proc. of IEEE/ACM International Conference on Computer Aided Design, pp. 569-571, 2013.
[28] P.-H. Wu et al, "1-D Cell Generation With Printability Enhancement," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, Issue 3, pp. 419-432, 2013.
[29] J. Cortadella, "Area-Optimal Transistor Folding for 1-D Gridded Cell Design," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, Issue 11, pp. 1708-1721, 2013.
[30] J. Cortadella et al, "A Boolean Rule-Based Approach for Manufacturability-Aware Cell Routing," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, Issue 3, pp. 409-422, 2014.
[31] K. Vaidyanathan et al, "Sub-20 nm Design Technology Co-Optimization for Standard Cell Logic," in Proc. of IEEE/ACM International Conference on Computer Aided Design, pp. 124-131, 2014.
[32] R. Aitken et al, "Physical Design and FinFETs," in ACM International Symposium on Physical Design, pp. 65-68, 2014.
[33] H. Mashiko and Y. Kohira, "Area Minimization Method for CMOS Circuits Using Constraint Programming in 1D-Layout Style," in Proc. of IEEE International Symposium on VLSI Design, Automation and Test, 2016.
[34] H.-J. Lu et al, “Practical ILP-Based Routing of Standard Cells,” in Proc. of IEEE Design, Automation and Test in Europe, pp. 245-548, 2016.
[35] Pascal Cremer et al, “Automatic Cell Layout in the 7nm Era,” in ACM International Symposium on Physical Design, pp. 99-106, 2017.
[36] X. Xu, "Standard Cell Library Design and Optimization Methodology for ASAP7 PDK," in Proc. of IEEE/ACM International Conference on Computer Aided Design, pp. 999-1004, 2017.
[37] M.-C. Kim et al., “A SimPLR method for routability-driven placement,” in Proc. of the 48th IEEE/ACM International Conference on Computer-Aided Design, pp. 67 – 73, 2011.
[38] Tim Nieberg, “Gridless Pin Access in Detailed Routing,” in Proc of the 48th ACM/IEEE Design Automation Conference, pp. 170 – 175, 2011.
[39] W.-H. Liu et al., “Optimization of Placement Solutions for Routability,” in Proc. of the 50th ACM/IEEE Design Automation Conference, 2013.
[40] X. He et al., “Ripple 2.0: High Quality Routability-Driven Placement via Global Router Integration,” in Proc. of the 50th ACM/IEEE Design Automation Conference, 2013.
[41] W.-H. Liu, C.-K. Koh, and Y.-L. Li, "Optimization of Placement Solutions for Routability," in Proc. of the 50st ACM/EDAC/IEEE Design Automation Conference, 2013.
[42] T. Lin and Chris Chu, “POLAR 2.0: An Effective Routability-Driven Placer,” in Proc. of the 51st ACM/EDAC/IEEE Design Automation Conference, 2014.
[43] Y. Du and Martin D. F. Wong, "Optimization of Standard Cell Based Detailed Placement for 16 nm FinFET Process," in Proc. of IEEE Design, Automation and Test in Europe, 2014.
[44] M.-K. Hsu et al., “Design and Manufacturing Process Co-Optimization in Nano-Technology," in Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp. 574 – 581, 2014.
[45] C.-C. Huang et al, "Detailed-Routing-Driven Analytical Standard-Cell Placement," in Proc. of the 20th Asia and South Pacific Design Automation Conference, pp. 378-383, 2015. D. Shi, and A. Davoodi, "Improving Detailed Routability and Pin Access with 3D Monolithic Standard Cells," in ACM International Symposium on Physical Design, 2017.
[46] X. Xu et al, "Concurrent Pin Access Optimization for Unidirectional Routing," in Proc. of the 53th ACM/IEEE Design Automation Conference, 2017.
[47] W. Ye et al, “Standard Cell Layout Regularity and Pin Access Optimization Considering Middle-of-Line,” in Proc. of ACM Great Lakes Symposium on VLSI, pp. 289-294, 2015.
[48] X. Xu et al., “Self-Aligned Double Patterning Aware Pin Access and Standard Cell Layout Co-Optimization," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 34(5), pp. 699 – 712, 2015.
[49] X. Xu et al., “PARR: Pin Access Planning and Regular Routing for Self-Aligned Double Patterning,” in Proc. of the 52nd ACM/IEEE Design Automation Conference, 2015.
[50] X. Xu et al., “Standard Cell Pin Access and Physical Design in Advanced Lithography,” in Proc. of SPIE Intl. Symp. Advanced Lithography Conference, pp. 21 – 25, 2016.
[51] J. Seo et al, "Pin Accessibility-Driven Cell Layout Redesign and Placement Optimization," in Proc. of the 53th ACM/IEEE Design Automation Conference, 2017.
[52] K. Bhanushali, and W. Rhett Davis, "FreePDK15: An Open-Source Predictive Process Design Kit for 15nm FinFET Technology," in ACM International Symposium on Physical Design, pp. 166-170, 2015.
[53] M. Martins et al, "Open Cell Library in 15nm FreePDK Technology," in ACM International Symposium on Physical Design, pp. 171-178, 2015.
[54] M. Oostindie, C. Zelnik, and M. Berkens, "Design Rule Management and Its Applications in 15nm FreePDK Technology," in ACM International Symposium on Physical Design, pp. 179-183, 2015.
[55] L.-D. Huang and D. F. Wong, “Optical Proximity Correction (OPC)-Friendly Maze Routing,” In Proc. Design Automation Conference, 2004.
[56] M. C. Simmons et al, “A state-of-the-art hotspot recognition system for full chip verification with lithographic simulation,” In Proc. International Society for Optical and Photonics, 2011.
[57] M. Cote and P. Hurat, “Layout Printability Optimization Using a Silicon Simulation Methodology,” In Proc. International Symposium on Quality of Electronic Design, 2004.
[58] Hassan Lachkar et al, "Layout Uniformity: A Metric for Yield Enhancement", In Proc. of International Midwest Symposium on Circuits and Systems, 2011.
[59] Chris Schuermyer et al, "Identifying Systematic Critical Features Using Silicon Diagnosis Data", In Proc. of Advanced Semiconductor Manufacturing Conference, 2012.
[60] Michel Cote and Philippe Hurat, "Standard Cell Printability Grading and Hot Spot Detection", In Proc. of International Symposium on Quality of Electronic Design, 2005.
[61] Ed Roseboom et al, "Automated Full-Chip Hotspot Detection and Removal Flow for Interconnect Layers of Cell-Based Designs", In Proc. International Society for Optical and Photonics, 2007.
[62] A. B. Kahng et al, “Fast Dual-Graph-Based Hotspot Filtering,” In IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 9, pp. 1635-1642, 2008.
[63] Y.-T. Yu et al, “Accurate Process-Hotspot Detection Using Critical Design Rule Extraction,” In Proc. Design Automation Conference, 2012.
[64] H. Yao et al, “Efficient Process-Hotspot Detection Using Range Pattern Matching,” In Proc. International Conference on Computer Aided Design, 2006.
[65] J. Xu et al, “Accurate Detection for Process Hotspot s with Vias and Incomplete specification”, In Proc. International Conference on Computer Aided Design, 2007.
[66] J. Guo et al, “Improved Tangent Space Based Distance Metric for Accurate Lithographic Hotspot Classification,” In Proc. Design Automation Conference, 2012.
[67] S.-Y. Lin et al, "A Novel Fuzzy Matching Model for Lithography Hotspot Detection," In Proc. Design Automation Conference, 2013.
[68] D. Ding et al, “High Performance Lithographic Hotspot Detection Using Hierarchically Refined Machine Learning,” In Proc. Asia and South Pacific Design Automation Conference, 2011.
[69] J.-Y. Wuu et al, “Rapid Layout Pattern Classification,” In Proc. Asia and South Pacific Design Automation Conference, 2011.
[70] Y.-T. Yu et al, “Machine-Learning-Based Hotspot Detection Using Topological Classification and Critical Feature Extraction,” In Proc. Design Automation Conference, 2013.
[71] D.-S. Fu et al, “Topology-Driven Cell Layout Migration with Collinear Constraints”, In Proc. of International Conference on Computer Design, 2009.
[72] Moon J., “Counting Labelled Trees”, Canadian Math. Congress, 1970.
[73] Kirti N Bhanushali, “Design Rule Development for FreePDK15: An Open Source Predictive Process Design Kit for 15nm FinFET Devices,” Thesis, North Carolina State University, May 2014. http://www.lib.ncsu.edu/resolver/1840.16/9519.
[74] H.-Y. Su, “A Novel Fast and Accurate Process Hotspot Detection Method with Prüfer-Code Layout Encoding,” Master Thesis, National Chiao Tung University, 2013.
[75] H.-Y. Su et al, “A Novel Fast Layout Encoding Method for Exact Multilayer Pattern Matching With Prüfer Encoding,” In IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 34, No. 1, pp. 95-108, 2015.