FPGA-Par: An Efficient Algorithm for Elegant Partitioning in Multi-FPGA Systems

This work introduces FPGA-Par, an efficient graph partitioning algorithm for multi-FPGA systems. FPGA-Par utilizes an iterative balanced partitioning and supernodes transferring algorithm that transforms imbalanced partitioning problems into balanced ones, addressing the inefficiencies associated with traditional single-node movement methods, as well as eliminating the need for brute-force exploration of imbalance factors. This approach achieves partitions with flexible size ratios that satisfy resource constraints, resulting in improved partition quality. Experimental results demonstrate that FPGA-Par reduces time overhead by 55% compared to state-of-the-art imbalanced partitioning algorithms. Furthermore, it improves partition quality metrics, with Cut and Cut<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</inf> decreasing by 38% and 25%, respectively, and achieves a 1.25x increase in system frequency after mapping and routing on a multi-FPGA system.