Performance-Driven Simultaneous Partitioning and Routing for Multi-FPGA Systems

A multi-FPGA system consists of multiple FPGAs connected by physical wires, and a circuit is partitioned to fit each FPGA and routed on the system by such physical wires. Due to the limited numbers of input/output (I/O) pins in an FPGA, however, not all signals can be transmitted between FPGAs directly. Moreover, the routing resource may not be sufficient to accommodate many cross-FPGA signals from circuit partitioning. As a result, input/output time-division multiplexing (TDM) is introduced to send a group of cross-FPGA signals in a routing channel with a timing penalty. To optimize the performance of such a system, we shall develop a simultaneous partitioning and routing algorithm considering the timing penalty caused by I/O TDM. Considering the TDM delay penalty, we propose a simultaneous partitioning and routing algorithm to remedy the insufficiency of the two-stage flow of partitioning followed by routing. Our algorithm consists of two major steps: (1) a novel routing-aware partitioning framework to obtain an initial solution considering irregular, asymmetric connections, and (2) a partition-aware routing scheme to optimize routing in each partitioning pass. Experimental results show that our proposed algorithm can achieve better timing than the classical flow.