陳少傑臺灣大學：電機工程學研究所Fang, Jyh-PerngJyh-PerngFang2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53073線評估及電源遞送這兩個問題在大多數情況下彼此獨立，但在某些情況下卻彼此相關，因此，我們針對不同的情況提出不同的對策。 對於電源遞送的評估，我們提出SE演算法來迅速評估電源輸入線的壓降。和現有的技術相比，SE演算法的優點是其資料結構單純，因此評估速度非常快。 就接線的問題而言，我們針對常見的繞線及緩衝器置入進行處理，所提出的包括MR演算法及MBR演算法，前者負責曼哈頓式繞線及緩衝器置入的評估，後者負責迂迴式繞線及緩衝器置入的評估。這兩者都採用現有的IFR技術來計算緩衝器的置入位置。 基於提昇速度及精確度的考量，MR及MBR演算法更分別被升級成FMR及DR演算法，計算緩衝器置入位置的方法也由IFR技術改成速度更快的BSA技術。 而且我們還進一步將習用的緩衝器位置計算方法BSA改進成EBSA。和BSA相較，EBSA對於獨佔性匯流排的緩衝器擁擠程度的評估較正確。 對於低成本的設計或接線層受限的設計而言，電源線和訊號線常不得不置於同一層。因此，若能將接線評估及電源遞送評估整合在一起，將能使評估結果更精確。我們將評估接線、評估電源遞送的諸演算法整合成一個完整的程序。在這個程序中，電源規劃的評估結果可以視需要饋入繞線演算法中。為了讓壓降及瞬間電流雜訊的評估結果可以饋入接線評估的演算法中，並新增瞬間電流雜訊的評估能力，我們將SE演算法更新成OSE演算法。為了評估電源線的繞線擁擠程度，我們也提出PMR演算法。另外，還提出FPSMR演算法，它別經由PMR演算法及FMR演算法評估電源線及訊號線的繞線擁擠程度，並加以整合。我們還將整合的程序嵌入疊代式平面規劃演算法中，使得繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊等影響實體設計訊號完整性的因素可以在平面規劃的階段先期評估，從而得出具有較佳面積/總線長且滿足繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊等限制條件的平面圖。 本論文所提出的諸演算法及計算程序均基於輕便靈敏的閘格結構，由於這種結構的計算速度夠快，因此相關評估的演算法可以順利整合至平面規劃器，而且不會使平面規劃器的整體速度明顯變慢。將繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊的評估整合至平面規劃器中可以先期過濾可能會在設計流程後段失敗的設計，從而早期達到設計收歛(design closure)的目標。With the advances of VLSI technology, deep-sub-micron (DSM) fabrication process becomes more and more popular. In a DSM design, the congestion dominated by interconnections has become an important design issue. Some other previously overlooked effects, such as IR-drop and ground-bounce are also becoming the first-order design parameters to consider. Both the interconnection and power delivery effects are difficult to predict precisely during early design stage. Therefore, the VLSI physical design flow for DSM fabrication technology is typically performed in an iterative and incremental style. This research attempts to decrease the design iterations in such an iterative design flow by excluding the factors that are inclined to cause design failure. We propose two main problem-solving mechanisms at the foorplanning stage: interconnection evaluation and power delivery evaluation. The former takes congestion into account, the latter focuses on IR-drop and ground bounce. These two problems are independent for most design cases, but are related for some design cases. Therefore, different strategies have to be proposed for different conditions. For the problem of power delivery evaluation, a Successive Elimination (SE) power planning algorithm is proposed to evaluate IR-drop’s of power inputs. In comparison to the existing approaches, SE algorithm features simple data structure and thus a significantly efficient evaluation speed. For the problem of interconnection evaluation, we proposed a Manhattan Routing (MR) algorithm and a Maze-based between-buffer Routing (MBR) algorithm, which apply the existing Independent Feasible Region (IFR) technique to decide buffer locations and are responsible for the simultaneous routing and buffering, respectively in a Manhattan-type and a detour-type of interconnections. The MR and MBR algorithms are then respectively revised as a Fast Manhattan Routing (FMR) algorithm and a Detour Routing (DR) algorithm. The FMR and DR algorithms adopt the technique of Buffer Sit Approach (BSA) instead of IFR to decide buffer locations. In comparison to the MR and MBR algorithms, the FMR and DR algorithms feature a more efficient congestion evaluation. Moreover, as we have observed that BSA may insert buffers to congested regions on a dominant bus, an extended version of BSA, enhanced buffer site approach (EBSA), is proposed, which can evenly insert buffers to a dominant bus. For a low cost design or a design with limited layers, where power lines and signal nets are inevitably put on the same layer(s), the integration of interconnection evaluation and IR-drop/ground-bounce evaluation facilitates a more precise prediction Thus, a procedure is proposed to integrate power delivery planning, routing, and buffering in an iterative floorplanner such that IR-drop, ground-bounce and different kinds of congestions in a design can be simultaneously evaluated. To support more precise evaluation and to facilitate the interactions between power delivery planning and congestion evaluation, the SE algorithm is further enhanced as an Ordered Successive Elimination (OSE) algorithm to handle ground bounce additionally and to generate information of power lines. Also, a Fast Power line and Signal net Manhattan Routing (FPSMR) algorithm is included in our procedure to perform congestion evaluation of power lines and signal nets. The FPSMR algorithm is analogous to the FMR algorithm. The only difference is that, before operating as the FMR algorithm doing to evaluate congestion, the FPSMR algorithm has to invoke a Power line Manhattan Routing (PMR) algorithm to route power lines generated by the OSE algorithm. Sharing an agile grid data structure, the algorithms and procedures presented in this Dissertation feature consuming less memory as well as providing a quick and effective evaluation. An effective evaluation facilitates filtering out designs with worse routability or inferior performance. Besides, as these evaluations are performed at an earlier design stage, the design iteration is thus effectively decreased. Since the evaluation speed of these algorithms and procedures is very fast, the operation speed of an iterative floorplanner integrating the proposed procedures can be much improved.ABSTRACT i LIST OF FIGURES vii LIST OF TABLES ix LIST OF ALGORITHMS xi CHAPTER 1 INTRODUCTION 1 1.1 Floorplanning in VLSI Physical Design 3 1.2 Previous Work 4 1.2.1 Floorplanning 4 1.2.2 Power Delivery Planning 5 1.2.3 Interconnection Planning 5 1.3 Simultaneous Power Delivery and Interconnection Planning 7 1.4 Our Contribution 8 1.5 Organization of the Dissertation 10 CHAPTER 2 BACKGROUND 11 2.1 Preconditions and Postconditions 11 2.2 Data Representations and Terminologies 11 2.2.1 B*-Tree 12 2.2.2 Grid Structures 12 2.2.3 Terminologies 12 2.3 Procedure of Integration 14 2.4 Independent Feasible Region and Buffer Site Approach 17 CHAPTER 3 SUCCESSIVE ELIMINATION AND IR-DROP EVALUATION 21 3.1 Background 21 3.2 Problem Formulation 22 3.3 Successive Elimination Method 22 3.3.1 Building a Supply-Demand Grid-Graph 23 3.3.2 Successive Elimination 24 3.3.3 Variation of SE Algorithm 27 3.3.4 Analysis of SE Algorithm 28 3.4 Experiment Results 29 3.5 Summary 31 CHAPTER 4 MANHATTAN ROUTING AND DETOUR ROUTING 33 4.1 Background 33 4.2 Models and Cost Functions 34 4.2.1 Net Density Estimation 35 4.2.2 Buffer Density Estimation 35 4.2.3 Cost Functions 36 4.3 Routing and Buffer-Insertion Algorithms 37 4.3.1 Manhattan Router 38 4.3.2 Analysis of MR 40 4.3.3 Maze-Based Between-Buffer Router 41 4.3.4 Procedure of Floorplanning 43 4.4 Experiment Results and Discussion 44 4.4.1 Routing with Different Schemes of MR and MBR 44 4.4.2 Routing with Different Net Orderings 45 4.4.3 Integration of MR/MBR and SA-Based Floorplanning Algorithm 45 4.5 Summary 46 CHAPTER 5 EFFICIENT MANHATTAN ROUTING AND DETOUR ROUTING 49 5.1 Background 49 5.2 Members in a Grid 50 5.3 Routing and Buffer-Insertion Procedure 51 5.3.1 Fast Manhattan Routing Algorithm 51 5.3.2 Detour Routing Algorithm 54 5.3.3 Time Complexities of FMR and DR 56 5.4 Experiment Results and Discussion 56 5.4.1 Classifications of Nets 56 5.4.2 Routing with Different Schemes of FMR and DR 57 5.5 Summary 59 CHAPTER 6 AN ENHANCED BUFFER SITE APPROACH 61 6.1 Background 61 6.1.1 Buffer Number and Congestion 61 6.1.2 Our Contribution 63 6.2 Problem Formulation 63 6.3 Congestion Evaluation model 64 6.4 Evaluating Buffer Congestion 65 6.4.1 Deciding Routing Path 65 6.4.2 Buffer Congestion Estimation 65 6.5 Experiment Results and Discussion 69 6.5.1 Applying EBSA to MCNC Circuits 69 6.5.2 The Effect of EBSA 71 6.6 Summary 72 CHAPTER 7 SIMULTANEOUS ROUTING BUFFERING AND POWER DELIVERY PLANNING 75 7.1 Background 75 7.1.1 Ground Bounce 76 7.1.2 Our Contribution 77 7.2 Problem Formulation 77 7.3 Procedure of Evaluating IR-Drop and Ground Bounce 78 7.3.1 Modeling Ground Bounce 78 7.3.2 Ordered Successive Elimination 79 7.3.3 Comparison of OSE and SE 82 7.4 Procedure of Evaluating IR-Drop Routing and Buffer-Insertion 82 7.4.1 Algorithm FPSMR 83 7.4.1.1 Routing Power Lines 84 7.4.1.2 Routing Signal Nets 84 7.4.2 Modified Detour Routing Algorithm 86 7.5 Experiment Results and Discussion 87 7.6 Summary 89 CHAPTER 8 CONCLUSION 91 BIBLIOGRAPHY 95874854 bytesapplication/pdfen-US電源規劃平面規劃繞線緩衝器置入Power PlanningRoutingBufferingFloorplanthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53073/1/ntu-93-D88921026-1.pdf