跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 21:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳信隆
研究生(外文):HsinLung Chen
論文名稱:以三維子遞移封閉圖處理時序性平面規劃
論文名稱(外文):Temporal Floorplanning Using 3D-subTCG
指導教授:莊仁輝張耀文張耀文引用關係
指導教授(外文):Jen-Hui ChuangYao-Wen Chang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
中文關鍵詞:時序性平面規劃遞移封閉圖三維子遞移封閉圖可重組態先後順序
外文關鍵詞:temporal floorplanningTransitive Closure Graph3D-subTCGreconfigurableprecedence
相關次數:
  • 被引用被引用:0
  • 點閱點閱:173
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
現場可程式化邏輯閘陣列 (FPGA) 是一種可以重新程式化的邏輯元件,它可以用來實作多層次邏輯,設計者可以直接在現場可程式化邏輯閘陣列上實作線路,毋須經由費時的製程,進而降低雛型製作的費用和縮短製造的時間。目前,現場可程式化邏輯閘陣列被廣泛的使用成一個獨立元件或是系統晶片的部份元件。隨著技術的演進,現場可程式化邏輯閘陣列的邏輯容量已經大量增加,為了能處理較高的邏輯複雜度,可重組態現場可程式化邏輯閘陣列 (dynamically reconfigurable FPGA) 利用分時共享 (time-sharing) 的技術來增加邏輯容量。在這本碩士論文中,我們使用一個新的平面規劃表示法──三維子遞移封閉圖 (3D-subTCG) 來處理在可重組的邏輯元件中三維平面規劃的問題。三維子遞移封閉圖表示法是延伸於遞移封閉圖 (TCG) 表示法,透過引進一個新的圖來描述模組間在時間軸上的關係,三維子遞移封閉圖表示法非常簡單而且非常好實作。模組間的幾何關係可以很直接的從遞移封閉圖表示法中看出,而三維子遞移封閉圖承接了這個特性,所以可以很容易的維持模組在可重組態現場可程式化邏輯閘陣列被執行時應遵循的執行先後順序。另外,我們推導出三維子遞移封閉圖的特性,用來降低解答空間以及縮短執行的時間。實驗結果證明,三維子遞移封閉圖可以在合理的執行時間內獲得比其他方法明顯更好的結果。
A Field programmabe gate array (FPGA) is a (re)programmable logic devices that implements multi-level logic.
FPGA's can be configured by designers at their sites, eliminating the time-consuming fabrication step, and thus result in low prototyping cost and short manufacturing times.
Currently, FPGA logic cores are widely used as stand-alone devices or parts of system-on-a-chip solutions.
As technology advances, FPGA logic capacity are getting higher.
To handle the high logic complexity, dynamically reconfigurable FPGAs apply the time-sharing technique to improve logic capacity.
In this thesis, we deal with the 3-dimension floorplanning/placement problems in the general reconfigurable device by using a novel floorplan representation, named {\em3D-subTCG} (3-Dimensional sub-Transitive Closure Graph).
The 3D-subTCG extends from the recently published Transitive Closure Graph (TCG) representation, by introducing an additional graph to describe the temporal relations between modules.
The 3D-subTCG is very simple and can be implemented easily. We
derive the feasibility conditions for the precedence constraints induced by the execution of the dynamically reconfigurable FPGAs. Inherited
the nice property from the TCG that the geometric relationship are transparent to its representation and its induced operations, we can easily maintain the precedence constraints in 3D-subTCGs.
We also derive some properties of the 3D-subTCG to reduce the solution space and shorten the running time for the 3-dimensional foorplanning/placement.
Experimental results show that our 3D-subTCG based algorithm can obtain significantly better floorplans than the previous work using reasonable running time.

