Multi-way Partitioning for Minimum Delay for Look-up Table Based FPGAs

In this paper we present a set cover based approach (SCP) to multi-way partitioning for minimum delay for Look-Up Table based FPGAs. SCP minimizes the num-ber of chip-crossings on each circuit path with minimum logic duplication costs to achieve implementations with minimum delay and minimum number of chips. The over-all complexity of SCP is (V 2). Experimental results demonstrate that SCP produces partitions that on the av-erage have 14 % fewer chips, 28 % fewer pins, and 93% fewer chip-crossings on each circuit path compared to ANN which is a simulated annealing based implementa-tion of classical multi-way partitioning. SCP achieves this performance and compact packing at the cost of duplicat-ing 13 % of logic on the average. Additionally, in compari-son with a lower bound we observe that SCP has produced near-optimal solutions.