Abstract：FPGA routability prediction is of great significance for solving the optimization of physical design. We propose an FPGA routability prediction model based on complex networks and CBAM-CNN. During the placement phase, we extract circuit features and complex network features related to circuit congestion and map them to RGB images. We introduce an attention mechanism to enhance the importance of features. The experimental results show that the prediction accuracy is 98.03%, precision is 98.3%, sensitivity is 98.3%, specificity is 97.67%, and the Matthews correlation coefficient is 93.75%. The importance of complex network features in FPGA routability prediction is ranked in order of degree, strength, eigenvector, and betweenness. This proves the effectiveness and importance of complex network features in predicting FPGA routability.
聂廷远, 王艳伟, 聂晶晶, 刘鹏飞. 基于注意力机制和复杂网络的FPGA可布性预测[J]. 复杂系统与复杂性科学, 2026, 23(1): 53-59.
NIE Tingyuan, WANG Yanwei, NIE Jingjing, LIU Pengfei. Routability Prediction for FPGA Design Based on Complex Networks and Attention Mechanism[J]. Complex Systems and Complexity Science, 2026, 23(1): 53-59.
[1] MA Y, ZENG X, YU B. Methodologies for layout decomposition and mask optimization: a systematic review[C]// IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC). Abu Dhabi: IEEE, 2017: 1-6. [2] BOZORGZADEH E, MEMIK S, YANG X, et al. Routability-driven packing: metrics and algorithms for cluster-based FPGAs[J]. Journal of Circuits, Systems, and Computers, 2005, 13(1): 77-100. [3] WOOD R, RUTENBAR R. FPGA routing and routability estimation via Boolean satisfiability[J]. IEEE Transactions on Very Large Scale Intergation (VLSI) Systems, 1998, 6(2): 222-231. [4] QI Z, CAI Y, ZHOU Q. Accurate prediction of detailed routing congestion using supervised data learning[C]// Proceedings of the IEEE International Conference on Computer Design. Korea (South): IEEE, 2014: 97-103. [5] ZHOU Q, WANG X, QI Z, et al. An accurate detailed routing routability prediction model in placement[C]// Proceedings of the Asia Symposium on Quality Electronic Design (ASQED’15). Kuala Lumpur: IEEE, 2015: 119-122. [6] CHAN W T J, DU Y, KAHNG A B, et al. BEOL stack-aware routability prediction from placement using data mining techniques[C]// Proceedings of the International Conference on Computer Design (ICCD’16). Scottsdale: IEEE, 2016: 41-48. [7] XIE Z Y, HUANG Y H, FANG G Q, et al. RouteNet: routability prediction for mixed-size designs using convolutional neural network[C]// IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego: IEEE, 2018: 1-8. [8] AL-HYARI A, ABUOWAIMER Z, MARTIN T, et al. Novel congestion-estimation and routability-prediction methods based on machine learning for modern FPGAs[J]. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2019, 12(3): 1-25. [9] MARTIN T, SHAWKI A, GARY G. Effective machine-learning models for predicting routability during FPGA placement[C]// ACM/IEEE 3rd Workshop on Machine Learning for CAD (MLCAD). Raleigh: IEEE, 2021: 1-6. [10] SZENTIMREY H, AL-HYARI A, FOXCROFT J, et al. Machine learning for congestion management and routability prediction within FPGA placement[J]. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2020, 25(5): 1-25. [11] GUNTER A D, WILTON S J. A machine learning approach for predicting the difficulty of FPGA routing problems[C]// IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). Marina Del Rey: IEEE, 2023: 63-74. [12] ALHYARI A, SHAMLI A, ABUOWAIMER Z, et al. A deep learning framework to predict routability for FPGA circuit placement[C]// International Conference on Field Programmable Logic and Applications. New York: ACM, 2019: 1-8. [13] 董亚盼,高陈强,谌放,等.基于注意力机制的红外小目标检测方法[J].重庆邮电大学学报(自然科学版),2023,35(2):219-226. DONG Y P, GAO C Q, CHEN F, et al. Infrared small target detection method based on attention mechanism[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2023, 35(2): 219-226. [14] 郭明健,高岩.基于复杂网络理论的电力网络抗毁性分析[J].复杂系统与复杂性科学,2022,19(4):1-6. GUO M J, GAO Y. Invulnerability analysis of power network based on complex network[J]. Complex Systems and Complexity Science, 2022, 19(4): 1-6. [15] 郑军,周海平.基于复杂网络理论的大型电路分析与优化[J].计算机工程,2011,37(15):283-285. ZHENG J, ZHOU H P. Analysis and optimization of large-scale circuit based on complex network theory[J]. Computer Engineering, 2011, 37(15): 283-285. [16] WOO S, PARK J, LEE J Y, et al. Cbam: Convolutional block attention module[C]// Proceedings of the European Conference on Computer Vision(ECCV). Munich: Springer, 2018: 3-19. [17] GREWAL G, AREIBI S. Guelph FPGA CAD Group [EB/OL]. (2017-03-17) [2023-10-26]. http://fpga.socs.uoguelph.ca/. [18] GREWAL G,AREIBI S,WESTRIK M,et al. Automatic flow selection and quality-of-result estimation for FPGA placement[C]// Proceedings of the 24th Reconfigurable Architectures Workshop. Lake Buena Vista: IEEE, 2017: 115-123. [19] LI W X, DHAR S, PAN D. UTPlaceF:a routability driven FPGA placer with physical and congestion aware packing[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2018, 37(4): 869-882. [20] MAAROUF D, ALHYARI A, ABUOWAIMER Z, et al. A machine learning congestion estimation model for modern FPGAs[C]// IEEE Int’l Conference on Field Programmable Logic and Applications. Dublin: IEEE, 2018: 1-8. [21] NIE T Y, FAN B, WANG Z H. Complexity and robustness of weighted circuit network of placement[J]. Physica A: Statistical Mechanics and Its Applications, 2022, 598: 127346. [22] AL-HYARI A, SZENTIMREY H, SHAMLI A, et al. A deep learning framework to predict routability for FPGA circuit placement[J]. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2021, 14(3): 1-28.