Abstract i
List of Tables v
List of Fiugures vi
Chapter 1. Introduction 1
1.1 Dynamically Reconfigurable Architecture................ 1
1.1.1 Atmel AT6000 Series FPGAs........................ 2
1.1.2 Xilinx XC4000E FPGAs............................. 3
1.1.3 Xilinx XC6200 Series FPGAs....................... 4
1.1.4 Xilinx Virtex Series FPGAs....................... 5
1.2 Previous Work.......................................... 6
1.3 Our Contributions...................................... 8
1.4 Organization of the Thesis............................. 9
Chapter 2. Preliminaries 10
Chapter 3. 3D-subTCG for Temporal Floorplanning 13
3.1 Review of TCG.......................................... 13
3.2 3D-subTCG.............................................. 15
Chapter 4. Temporal Floorplanning Algorithm 21
4.1 Reduction Edge Identification.......................... 21
4.2 Solution Perturbation.................................. 22
4.2.1 Rotation......................................... 23
4.2.2 Move............................................. 23
4.2.3 Swap............................................. 23
4.2.4 Reverse.......................................... 25
4.2.5 Transpositional Move............................. 25
4.3 Feasibility Detection.................................. 27
4.4 The Algorithm.......................................... 30
Chapter 5. Experimental Results 32
Chapter 6. Concluding Remarks 40
Bibliography

[1] Atmel, "AT6000 FPGA Configuration Guide," Atmel, Inc.
[2] K. Bazargan, R. Kastner, and M. Sarrafzadeh,
"Fast Template Placement for Reconfigurable Computing Systems,"
IEEE Design & Test of Computers, vol.17, no. 1, pp. 68--83, Mar. 2000.
[3] J. E. Beasley,
``An Exact Two-Dimensional Non-Guillotine Cutting Stock Tree Search Procedure,''
Operations Research, vol.33, no. 1, pp. 49--64, 1985.
[4] T. Cormen, C. Leiserson, and R. Rivest,
``Introduction to Algorithms,''
McGraw-Hill Book Company, 1990.
[5] W. L. Chen, and T. M. Hsieh,
``A Spaceplan Algotithm Using Sequence Triplet Representation,''
Chung Yuan Journal, vol.30, no. 1, pp. 99--104, Mar. 2002.
[6] S. P. Fekete, E. K\"{o}hler, and J. Teich,
``Optimal FPGA Module Placement with Temporal Precedence Constraints,''
Proc. DATE, pp. 658-665, Mar. 2001.
[7] S. P. Fekete, and J. Schepers,
``On more-dimensional packing III: Exact Algorithms,''
ZPR Technical Report 97-290 1997.
[8] M. Gokhale, B. Holmes, A. Kopster, D. Kunze, D. Lopresti,
S. Lucas, R. Minnich, and P. Olsen,
``Splash: A Reconfigurable Linear Logic Array,''
International Conference on Parallel Processing, pp. 526--532, 1990.
[9] S. Hauck,
``The Roles of FPGAs in Reprogrammable Systems,''
Proc. of the IEEE, vol.86, no. 4, pp. 615--639, Apr. 1998.
[10] S. Hauck, Z. Li, and E.J. Schwabe,
``Configuration Compression for the Xilinx XC6200 FPGA,''
Proc. of the IEEE Symposium on FPGAs for Custom Computing Machines, pp. 138--146, 1998.
[11] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi,
``Optimization by Simulated Annealing,''
Science, vol. 220, no. 4598, pp.671--680, May, 1983.
[12] E. Lawler,
Combinatorial Optimization: Networks and Matroids,
Holt, Rinehart, and Winston, 1976.
[13] J.-M. Lin and Y.-W Chang,
``TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,''
Proc. DAC, pp. 764--769, June 2001.
[14] J.-M. Lin, H.-L Cheng and Y.-W. Chang,
``Arbitrary Convex and Concave Rectilinear Module Packing Using TCG,''
Proc. DATE, pp. 69--75, March 2002.
[15] J. Teich, S. P. Fekete, and J. Schepers,
``Compile-Time Optimization of Dynamic Hardware Reconfigurations,''
Proc PDPTA, pp. 1097--1103, June 1999.
[16] S. Trimberger,
``A Time-Multiplexed FPGA,''
Proc. FCCM'97.
[17] Xilinx,
``XC6200 Field Programmable Gate Arrays Data Sheet,''
Xilinx, Inc., Oct. 1996.
[18] Xilinx,
``XAPP151 Virtex Series Configuration Architecture User Guide v1.5,''
Xilinx, Inc., Sep. 2000.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文