FPGA-Oriented Routing Algorithm Considering Internal and External Structures

To address the mismatch between the number of inter-FPGA signals and the limited number of available I/O pins in multi-FPGA prototyping systems, time-division multiplexing(TDM) is used to improve the utilization of inter-FPGA interconnect resources. However, TDM introduces additional timing delay overhead, thereby extending the system clock period and reducing the system operating frequency. To overcome this limitation, this paper proposes an FPGA-oriented routing algorithm considering internal and external structures to shorten the system clock period and improve the system operating frequency. First, a Lagrangian relaxation-based initialization strategy for TDM ratios is proposed and the Lagrange multipliers are iteratively updated through an alternative sub-gradient method to improve convergence efficiency and obtaining a high-quality continuous initial solution. Subsequently, a greedy discretization method is proposed to convert the continuous initial solution into TDM ratios that satisfy the problem constraints, while reducing TDM overhead of critical interconnects through fine-grained legalization. Finally, a reassignment strategy is proposed for critical nets to lower multiplexing delay without violating feasibility, which in turn shortens the system clock period. Experimental results demonstrate that the proposed algorithm achieves a better TDM ratio assignment solution, shortens the system clock period and thereby improves the system operating frequency while satisfying all TDM constraints.