One of the main advantages of FPGA and CPLD is the high development speed; therefore, the importance of effective computer-aided design tools for modern microcircuits of these classes cannot be overestimated. Placement and routing are the most time-consuming stages of FPGA/CPLD design flow. The quality of results of these stages is crucial to the final performance of custom digital circuits implemented on FPGA/CPLD. The paper discusses an approach to accelerating the routing stage within the layout synthesis flow for FPGA/CPLD by introducing a few algorithmic improvements to a routing procedure. The basic routing algorithm under study is a modified Pathfinder for a mixed routing resource graph. Pathfinder is a well-known negotiation-based routing algorithm that works on the principle of iteratively eliminating congestions of chip routing resources. For experiments, the sets of test digital circuits ISCAS'85, ISCAS'89, LGSynth'89 and several custom industrial projects were used. The impact of the proposed algorithmic improvements was analyzed using four FPGA/CPLD architectures. It has been established that due to the improvements of the algorithm proposed in the paper, the average reduction in routing time was from 1.3 to 2.6 times, depending on the FPGA/CPLD architecture, with no significant negative effect on the timing characteristics of the designed circuits.
Mariya A. Zapletina
Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow, Russia
1. McMurchie L., Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs // FPGA’95: Proceedings of the 1995 ACM Third International Symposium on Field-Programmable Gate Arrays. New York: ACM, 1995. P. 111–117. DOI: https://doi.org/10.1145/201310.201328
2. Zhou Y., Vercruyce D., Stroobandt D. Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization // ACM Transactions on Reconfigurable Technology and Systems. 2020. Vol. 13. Iss. 4. Art. No. 18. P. 1–26. DOI: https://doi.org/10.1145/3406959
3. VTR 8: High-performance CAD and customizable FPGA architecture modelling / K.E. Murray, O. Petelin, Sh. Zhong et al. // ACM Transactions on Reconfigurable Technology and Systems. 2020. Vol. 13. Iss. 2. Art. No. 9. P. 1–55. DOI: https://doi.org/10.1145/3388617
4. Pan M., Xu Y., Zhang Y., Chu Ch. Fastroute: An efficient and high-quality global router // VLSI Design. 2012. Art. ID 608362. 18 p. DOI: https://doi.org/10.1155/2012/608362
5. He J., Burtscher M., Manohar R., Pingali K. SPRoute: A scalable parallel negotiation-based global router // 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-2019). Westminster, CO: IEEE, 2019. P. 1–8. DOI: https://doi.org/10.1109/ICCAD45719.2019.8942105
6. Vercruyce D., Vansteenkiste E., Stroobandt D. CRoute: A fast high-quality timing-driven connection-based FPGA router // 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, CA: IEEE, 2019. P. 53–60. DOI: https://doi.org/10.1109/FCCM.2019.00017
7. Murray K.E., Zhong S., Betz V. AIR: A fast but lazy timing-driven FPGA router // 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Beijing: IEEE, 2020. P. 338–344. DOI: https://doi.org/10.1109/ASP-DAC47756.2020.9045175
8. Hoo C.H., Kumar A. ParaDRo: A parallel deterministic router based on spatial partition-ing and scheduling // FPGA’18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. New York: ACM, 2018. P. 67–76. DOI: https://doi.org/10.1145/3174243.3174246
9. Fraisse H. Incremental routing for circuit designs using a SAT router. U.S. Patent No. 10445456. Filed: 14.06.2017. Publ.: 15.10.2019.
10. High-definition routing congestion prediction for large-scale FPGAs / M.B. Alawieh, W. Li, Y. Lin et al. // 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Beijing: IEEE, 2020. P. 26–31. DOI: https://doi.org/10.1109/ASP-DAC47756.2020.9045178
11. Li W., Dehkordi M.E., Yang S., Pan D.Z. Simultaneous placement and clock tree con-struction for modern FPGAs // FPGA’19: Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. New York: ACM, 2019. P. 132–141. DOI: https://doi.org/10.1145/3289602.3293897
12. Kannan P., Bhatia D. Tightly integrated placement and routing for FPGAs // FPL 2001: Field-Programmable Logic and Applications. Berlin; Heidelberg: Springer, 2001. P. 233–242. DOI: https://doi.org/10.1007/3-540-44687-7_25
13. Liu W.-H., Kao W.-C., Li Y.-L., Chao K.-Y. Multi-threaded collision-aware global rout-ing with bounded-length maze routing // Design Automation Conference. Anaheim, CA: IEEE, 2010. P. 200–205.
14. Pan M., Chu C. IPR: An integrated placement and routing algorithm // 2007 44th ACM/IEEE Design Automation Conference. San Diego, CA: IEEE, 2007. P. 59–62.
15. Змеев Д.Н., Левченко Н.Н., Окунев А.С., Стемпковский А.Л. Влияние особенно-стей модели вычислений и архитектуры на надежность параллельной потоковой вычислительной системы // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2020. № 1. С. 64–69. DOI: https://doi.org/10.31114/2078-7707-2020-1-64-69
16. Brglez F., Fujiwara H. A neutral netlist of 10 combinational circuits and a targeted translator in FORTRAN // Special Session on Recent Algorithms for Gate-Level ATPG with Fault Simulation and Their Performance Assessment, 1985 IEEE Int. Symp. on Circuits and Sys-tems. Kyoto: IEEE, 1985. P. 663–698.
17. Brglez F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark cir-cuits // IEEE International Symposium on Circuits and Systems. Portland, OR: IEEE, 1989. Vol. 3. P. 1929–1934. DOI: https://doi.org/10.1109/ISCAS.1989.100747
18. Yang S. Logic synthesis and optimization benchmarks: Technical report, MCNC, Dec. 1988 // 1989 MCNC International Workshop on Logic Synthesis. S. l.: MCNC, 1989. P. 14.
19. Железников Д.А., Заплетина М.А., Хватов В.М. Исследование механизма разры-ва и перетрассировки на этапе топологического синтеза в базисе реконфигурируемых систем на кристалле // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2018. № 1. С. 188–192. DOI: https://doi.org/10.31114/2078-7707-2018-1-188-192
20. Маршрут топологического синтеза для реконфигурируемых систем на кристалле специального назначения / С.В. Гаврилов, Д.А. Железников, М.А. Заплетина и др. // Микроэлектроника, 2019. Т. 48. № 3. С. 211–223. DOI: https://doi.org/10.1134/S0544126919030050
21. ПАЦИС 5400ТР094 // Дизайн центр «Союз»: [Электронный ресурс]. URL: https://dcsoyuz.ru/search/art/1605 (дата обращения: 06.04.2021).
22. ProASIC3 series // Microsemi: [Web] / Microchip Technology Inc. URL: https://www.microsemi.com/product-directory/fpgas/1690-proasic3 (дата обращения: 06.04.2021).
23. Intel MAX II Device Handbook / Altera Corp. 2009. 297 p. // Intel: [Web] / Intel Corp. URL: https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/max2/max2_mii5v1.pdf (дата обращения: 06.04.2021).