用戶可程式邏輯閘陣列之資料流合成器

Abstract

本論文中，我們製作一個可應用於用戶可程式邏輯閘陣列上的資料流合成 器，我們在利用用戶可程式邏輯閘陣列設計資料流線路時，加速線路的產 生，並有效利用用戶可程式邏輯閘陣列的硬體資源以及得到較佳的結果。 在論文中，我們探討了： (1).如何建及選擇元件庫（Cell Library）及 其資料結構。 (2).輸入的語法及分析成所需格式。 (3).決定中間格式的 表示法及資料結構。 (4).元件（Cell）的排列演算法（Placement Algorithm）。 (5).元件的拉線演算法（Routing Algorithm）並決定能 不能成功。 (6).元件的接腳指定（Pin Assignment）。 (7).擴展成所需 位元數的線路和轉成用戶可程式邏輯閘陣列所需格式。由於資料流的位元 分割（Bitsliced ）特性，使得對稱式架構的二維排列和拉線問題減縮成 一維的問題。我們也想出一些有關排列演算法的架構，並比較它們的結果 。而拉線程式是用一個已發表的方法，稱之為大略展開圖（Coarse graph expansion）(CGE) ，再經過一些改變，成為一更改過的版本。目 前的系統，是以 Xilinx XC3000 系列晶片為主，將來，我們希望提升結 果到 Xilinx XC4000 系列晶片並擴展我們的演算法，成為解決二維排列 和拉線的問題。 In this thesis, we proposed and implemented some procedures to do the data path synthesis in Field Programmable Gate Arrays (FPGAs). This thesis involves the following issues : (1). How to build and select the cell library. (2). The input format. (3). To select the intermediate representation. (4). The algorithm of cell placement. (5). Select the routing algorithm and routability analysis. (6). Algorithm of pin assignment. (7). Transfer the result to the Xilinx's format. Due to the bit sliced nature of the data path,the two dimensional placing and routing problem of symmetrical architecture is reduced to a one dimensional one. We studied and implemented several placement algorithms and compared results. The router is using a modified version of a previously published method called Coarse graph expansion (CGE).The current system is deigned for Xilinx XC3000 FPGA chips. In the future, we hope to upgrade the result to XC4000 series and extend our algorithms to two dimensional placement and routing problems.