Abstract
在這篇論文中, 我們以二元決策圖(Binary Decision Diagram)為基礎, 提出兩種方案來解決可程式化閘陣積體電路(Field Programmable Gate Array)之映成技術(technology mapping)。分割及解碼方式( Cut_and_encode)是以Roth_Karp分解法( Roth_Karp decomposition)為理 論基礎, 而替換法(Substitution method)是以布林代數替換(Boolean substitution) 為基礎。最後, 做一些實驗來測試我們的結果。我們發現 資料路徑邏輯( data path logic)比較適用用我們的方法。近年來可程式 化閘陣積體電路廣泛的被使用在電路原型( prototype)的製造上, 但以往 以單元為基礎(cell-based)的映成技術並不適用在這種機積體電路上, 所 以我們必需去發展新的映成技術。而基於二元決策圖在基本架構上的簡單 性, 我們提出以二元決策圖為基礎之可程式化閘陣積體電路之映成技術。 在這過程中,我們所考慮的是如何去減少在映成之後所需的可規劃邏輯區 塊( Configurable Logic Block CLB)的數目。我們介紹以前在可程式化 閘陣積體電路上以減少所需的可規劃邏輯區塊為導向的映成技術所作的相 關研究。他們分別是chortle, chortle-crf, mis-pga, Xmap, VISMAP, BDDsyn, MapBDD 等等。這些方法除了Xmap用If-Then-Else DAG, MapBDD 和 BDDsyn 用BDD,其餘的方法都是用布林網路(Boolean network)為其架 構。二元決策圖(BDD)是一種有根有向無迴圈圖, 它有兩種節點：非終端 節點與終端節點。終端節點也有兩種：０節點及１節點。它有兩種邊：０ 邊及１邊。每一非終端節點代表一個布林函數。我們將系統與ＳＩＳ(U. C. Berkeley 所發展的軟體)相結合。利用ＳＩＳ對布林網路(Boolean network)做一些化簡。接著分別用分割及解碼法, 替換法, 和兩種混合法 對一組布林網路(Boolean network)做映成技術(technology mapping)。 本篇論文介紹兩種方法來解決可程式化閘陣積體電路中的映成技術問題( technology mapping)。一種是分割及解碼法, 另一種是布林替換法。兩 種方法都以二元決策圖做為資料結構。我們仍能以下列方法來改進我們的 演算法：在替換法中,用好的方法來找替換節點。使用VISMAP中所提的方 法做為後續處理。 Field Programmable Gate Array(FPGA) is a new technology that provides users the programmability in the field. The short rapid prototyping and low manufacturing cost have made FPGA an important technology for VLSI ASIC design. There are mainly two types of FPGA architecture : one is based on table lookup (e. g., Xilinx), the other is based on multiplexers (e.g., Actel). In this thesis, we focus on the Table Look_Up(TLU) architecture. A basic cell in the TLU architecture is called a configurable logic block (CLB). It can realize any function of up to k inputs. In XC3000 series, k is 5. The interconnections between the logic blocks consists of metal segments joined by program-controlled pass transistors. The logic functions and the interconnections are determined by the configuration program data stored in the internal static memory cells. Technology mapping is a process of transforming technology independent Boolean network into technology-based circuit. For TLU-based FPGAs, a technology mapper decomposes the Boolean network into a set of subnetworks such that each subnetwork is implemented using a CLB. Since a traditional technology mapper needs an explicit library definition, it is not feasible to enumerate all the functions that a RAM cell can perform. For example, in the Xilinx 3000 series, each CLB has 5 inputs, so we must have 2^(2^5) explicit library entries if we use the traditional technology mapper. Thus, the traditional technology mapper is not suitable for FPGA mapping. We propose a new technology mapper in this thesis. Two techniques are used. One is based on Roth_Karp decomposition and the other Boolean substitution. Both techniques are developed on the Binary Decision Diagrams.