陳少傑臺灣大學：電機工程學研究所何宗易Ho, Tsung-YiTsung-YiHo2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53409由於超大型積體電路技術的快速發展，晶片設計已經到達奈米製程的時代。但在奈米晶片實體設計中，繞線(routing)所造成的問題佔整體晶片設計效能的比例卻逐漸增加且面臨到許多問題，尤其是(1)設計複雜度、(2)訊號完整度(signal-integrity)及(3)製造度(manufacturability)等三大問題急需去處理。因此，本篇論文提出了一創新的多階層繞線器(mSIGMA)來解決訊號完整度及可製造度等問題。 早期的繞線問題是使用直接兩階段繞線方式(flat routing)，也就是全域繞線(global routing)及區域繞線(detailed routing)來處理繞線問題，但此解法受限在其對於處理大量資料時的延伸性，為了解決這問題，學者們提出了階層繞線(hierarchical routing)來解決較大量的繞線問題，其使用了分而治之(divide and conquer)的方式來降低問題複雜度，但階層繞線仍受限於其無法保留各切割區塊間的全域資訊，得到更精確的結果，為了解決此問題，學者提出了多階層繞線器來解決以上架構所產生的問題。 多階層架構包含兩個主要步驟：粗糙化(coarsening)及反粗糙化(uncoarsening)。與之前多階層繞線器架構不同的地方是，我們在粗糙化及反粗糙化之間，提出了一軌道指派(track assignment)階段來加快繞線速度及實作最佳化。除了此創新的多階層架構，我們也對串音問題(crosstalk)、效能問題(performance)、天線效應問題(antenna effect)甚至最近提出的X架構(X-architecture)做了深入的研究。實驗結果證明，我們的創新架構比其他方法具有較好的彈性來處理以上的問題。跟之前發表在電子設計自動化重要會議發表的多階層繞線器相比，我們的方法在串音、效能、天線效應及總線長上，都有明顯的改善。在X架構的研究上，跟我們實作在曼哈頓架構(Manhattan architecture)的多階層繞線器相比，在總線長及效能上也都得到了不錯的成果。As technology advances into nanometer territory, the paradigm shift of the routing problem is indispensable to cope with three major challenges: design complexity, signal-integrity problem, and manufacturability problem. As Moore's Law continues unencumbered into the nanometer era, chips are reaching 100 M gates in size, process geometries have shrunk to 90 nm and below, and engineers have to face compounded design complexity with every new design. These nanometer-scale designs require a new generation of physics-aware and manufacturing- aware routing. At 90 nm and below, there are so many signal-integrity issues that design teams cannot manually correct them all. Nanometer routers must prevent and correct these effects on-the-fly in order to reach timing closure. From a manufacturability standpoint, nanometer routers must explicitly support the ever increasing design complexity, and be capable of adapting to the requirements of timing, signal integrity, process antenna effect, and new interconnect architecture such as X-architecture. In this Dissertation, we propose a novel multilevel full-chip router, namely mSIGMA for SIGnal-integrity and MAnufacturability optimization. To handle the ever increasing design complexity of gigascale integration, the mSIGMA use a multilevel framework that has attracted much attention in the literature recently. The traditional multilevel framework employs a two-stage technique: coarsening followed by uncoarsening. The coarsening stage iteratively groups a set of circuit components (e.g., circuit nodes, cells, modules, routing tiles, etc.) based on a predefined cost metric until the number of components being considered is smaller than a threshold. Then, the uncoarsening stage iteratively ungroups a set of previously clustered circuit components and refines the solution by using optimization techniques. Different with the previous multilevel routing framework, we introduce an intermediate track assignment phase between coarsening and uncoarsening stages, to improve run-time and achieve optimization. To handle the signal-integrity problem, especially the crosstalk problem, we propose a fast layer/track assignment heuristic for crosstalk optimization. We first build the horizontal constraint graph (HCG) for all segments in the panel. For the crosstalk-driven layer assignment problem, we resort to a simple yet efficient heuristic by constructing a maximum spanning tree from the given HCG. Since a tree can be k colored in linear time if we have k layers, we shall first partition the vertices incident on edges with larger costs (coupling lengths) and allocates the corresponding segments to different layers. Then, our track assignment algorithm starts by finding the maximal sets of conflicting segments, and assigns these conflicting segments by the bipartite assignment graph till they are assigned in the panel. To handle the manufacturability problem, such as process antenna effect and the X-architecture, we also propose a desirable track assignment in our multilevel routing framework for manufacturability optimization. To solve the antenna effect, we propose a built-in jumper insertion approach for antenna effect avoidance. To take the advantage of the X-architecture, we also adopt our new multilevel routing framework for the X-based architecture, and the experimental results show the promise of wirelength and delay reduction.ABSTRACT i TABLE OF CONTENTS iii LIST OF FIGURES vii LIST OF TABLES xi CHAPTER 1 INTRODUCTION 1 1.1 Down to the Wire 1 1.2 Routing Requirements for the Nanometer Era 3 1.2.1 Signal-Integrity Problems 4 1.2.2 Manufacturability Problems 8 1.3 Overview of the Dissertation 11 1.3.1 Multilevel Routing Framework 11 1.3.2 Multilevel Full-Chip Routing Considering Crosstalk and Performance 12 1.3.3 Multilevel Full-Chip Routing Considering Antenna Effect Avoidance 13 1.3.4 Multilevel Full-Chip Routing for the X-Based Architecture 13 1.4 Organization of the Dissertation 14 CHAPTER 2 MULTILEVEL ROUTING FRAMEWORK 15 2.1 Traditional Routing 15 2.1.1 Sequential Approaches 16 2.1.2 Concurrent Approaches 17 2.1.3 Hierarchical Approaches 19 2.2 Multilevel Routing 21 2.2.1 Previous Multilevel Routing Framework 22 2.2.2 Our Multilevel Routing Framework 26 2.2.3 Routing Model 28 2.2.4 Multilevel Routing Model 29 CHAPTER 3 MULTILEVEL FULL-CHIP ROUTING CONSIDERING CROSSTALK AND PERFORMANCE 31 3.1 Introduction 31 3.2 Elmore Delay Model 34 3.3 Multilevel Routing Framework 36 3.3.1 Performance-Driven Routing Tree Construction 37 3.3.2 Crosstalk-Driven Layer/Track Assignment 45 3.4 Experimental Results 50 3.5 Summary 55 CHAPTER 4 MULTILEVEL FULL-CHIP ROUTING CONSIDERING ANTENNA EFFECT AVOIDANCE 57 4.1 Introduction 57 4.2 Antenna Effect Damage 60 4.3 Multilevel Routing Framework 64 4.3.1 Bottom-Up Optimal Jumper Prediction 66 4.3.2 Multilevel Routing with Antenna Avoidance 72 4.3 Experimental Results 76 4.3 Summary 77 CHAPTER 5 MULTILEVEL FULL-CHIP ROUTING FOR THE X-BASED ARCHI- TECTURE 79 5.1 Introduction 79 5.2 Multilevel X Routing Framework 83 5.3 X-Architecture Steiner Tree Construction 85 5.3.1 Three-Terminal Net Routing Based on X-Architecture 86 5.3.2 X-Steiner Tree Algorithm Based on Delaunay Triangulation 90 5.4 Routability-Driven Pattern Routing 91 5.5 Trapezoid-Shaped Track Assignment 93 5.6 Experimental Results 98 5.7 Summary 101 CHAPTER 6 CONCLUSION REMARKS AND FUTURE WORK 103 6.1 Multilevel Routing Framework 103 6.2 Multilevel Full-Chip Routing Framework Considering Crosstalk and Performance 104 6.3 Multilevel Full-Chip Routing Framework Considering Antenna Effect Avoidance 105 6.4 Multilevel Full-Chip Routing Framework for the X-Based Architecture 105 6.5 Future Work 106 BIBLIOGRAPHY 1073566837 bytesapplication/pdfen-US積體電路實體設計繞線訊號完整度製造度VLSI Physical DesignRoutingSignal-integrityManufacturability[SDGs]SDG16thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53409/1/ntu-94-D90921011-1.pdf