高级检索
王德奎, 张丽丽, 陆旭. 轻量化FPGA布线路径搜索算法[J]. 计算机辅助设计与图形学学报, 2023, 35(5): 789-795. DOI: 10.3724/SP.J.1089.2023.19420
引用本文: 王德奎, 张丽丽, 陆旭. 轻量化FPGA布线路径搜索算法[J]. 计算机辅助设计与图形学学报, 2023, 35(5): 789-795. DOI: 10.3724/SP.J.1089.2023.19420
Wang Dekui, Zhang Lili, Lu Xu. Light Search Algorithm for FPGA Routing Path[J]. Journal of Computer-Aided Design & Computer Graphics, 2023, 35(5): 789-795. DOI: 10.3724/SP.J.1089.2023.19420
Citation: Wang Dekui, Zhang Lili, Lu Xu. Light Search Algorithm for FPGA Routing Path[J]. Journal of Computer-Aided Design & Computer Graphics, 2023, 35(5): 789-795. DOI: 10.3724/SP.J.1089.2023.19420

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

Light Search Algorithm for FPGA Routing Path

  • 摘要: 针对FPGA布线耗时较长的问题,提出一种基于最优节点预测的轻量化FPGA布线路径搜索算法.该算法通过预测最优布线资源节点,在搜索最优布线路径时只对最优节点进行详细计算、分析,无须搜索其他节点,从而提高搜索速度;当轻量化搜索失败时,以全局最优节点为源点重新进行轻量化搜索,提高全局搜索能力;在寻找全局最优节点时,只对可能出现在最优路径上的次优节点进行详细计算分析,减少无效计算.使用VTR标准电路对所提算法和VPR 8.0进行测试,并从布线所需时间和结果质量2个方面进行比较.实验结果表明,与VPR 8.0中布线路径搜索算法相比,所提算法在保证布线结果质量基本不变的情况下,将搜索的布线资源节点数量减少41.8%,可节省31.3%的运行时间.

     

    Abstract: 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.

     

/

返回文章
返回