面向大规模FPGA的粗粒度并行布线方法研究

田春生; 陈雷; 王硕; 周婧; 王卓立; 张瑶伟

doi:10.20193/j.ices2097-4191.2025.0024

PDF(6548 KB)

集成电路与嵌入式系统 ›› 2025, Vol. 25 ›› Issue (6) : 68-77. DOI: 10.20193/j.ices2097-4191.2025.0024

FPGA前沿技术与应用研究专刊

面向大规模FPGA的粗粒度并行布线方法研究

作者信息 +

Research on coarse-grained parallel routing method for large-scale FPGAs

Author information +

文章历史 +

摘要

针对大规模FPGA布线过程中存在的资源开销与内存占用过大、布线算法求解效率低等问题,提出了一种资源友好型的面向大规模FPGA的粗粒度并行布线方法。首先,提出了非侵入式的数据优化技术,以减少因布线资源图而导致的资源开销与内存占用,解决因FPGA规模增大而导致的内存空间爆炸问题,为布线方法提供数据基座。其次,提出了自适应负载均衡以及高扇出线网划分技术,以解决粗粒度并行布线方法并行度低的问题,提升布线方法求解效率。实验结果表明,所提出的面向大规模FPGA的粗粒度并行布线方法可以在降低资源消耗与内存占用90%的情况下,获得3.18倍的运行时间加速比,而不会对线长与关键路径实验等性能指标造成影响。

Abstract

Aiming at the problems such as excessive resource overhead, high memory consumption, and low routing efficiency in the routing process of large-scale FPGAs, a resource-friendly coarse-grained parallel routing method tailored for large-scale FPGAs is proposed. First, a non-intrusive data optimization technique is proposed to reduce the resource overhead and memory consumption caused by the routing resource graph, addressing the memory explosion problem resulting from the increasing scale of FPGAs and providing a data foundation for the routing method. Second, adaptive load balancing and high-fanout net partitioning techniques are introduced to tackle the low parallelism in coarse-grained parallel routing, thereby improving the overall routing efficiency. The experimental results show that the proposed coarse-grained parallel routing method for large-scale FPGAs can achieve a 3.18× speedup in runtime while reducing resource and memory consumption by 90%, without compromising performance metrics such as wirelength and critical path delay.

导出引用

田春生, 陈雷, 王硕, 等. 面向大规模FPGA的粗粒度并行布线方法研究[J]. 集成电路与嵌入式系统. 2025, 25(6): 68-77 https://doi.org/10.20193/j.ices2097-4191.2025.0024

TIAN Chunsheng, CHEN Lei, WANG Shuo, et al. Research on coarse-grained parallel routing method for large-scale FPGAs[J]. Integrated Circuits and Embedded Systems. 2025, 25(6): 68-77 https://doi.org/10.20193/j.ices2097-4191.2025.0024

中图分类号： TN47 (大规模集成电路、超大规模集成电路)

参考文献

列表( 原文顺序 | 文献年度倒序 | 文中引用次数倒序 ) 可视化分析

[1]	田春生, 陈雷, 王源, 等. 基于图神经网络的电子设计自动化技术研究进展[J]. 电子与信息学报, 2023, 45(9):3069-3082. TIAN C S, CHEN L, WANG Y, et al. A survey for electronic design automation based on graph neural network[J]. Journal of Electronics & Information Technology, 2023, 45(9):3069-3082. (in Chinese) 本文引用 [1]

[2]	田春生, 陈雷, 王源, 等. 基于机器学习的FPGA电子设计自动化技术研究综述[J]. 电子与信息学报, 2023, 45(1):1-13. TIAN C S, CHEN L, WANG Y, et al. A survey on FPGA electronic design automation technology based on machine learning[J]. Journal of Electronics & Information Technology, 2023, 45(1):1-13. (in Chinese) 本文引用 [1]

[3]	高帅. 28 nm SRAM型FPGA单粒子多位翻转和瞬态效应研究[D]. 北京: 中国科学院大学, 2023. GAO S. Study of single-event multiple upset and transient effect on 28nm SRAM-based FPGA[D]. Beijing: University of Chinese Academy of Sciences, 2023. (in Chinese) 本文引用 [1]

[4]	VERCRUYCE D, VANSTEENKISTE E, STROOBANDT D. Croute:a fast high-quality timing-driven connection-based FPGA router[C]// 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM),San Diego,CA,USA, 2019:53-60. 本文引用 [4]

[5]	MURRAY K E, ZHONG S, BETZ V. AIR:A fast but lazy timing-driven FPGA router[C]// 2020 25th Asia and South Pacific Design Automation Conference(ASP-DAC),Beijing,China, 2020:338-344. 本文引用 [3]

[6]

田春生, 陈雷, 王源, 等. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5):1243-1254.doi: 10.12263/DZXB.20210637.

摘要

