Time-Division Multiplexing Based System-Level FPGA Routing for Logic Verification

Multi-FPGA prototyping is widely used for modern VLSI verification, but the limited number of inter-FPGA connections in a multi-FPGA system may cause routing failures. As a result, the time-division multiplexing (TDM) technique is adopted to increase its resource utilization by transmitting multiple signals through the same routing channel. Due to the large signal delay between FPGA pairs, however, the performance of such a system greatly depends on the inter-FPGA routing quality. In this paper, we propose a TDM-based system-level routing algorithm to simultaneously minimize the maximum TDM (signal multiplexing) ratio and runtime, considering the crucial ratio constraints. By weighting the routing edges, we first model the net routing as a Steiner minimum tree (SMT) problem and solve it with an approximation algorithm with the performance bound 2(1 - 1/1), where l is the number of leaves in an optimal SMT. Then, a timing-driven assignment method is presented to evenly distribute the TDM ratio to routing signals, followed by a novel reassignment algorithm to efficiently handle unbalanced net groups. Finally, a ratio-aware refinement technique is employed to further improve the solution quality. Compared with the top-3 winners at the 2019 CAD Contest at ICCAD based on the contest benchmarks, experiment results show that our proposed algorithm achieves the best runtime and TDM ratio while satisfying all TDM constraints.