黃寶儀臺灣大學：電機工程學研究所湯凱富Tang, Kai-FuKai-FuTang2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53489為了降低時脈週期以及促進循序電路的傳輸，在設計時需考量將管線模組一個接一個的擺放。在這篇論文中，我們利用遞移封閉圖的表示法處理以管線為導向的電路平面規劃問題。遞移封閉圖是一個具有彈性且有效率的表示法，我們首先探討在管線模組限制條件下所具備的必要條件，並提出一個演算法，該演算法保證在每次運作過程都可以找到符合管線模組限制條件的電路擺法。實驗數據顯示，說明了我們的方法比起之前使用sequence-pair表示法的方法有很明顯的進步。To reduce clock period and facilitate sequential data transfer, it is desired to abut pipeline blocks one by one without predefined directions. In this thesis, we handle the floorplanning with pipeline constraints using the TCG representation. The TCG representation has been shown a flexible and efficient representation. We first explore the necessary conditions with pipeline constraints, and then propose algorithms that can guarantee a feasible floorplan with pipeline constraints during each operation. The experimental results have shown that our algorithm can obtain superior results compared to the method using the sequence-pair representation.Abstract (Chinese) i Abstract ii Acknowledgements iii List of Tables vi List of Figures vii Chapter 1. Introduction 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Slicing and Non-Slicing Floorplans . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Slicing Floorplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Non-Slicing Floorplan . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 PreviousWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Floorplanning Algorithms for Alignment and Performance Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Floorplanning Algorithms for Pipeline Constraints . . . . . . . . . 7 1.4 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapter 2. Preliminaries 10 2.1 The TCG Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Pipeline Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chapter 3. Floorplanning with Pipeline Constraints 15 3.1 TCG with Pipeline Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Transitive Reduction and Closure Edges . . . . . . . . . . . . . . . 15 3.1.2 Inseparability Constraint . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Transforming an Infeasible Floorplan to a Feasible One . . . . . . . . . . 19 3.2.1 Dummy Block Insertion . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.2 Dummy Edge Insertion . . . . . . . . . . . . . . . . . . . . . . . . 20 Chapter 4. Algorithm 22 4.1 Reduction Edge Identification . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Solution Perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.1 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.2 Swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.3 Reverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.4 Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Feasibility Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Chapter 5. Experimental Results 28 Chapter 6. Conclusion 32 Bibliography 33263934 bytesapplication/pdfen-US電子設計自動化平片規劃Electronic Design AutomationFloorplanningthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53489/1/ntu-94-R92921033-1.pdf