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 bipartite graph），給定不同的成本函數（cost function） 當作其連線（edge） ，求出一組最小配對（minimal matching）。我們設計三組不同型態的電 路，來測試我們的方法。由實驗結果可得知，我們的方法可達到縮短設計 流程及提高使用率，降低延遲等目的。 In this thesis we present a design method from RT level to Field Programmable Gate Arrays (FPGAs) . Not only datapath unit but also the control-path unit is considered in this system. Our goal is to find a placement method so that the placement time and routing time can be shortened. We propose a hierarchical placement methodology. We use the information after technology mapping of each RT component and available routing resource of FPGAs to determine the relative location of each RT component first. Our method ensures not only the design cycle is shorten but also better utiliz- ation of FPGA cell and timing constraint can be met.