用于时分复用技术的多阶段协同优化FPGA布线方法  

Multi-Stage Co-Optimization FPGA Routing for Time-Division Multiplexing Technique

作　　者：刘耿耿[1,2] 许文霖 周茹平 徐宁 LIU Genggeng;XU Wenlin;ZHOU Ruping;XU Ning(College of Computer and Data Science,Fuzhou University,Fuzhou 350116,China;Fujian Key Laboratory of Network Computing and Intelligent Information Processing(Fuzhou University),Fuzhou 350116,China;School of Information Engineering,Wuhan University of Technology,Wuhan 430070,China)

机构地区：[1]福州大学计算机与大数据学院,福州350116 [2]福建省网络计算与智能信息处理重点实验室,福州350116 [3]武汉理工大学信息工程学院,武汉430070

出　　处：《电子与信息学报》2023年第9期3430-3438,共9页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61877010)。

摘　　要：时分复用(Time-Division Multiplexing,TDM)技术被广泛地运用于解决IO瓶颈问题,以提高现场可编程门阵列(Field Programmable Gate Array,FPGA)系统的可布线性,但TDM比率的增大会导致系统时延的显著增加。因此,为了优化FPGA系统时延以及可布线性,该文提出一种用于时分复用技术的多阶段协同优化FPGA布线(Multi-Stage Co-Optimization FPGA Routing,MSCOFRouting)方法。首先,设计自适应布线算法,以减少布线拥塞情况,提高可布线性,解决FPGA间的布线优化问题,为后续的TDM比率分配提供高质量的布线结果。其次,为了避免因大规模线网组的TDM比率过大而导致系统时延劣化的情况,提出基于拉格朗日松弛(Lagrangian Relaxation,LR)的TDM比率分配算法,为布线图的边分配系统时延更小的初始TDM比率。此外,为了进一步减小最大线网组的TDM比率,通过一种多层次的TDM比率优化算法,缩减线网组和FPGA连接对的TDM比率。同时,为了提高MSCOFRouter的运行效率,在上述3个算法中使用多线程并行化方法,有效缩减运行时间。实验结果表明,MSCOFRouting可以获得满足TDM比率约束的结果,取得同类工作中最佳的布线优化结果和TDM比率分配结果。Time-Division Multiplexing(TDM)technology is widely applied to solving the IO limitation problem to improve the routability of FPGA system.However,the increase of the TDM ratio leads to a significant increase in system delay.Therefore,a Multi-Stage Co-Optimization FPGA routing(MSCOFRouting)for Time-Division Multiplexing is proposed in this paper to optimize the system delay and the routability of FPGA system.First,an adaptive routing algorithm is proposed to reduce routing congestion,improve the routability,solve the routing optimization problem between FPGAs,and provide high-quality routing results for subsequent TDM ratio assignment.Second,to avoid the delay degradation caused by excessive TDM ratio of large-scale net groups,a TDM ratio assignment algorithm based on Lagrangian relaxation is utilized to assign the initial TDM ratio with a smaller delay to the edge distribution system of the routing graph.In addition,a multi-level TDM ratio optimization algorithm is used to reduce the TDM ratios of the net group with maximum TDM ratios.The TDM ratio reduction is employed for the net group and the FPGA connection pair.Meanwhile,a multi-thread parallelization method is integrated into the three algorithms above to improve further the efficiency of MSCOFRouter.Experiments show that MSCOFRouting can obtain the results satisfying the TDM ratio constraint,and achieve the best routing optimization results and TDM ratio assignment results.

关 键 词：FPGA系统 逻辑验证 时分复用 布线 拉格朗日松弛 

分 类 号：TN43[电子电信—微电子学与固体电子学]