Multi-way partitioning for minimum delay for look-up table based FPGAs

Abstract

In this paper we present a set cover based approach (SCP) to multi-way partitioning for minimum delay for Look-Up Table SCP minimizes the number of chip-crossings on each circuit path with minimum logic duplication costs to achieve implementations with minimum delay and minimum number of chips. The overall complexity of SCP is (V 2 ). Experimental results demonstrate that SCP produces partitions that on the average 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 implementation of classical multi-way partitioning. SCP achieves this performance and compact packing at the cost of duplicating 13% of logic on the average. Additionally, in comparison with a lower bound we observe that SCP has produced near-optimal solutions.