Cost minimization of partitioned circuits with complex resource constraints in FPGAs (poster abstract)

ABSTRACT

In this paper, we formulated a new cost minimization partition problem with complex resource constraints in large FPGAs and proposed a maximum matching and ILP based algorithm to solve it. In traditional partitioning methods, one starts with a random initial partition of the circuit. Instead, we proposed a maximum matching based algorithm to generate a feasible initial partition efficiently. The proposed problem is formulated in ILP model. The ILP solver, LINGO, is employed to find the number of FPGA chips of each type to minimize the total cost. Further, a new vertex ordering matching algorithm is proposed to get a smaller cut-size partition. Experimental results on the MCNC LGSynth91 benchmark show that circuit partition with multiple resource types has 20% lower cost on average than that use simple resource type FPGA. The proposed vertex ordering method reduces the cost by 19% compared with the method without vertex ordering considerations.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Theory