FPGA 分割問題之研究

Abstract

在本篇論文中，我們探討分割用戶可程式邏輯閘陣列(FPGA)關於面積方面 的兩個方法。我們先討論遞迴式的 Fiduccia-Mattheyses 演算法 (RFM) ，這是一種很直接且快速的方法。這個方法利用 FM 演算法反覆地切割輸 入電路，但是結果不是很好。然後，我們提出一個藉由不斷地分裂及合併 部份電路的加強型演算法。閘數最少的群當作選取其他群的種子，然後把 選到的群打散並重新分割。和分割整個電路比較，複雜度低，有更大的機 率求得好的結果。我們實做 RFM 和這個加強型演算法且用數個電路測試 。實驗證實加強型演算法的結果比 RFM 好。 In this thesis, two important methods in Field Programming Gate Array (FPGA) partitioning for area minimization are investigated. The first method is the recursive Fiduccia- Mattheyses heuristic (RFM) which is a straightforward and fast method. This method uses the FM heuristic repeatedly to cut the input netlist. However, the result isn't good. An improvement scheme by repeatedly splitting and merging part of the input netlist is proposed. The cluster with the fewest gates is the seed for selecting other clusters. Then we merge selected clusters and repartition them. As compared with partitioning the whole netlist, the complexity of the problem is reduced, and as a result, the probability of getting better results is increased. Both RFM and the proposed scheme are implemented and tested by benchmarks from MCNC. As we expect, the experimental results show that the proposed scheme archives much improvement compare to RFM.