轻量化FPGA布线路径搜索算法  

Light Search Algorithm for FPGA Routing Path

作　　者：王德奎 张丽丽 陆旭 Wang Dekui;Zhang Lili;Lu Xu(School of Information Science&Technology,Northwest University,Xi’an 710127;School of Computer Science and Technology,Xidian University,Xi’an 710071)

机构地区：[1]西北大学信息科学与技术学院,西安710127 [2]西安电子科技大学计算机科学与技术学院,西安710071

出　　处：《计算机辅助设计与图形学学报》2023年第5期789-795,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(62002290,62106199);陕西省教育厅一般项目(21JK0926)。

摘　　要：针对FPGA布线耗时较长的问题,提出一种基于最优节点预测的轻量化FPGA布线路径搜索算法.该算法通过预测最优布线资源节点,在搜索最优布线路径时只对最优节点进行详细计算、分析,无须搜索其他节点,从而提高搜索速度;当轻量化搜索失败时,以全局最优节点为源点重新进行轻量化搜索,提高全局搜索能力;在寻找全局最优节点时,只对可能出现在最优路径上的次优节点进行详细计算分析,减少无效计算.使用VTR标准电路对所提算法和VPR 8.0进行测试,并从布线所需时间和结果质量2个方面进行比较.实验结果表明,与VPR 8.0中布线路径搜索算法相比,所提算法在保证布线结果质量基本不变的情况下,将搜索的布线资源节点数量减少41.8%,可节省31.3%的运行时间.In order to address the long runtime issue of FPGA routing,a light search algorithm for FPGA routing path is presented.By predicting optimal nodes,the proposed algorithm computes and analyzes only the optimal nodes when searching for the shortest route,which improves the search efficiency.When the light search fails to find the sink,a new light search process is then started from the global optimal node,so as to improve the global search ability.In the search of global best nodes,only the suboptimal nodes that are promising to be on the lowest cost path are further analyzed which reduces the useless work.The proposed algorithm and VPR 8.0 are compared in terms of run-time and quality of results by using the VTR standard benchmark.Experimental results show that compared to the routing path searching algorithm in VPR 8.0,the proposed algorithm reduces the number of explored nodes by 41.8%,leading to a 31.3%runtime reduction.Meanwhile,the quality of results is basically unaffected.

关 键 词：现场可编程门阵列 布线算法 轻量化搜索 大规模电路 最短路径 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]