Abstract
在本篇論文中，我們提出一個從RTL 對映到可程式化陣列邏輯閘（Field Programmable Gate Array） 之自動化系統。 我們建立一個RT的資料庫，利用該資料庫所提供的訊息，配合適當的定位（Placement） 演算法，達到使可程式化陣列邏輯閘之設計時間縮短，提高其使用率，及使該設計之延遲（delay） 降低之目的。可程式化陣列邏輯閘（FPGA）因設計流程簡單，且製造過程快速，近年來廣泛的被使用在電路原型（prototype）上。但在設計時定位（placement） 及繞線（routing）須花費許多時間，故我們利用電路在RTL（Register Tran-sfer Level）之特性來定位，RTL 因為有模組的觀念，可以降低定位問題的複雜度（complexity）。在可程式化陣列邏輯閘（FPGA）的設計方法中，主要分為下列三個步驟：一．映成技術（Technology Mapping）：映成技術是運用數個可程式邏輯區塊（Configurable Logic Block） 來涵蓋整個線路。映成技術的好壞可能影響所須區塊的數目，或整個線路的延遲時間。二．定位（Placement）：定位是將可程式邏輯區塊擺置到可程式陣列邏輯閘上適當的位置。好的定位應確保完全的繞線及延遲的降低。三．繞線（Routing）：繞線則是將各可程式邏輯區塊間相同的信號（signal）連接在一起，完全的繞線是設計的最基本要求，而延遲的多寡則是繞線好壞評估。我們使用二種定位演算法來完成我們的方法：一．利用線性定位（Linear Placement）演算法決定RT組件間的相對位置。線性定位的目的是減少各組件間的切線（cut） 數目，因為可程式陣列邏輯閘的繞線資源（routing resource）有限，減少切線可提高使用率。二．利用二部份配對（Bipartite Matching）演算法，來決定RT內部可程式邏輯區塊（CLB） 的位置。建立一個完全二部份圖型（complete bipartitegraph），給定不同的成本函數（cost function） 當作其連線（edge），求出一組最小配對（minimal matching）。我們設計三組不同型態的電路，來測試我們的方法。由實驗結果可得知，我們的方法可達到縮短設計流程及提高使用率，降低延遲等目的。In this thesis we present a design method from RT level toField Programmable Gate Arrays (FPGAs) . Not only datapath unitbut also the control-path unit is considered in this system.Our goal is to find a placement method so that the placementtime and routing time can be shortened. We propose ahierarchical placement methodology. We use the informationafter technology mapping of each RT component and availablerouting resource of FPGAs to determine the relative locationof each RT component first. Our method ensures not only thedesign cycle is shorten but also better utiliz- ation of FPGAcell and timing constraint can be met.