Circuit Partitioning for Huge Logic Emulation Systems

Given a huge system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGAs for logic emulation. We first devise a Local Ratio-cut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed to replace the widely adopted recursive partitioning paradigm. Experimental results show that our approach achieves significant improvement in a much shorter run time compared to the recursive Fiduccia-Mattheyses approach on large designs. For example, on a benchmark of 160K gates and 90K nets, we reduced the number of FPGAs required by 29% and reduced the run time by 78%.