用戶可規劃閘陣列之邏輯合成與分割

Abstract

本論文中將探討用戶可規劃閘陣列之邏輯合成 (logic synthesis)、技術 映射(technology mapping) 及分割 (partitioning) 的相關問題，並提 出解決的演算法。在查對表式用戶可規劃閘陣列 (LUT-based FPGA) 的邏 輯合成問題上，本論文提出了一種以 Roth-Karp 分解法為基礎的演算法 來將給定的邏輯電路分解成可實作形式。在輸入變數的分割問題上，本論 文提出了一個可於Roth-Karp 分解法中選擇一個優良束縛集合 (boundset) 之啟發式演算法。這個演算法已被整合入一個新的分解流程 方案。在相容集合(compatible class)的編碼問題上，本論文將其視為一 個符號輸出 (symbolic-output)的編碼問題，而且發展出對應的解決演算 法。這個演算法被設計成可完全的發揮具有兩個輸出端 (two-output) 查 對表架構之特色。針對時間驅動式 (timing-driven) 之技術映射問題， 本論文提出了一個反覆式的面積/速度取捨 (area/performance trade- off) 演算法。這個方法首先找到一個面積最佳化且同時考慮電路階層 (level-considered) 的起始網路，然後在以一個反覆式的演算法來求得 一個包含完整面積/速度取捨映射解之解集合。實驗結果證明這個演算法 不僅可提供優秀的面積/速度取捨曲線，尚可提供可媲美大部分現存之階 層最佳化演算法同等品質的解。針對有容量限制 (capacity constraint) 的速度驅動式 (performance-driven) 電路叢集(circuit clustering) 問題，本論文提出了一個反覆式面積/延遲取捨 (area/delaytrade-off) 演算法。這個方法首先找出一個面積最佳化且同時考慮電路延遲的無迴路 叢集解。然後一個再叢集 (reclustering) 演算法被使用來求得一個包含 完整面積/延遲取捨叢集解的解集合。實驗結果證明由這個演算法所求得 之延遲最佳解，在電路延遲的表現上可媲美現存的延遲最佳化演算法所得 之解，但是其所需要的額外面積 (area overhead) 郤可顯著地減少。當 容量及接腳數同時都有限制時，這個演算法依然能夠提供完整的面積/延 遲取捨解集合。因此，這個演算法可以容易地運用於多用戶可規劃閘陣列 系統 (multi-FPGAsystem) 中，提供面積/延遲取捨的作業功能。 This dissertation explores the issues of logic synthesis, technologymapping and partitioning for field programmable gate arrays andproposes the corresponding algorithms to solve them. On thesynthesis of LUT-based FPGAs, an improved algorithm based on Roth-Karp decomposition is proposed to make the given logic networksfeasible. On the input variable partitioning, a novel heuristicalgorithm, which selects a good bound set in Roth- Karpdecomposition, is presented. And this algorithm is incorporatedinto a new decomposition flow scheme. The issue of compatible classencoding is formulated as a symbolic-output encoding problem andthen an encoding algorithm is developed to specifically solve it.This new encoding algorithm is designed to specifically exploit thefeature of the two-output LUT architecture. For timing-driventechnology mapping, an iterative area/performance trade-offalgorithm is presented. The approach begins with finding a level-considered area-optimized initial network for the given circuit. Aniterative algorithm is then applied to get the set of complete area/level trade-off mapping solutions. Experimental results show thatthis algorithm can provide not only an excellent area/level trade-off curve but also the level-optimized solutions that competefavorably with those provided by most existing level optimizationalgorithms. For performance-driven circuit clustering with capacityconstraint, an iterative area/delay trade-off clustering algorithmis proposed. The approach begins with finding an initial delay-considered area-optimized acyclic clustering solution. Thereclustering algorithm is then applied to get the set ofcomprehensive area/delay trade-off clustering solutions. Experimental results show that the delay-optimized solutionsprovided by this algorithm have almost the same performance withthat of the delay optimal solutions provided by the existing delayoptimal algorithm while the required area overhead is significantlyreduced. When both capacity and pin constraints are concerned, thisalgorithm is still capable of providing comprehensive area/delaytrade-off clustering solutions. Hence, this algorithm can be easilyapplied to performarea/delay trade-off operations for multi-FPGAsystems.