請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/24197
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 黃寶儀(Polly Huang) | |
dc.contributor.author | Kai-Fu Tang | en |
dc.contributor.author | 湯凱富 | zh_TW |
dc.date.accessioned | 2021-06-08T05:18:14Z | - |
dc.date.copyright | 2005-08-01 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-08-01 | |
dc.identifier.citation | [1] Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2004.
[2] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, 'B*-trees: A new representation for non-slicing floorplans,' Proc. DAC, pp. 458-463, 2000. [3] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, 'An O-tree representation of non-slicing floorplans and its applications,' Proc. DAC, pp. 268-273, 1999. [4] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu, 'Corner block list: an effective and efficient topological representation of non-slicing floorplan,' Proc. ICCAD, pp. 8-12, 2000. [5] J.-M. Lin and Y.-W. Chang, 'TCG: A transitive closure graph-based representation for non-slicing floorplans,' Proc. DAC, pp. 764-769, 2001. [6] J.-M. Lin and Y.-W. Chang, 'TCG-S: orthogonal coupling of P*-admissible representations for general floorplans,' Proc. DAC, pp. 842-847, 2002. [7] M. Lai and D. F. Wong, 'Slicing tree is a complete floorplan representation,' Proc. DATE, pp. 228--232, 2001. [8] E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976. [9] M. Moe and H. Schmit, 'Floorplanning of pipelined array modules using sequence pairs,' Proc. ISPD, pp. 143-150, 2003. [10] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, 'Rectangle-packing based module placement,' Proc. ICCAD, pp. 472-479, 1995. [11] S. Nakatake, H.Murata, K. Fujiyoshi, and Y. Kajitani, 'VLSI module placement on BSG-structure and IC layour applications,' Proc. ICCAD, pp. 484-491, 1996. [12] R. H. J. M. Otten, 'Automatic floorplan design,' Proc. DAC, pp. 261-267, 1982. [13] Y. Pang, C.-K. Cheng, K. Lampaert, and W. Xie, 'Rectilinear block packing using O-tree representation,' Proc. ISPD, pp. 156-161, 2001. [14] K. Sakanushi and Y. Kajitani, 'The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization,' Proc. APCAS, pp. 829--832, 2000. [15] X. Tang, R. Tian, and D. F. Wong, 'Fast evalution of sequence pair in block placement by longest common subsequence computation,' Proc. DATE, pp. 106-111, 2000. [16] X. Tang and D. F. Wong, 'FAST-SP: A fast algorithm for block placement based sequence pair,' Proc. APS-DAC, pp. 521-526, 2001. [17] X. Tang and D. F. Wong, 'Floorplanning with alignment and performance constraints,' Proc. DAC, pp. 848-853, 2002. [18] D. F. Wong and C. L. Liu, 'A new Algorithm for floorplan design,' Proc. DAC, pp. 101-107, 1986. [19] M.-C. Wu and Y.-W. Chang, 'Placement with Alignment and Performance Constraints Using the B*-tree representation,' Proc. ICCD, pp. 568-571, 2004. [20] J. Xu, P.-N. Guo, and C.-K. Cheng, 'Rectilinear block placement using sequence-pair,' Proc. ISPD, pp. 173-178, 1998. [21] B. Yao, H. Chen, C.-K. Cheng, and R. Graham, 'Revisiting floorplan representations,' Proc. ISPD, pp. 138--143, 2001. [22] F. Y. Young and D. F. Wong, 'Slicing floorplans with range constraint,' Proc. ISPD, pp. 97-102, 1999. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/24197 | - |
dc.description.abstract | 為了降低時脈週期以及促進循序電路的傳輸,在設計時需考量將管線模組一個接一個的擺放。在這篇論文中,我們利用遞移封閉圖的表示法處理以管線為導向的電路平面規劃問題。遞移封閉圖是一個具有彈性且有效率的表示法,我們首先探討在管線模組限制條件下所具備的必要條件,並提出一個演算法,該演算法保證在每次運作過程都可以找到符合管線模組限制條件的電路擺法。實驗數據顯示,說明了我們的方法比起之前使用sequence-pair表示法的方法有很明顯的進步。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T05:18:14Z (GMT). No. of bitstreams: 1 ntu-94-R92921033-1.pdf: 263934 bytes, checksum: f474ae0efd64cdacbd8d4f8415f418d2 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 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 33 | |
dc.language.iso | en | |
dc.title | 利用遞移封閉圖處理以管線為導向之平面規劃 | zh_TW |
dc.title | Pipeline-Driven Floorplanning Using TCG | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 張耀文(Yao-Wen Chang),黃俊郎(Jiun-Lang Huang),黃鐘揚(Chung-Yang Huang) | |
dc.subject.keyword | 電子設計自動化,平片規劃, | zh_TW |
dc.subject.keyword | Electronic Design Automation,Floorplanning, | en |
dc.relation.page | 35 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2005-08-01 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 257.75 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。