随着大规模集成电路器件复杂度与容量的不断提升，现场可编程门阵列（Field Programmable Gate Array, FPGA）以高度的并行、可定制和可重构的特性得到了广泛的关注与应用. 在制约FPGA发展的众多因素中，最为关键的便是电子设计自动化（Electronic Design Automation, EDA）技术，作为FPGA EDA流程中的关键环节，布局和布线技术的研究对于FPGA的重要性不言而喻. 本文综述了面向FPGA的布局和布线技术，包括基于划分的布局、基于启发式的布局、基于解析式的布局、FPGA串行布线和FPGA并行布线等技术，分析对比了不同技术方法的优缺点，在此基础上，本文还展望了未来FPGA布局和布线技术的发展趋势，将为FPGA未来健康可持续的发展提供有力支撑.

TIAN

C S

, CHEN

, WANG

, et al. Review on Technology of Placement and Routing for the FPGA[J]. Acta Electronica Sinica, 2022, 50(5):1243-1254. (in Chinese)

本文引用 [2]

[7]	STOJILOVIC M. Parallel FPGA routing: survey and challenges[C]// 2017 27th International Conference on Field Programmable Logic and Applications (FPL),Ghent,Belgium, 2017:1-8. 本文引用 [2]

[8]	HOO H C, HA YAJUN, KUMAE A. ParaFRo:a hybrid parallel FPGA router using fine grained synchronization and partitioning[C]// 2016 26th International Conference on Field Programmable Logic and Applications (FPL),Lausanne,Switzerland, 2016:1-11. 本文引用 [1]

[9]	HOO H C, KUMAR A. ParaDiMe:a distributed memory FPGA router based on speculative parallelism and path encoding[C]// 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2017:172-179. 本文引用 [1]

[10]	ROGERS S E. Implementation of an API for and the folding of FPGA Routing Resource Graphs in VTR[D]. Rexburg: Brigham Young University, 2022. 本文引用 [2]

[11]	CHIN S Y L, WILTON S J E. Static and dynamic memory footprint reduction for FPGA routing algorithms[J]. ACM Transactions on Reconfigurable Technology and Systems, 2009, 1(4):1-20. 本文引用 [2]

[12]	CHIN S Y L, WILTON S J E. Memory Footprint Reduction for FPGA Routing Algorithms[C]// 2007 International Conference on Field-Programmable Technology,Kitakyusyu,Japan, 2007:1-8. 本文引用 [2]

[13]	KENNINGS A. Simple FPGA routing graph compression[J]. arXiv preprint arXiv:1811.04749, 2018. 本文引用 [2]

[14]

麦景, 王嘉睿, 邸志雄, 等. OpenPARF:基于深度学习工具包的大规模异构FPGA开源布局布线框架[J]. 电子与信息学报, 2023, 45(9):3118-3131.

MAI

, WANG

J R

, DI

Z X

, et al. OpenPARF:an open-source placement and routing framework for large-scale heterogeneous FPGAs with deep learning toolkit[J]. Journal of Electronics & Information Technology, 2023, 45(9):3118-3131. (in Chinese)

本文引用 [2]

[15]	王德奎. FPGA高效布线方法研究[D]. 西安: 西安电子科技大学, 2020. WANG D K. Research on Efficient FPGA Routing Algorithm[D]. Xi`an: Xidian University, 2020. (in Chinese) 本文引用 [3]

[16]	VANSTEENKISTE E, BRUNEEL K, STROOBANDT D. A connection-based router for FPGAs[C]// 2013 International Conference on Field-Programmable Technology (FPT),Kyoto,Japan, 2013:326-329. 本文引用 [1]

[17]	GORT M, ANDERSON J H. Deterministic multi-core parallel routing for FPGAs[C]// 2010 International Conference on Field-Programmable Technology,Beijing,China, 2010:78-86. 本文引用 [1]

[18]	SHEN M H, LUO G J. Accelerate FPGA routing with parallel recursive partitioning[C]// 2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD),Austin,TX,USA, 2015:118-125. 本文引用 [1]

[19]	HOO C H, KUMAR A. ParaDRO:a parallel deterministic router based on spatial partitioning and scheduling[C]// 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays,New York,USA, 2018:66-76. 本文引用 [1]

[20]	ZHOU Y, VERCRUYCE D, STROOBANDT D. Accelerating FPGA Routing Through Algorithmic Enhancements and Connection-aware Parallelization[J]. ACM Transactions on Reconfigurable Technology and Systems, 2020, 13(4):1-26. 本文引用 [1]

[21]	MOCTAR Y O D, BRISK P. Parallel FPGA routing based on the operator formulation[C]// Proceedings of the 51st Annual Design Automation Conference,San Francisco,CA,USA, 2014:1-6. 本文引用 [1]

[22]	SHEN M H, LUO G J, XIAO N. Explorting GPU-accelerated routing for FPGAs[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(6):1331-1445. 本文引用 [1]

[23]	KOSAR F. A net-decomposing parallel field-programmable gate array router[D]. Toronto: University of Toronto, 2023. 本文引用 [1]

[24]	BARMAN R, BADADE S, DESHPANDE S, et al. Lossless data compression method using deep learning[C]// Machine Intelligence and Smart Systems.Algorithms for Intelligent Systems.Springer, Singapore, 2022. 本文引用 [1]