Currently, FPGA circuit design becomes increasingly popular among developers of low-volume manufacturing electronic equipment, which is due to the lower cost of the product compared to application-specific circuits, as well as to the emergence of new, more advanced FPGAs. In this connection, an important task is the creation of highly efficient computer-aided design algorithms that allow obtaining high output characteristics of circuits designed on the basis of FPGAs in the shortest possible time. In this work, a fast algorithm for solving the routing problem within the FPGA layout synthesis flow is proposed. The operation of the algorithm was tested on popular digital benchmarks ISCAS’85, ISCAS’89, LGSynth’89, IWLS’2005 and a number of open projects implemented on an FPGA from the 5510TC028 system-on-a-chip. The stages of a layout synthesis flow that precede routing stage were carried out using the corresponding modules of the X-CAD computer-aided design system developed by IPPM RAS. According to experimental results, the developed algorithm has demonstrated an average routing runtime reduction of 2.8 times compared to the default X-CAD routing algorithm without a significant impact on the circuits timing characteristics estimated with open-source static timing analysis tool OpenSTA.
-
Key words:
field-programmable gate array, FPGA, computer-aided design, layout design, physical synthesis, place and route, PnR, routing, Pathfinder, shortest path search
-
Published in:
CIRCUIT ENGINEERING AND DESIGN
-
Bibliography link:
Chistyakov А. Yu., Zapletina M. A. Fast FPGA routing algorithm with partial rip up of routing trees. Izv.vuzov. Elektronika = Proc. Univ. Electronics. 2025;30(2):162–171. (In Russ.). https://doi.org/10.24151/1561-5405-2025-30-2-162-171.
-
Financial source:
theoretical research has been supported by the Ministry of Education and Science of Russian Federation within the framework of the state assignment of the National Research Center “Kurchatov Institute”; computational experiments were carried out within the framework of the state assignment of MIET.
1. Luu J., Goeders J., Wainberg M., Somerville A., Yu T., Nasartschuk K. et al. VTR 7.0: Next generation architecture and CAD system for FPGAs. ACM Trans. ReconfigurableTechnol. Syst. 2014;7(6):1–30.
https://doi.org/10.1145/2617593
2. Гаврилов С. В., Железников Д. А., Заплетина М. А., Тиунов И. В., Хватов В. М., Чочаев Р. Ж., Шокарев Д. Б. Разработка доверенных средств проектирования ИС в базисе гетерогенных ПЛИС. Тр. Института системного программирования РАН. 2023;35(5):107–126.
https://doi.org/10.15514/ISPRAS-2022-35(5)-8. EDN: KJOKIC.
Gavrilov S. V., Zheleznikov D. A., Zapletina M. A., Tiunov I. V., Khvatov V. M., Chochaev R. Zh., Shokarev D. B. Development of the trusted tools for IC design on heterogeneous FPGAs.Tr. Instituta sistemnogo programmirovaniya RAN = Proceedings of ISP RAS. 2023;35(5):107–126. (In Russ.).
https://doi.org/10.15514/ISPRAS-2022-35(5)-8
3. Tang X., Giacomin E., Chauviere B., Alacchi A., Gaillardon P.-E. OpenFPGA: An open-source framework for agile prototyping customizable FPGAs. IEEE Micro. 2020;40(4):41–48.
https://doi.org/10.1109/MM.2020.2995854
4. Shah D., Hung E., Wolf C., Bazanski S., Gisselquist D., Milanovic M. Yosys+nextpnr: An open source framework from Verilog to Bitstream for commercial FPGAs. In: 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, CA: IEEE; 2019, pp. 1–4.
https://doi.org/10.1109/FCCM.2019.00010
5. RapidWright. Available at:
https://www.rapidwright.io/ (accessed: 15.01.2025).
6. Zapletina M. A., Zheleznikov D. A. The acceleration techniques for the modified pathfinder routing algorithm on an island-style FPGA. In: 2022 Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg: IEEE; 2022, pp. 920–923.
https://doi.org/10.1109/ElConRus54750.2022.9755536
7. Murray K. E., Zhong S., Betz V. AIR: A fast but lazy timing-driven FPGA router. In: 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Beijing: IEEE; 2020, pp. 338–344.
https://doi.org/10.1109/ASP-DAC47756.2020.9045175
8. McMurchie L., Ebeling C. PathFinder: A negotiation-based performance-driven router for FPGAs. In: Proceedings of the 1995 ACM 3rd International Symposium on FPGAs (FPGA ’95). New York: ACM; 1995, pp. 111–117.
https://doi.org/10.1145/201310.201328
9. Zhou Y., Vercruyce D., Stroobandt D. Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization. ACM Trans. Reconfigurable Technol. Syst. 2020;13(4):18.
https://doi.org/10.1145/3406959
10. Vercruyce D., Vansteenkiste E., Stroobandt D. CRoute: a fast high-quality timing-driven connection-based FPGA router. In: 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). SanDiego, CA: IEEE; 2019, pp. 53–60.
https://doi.org/10.1109/FCCM.2019.00017
11. Контракт: 1770559633917000449: ОКР «Разработка и освоение серийного производства микросхемы типа система на кристалле, состоящей из ядер процессора и ПЛИС емкостью не менее 800 тыс. системных вентилей». ГосЗатраты. Available at:
https://clearspending.ru/contract/1770559633917000449/#suppliers (accessed: 15.01.2025).
Contract: 1770559633917000449: NPD “Development and series production ramp-up of SoC microcircuit consisting of IP cores and FPGAs with capacity no less than 800 thousand system gates”. ClearSpending.(In Russ.). Available at:
https://clearspending.ru/contract/1770559633917000449/#suppliers (accessed: 15.01.2025).
12. Wang D., Duan Z., Tian C., Huang B., Zhang N. A runtime optimization approach for FPGA routing.IEEE Trans. Comput. Aided Des.Integr. Circuits Syst. 2018;37(8):1706–1710.
https://doi.org/10.1109/TCAD.2017.2768416