Lagrangian Relaxation-Based Time-Division Multiplexing Optimization for Multi-FPGA Systems

<?tight?>To increase the resource utilization in multi-FPGA (field-programmable gate array) systems, time-division multiplexing (TDM) is a widely used technique to accommodate a large number of inter-FPGA signals. However, with this technique, the delay imposed by the inter-FPGA connections becomes significant. Previous research has shown that the TDM ratios of signals can greatly affect the performance of a system. In this article, to minimize the system clock period and support more practical constraints in modern multi-FPGA systems, we propose an analytical framework to optimize the TDM ratios of inter-FPGA nets. A Lagrangian relaxation-based method first gives a continuous result under relaxed constraints. A binary search--based discretization algorithm is then used to assign the TDM ratio of each net such that the resulting maximum displacement is optimal and all the constraints are satisfied. Finally, a swapping-based post refinement is performed to further optimize the TDM ratios. For comparison, we also solve the problem using linear programming (LP)--based methods, which have guaranteed error bounds to the optimal solutions. Experimental results show that our framework can achieve similar quality with much shorter runtime compared to the LP-based methods. Moreover, our framework scales for designs with over 45,000 inter-FPGA nets while the runtime and memory usage of the LP-based methods will increase dramatically as the design scale becomes larger.