FPGA分割問題之研究

Abstract

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.