以三維子遞移封閉圖處理時序性平面規劃

Abstract

現場可程式化邏輯閘陣列 (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.