Izvestiya Vysshikh Uchebnykh Zavedenii. Elektronika home

Publication of the journal

The section is currently being updated

One of the main advantages of FPGA design flow compared with ASICs and gate arrays is the required functionality implementation speed. However, their weakness is the final circuit, and attempts to improve them lead to an increase in the design flow time in most cases. Therefore, effective computer-aided design tools for modern FPGA that consider both these aspects are very essential. This work proposes an approach to accelerate the routing stage in FPGA design flow by modification of a basic routing algorithm Pathfinder adapted to a mixed route graph. The modification is to create and use backpass tree structures that allow the implementation of a directed path search on a mixed route graph having no information about geometric coordinates of its elements. Benchmark sets used for testing are LGSynth’89, IWLS’2005, and a range of projects from opencores.org. The work of the algorithm was analyzed using four FPGA architectures. According to the analysis of experimental results the modified algorithm has demonstrated an average routing runtime reduction of 1.8 to 3.6 depending on the target FPGA.

Key words: field-programmable gate array, computer-aided design, topological layout design, physical synthesis, place and route, PnR, routing, Pathfinder, shortest path search, directed path search
Published in: CIRCUIT ENGINEERING AND DESIGN
Bibliography link: Chistiakov A. Yu., Zapletina M. A. Backpass trees on a mixed route graph for accelerated FPGA routing. Proc. Univ. Electronics, 2024, vol. 29, no. 2, pp. 185–193. https://doi.org/10.24151/1561-5405-2024-29-2-185-193

Alexander Yu. Chistiakov
Institute for Design Problems in Microelectronics of the Russian Academy of Sciences (Russia, 124365, Moscow, Zelenograd, Sovetskaya st., 3)

Mariya A. Zapletina
Institute for Design Problems in Microelectronics of the Russian Academy of Sciences (Russia, 124365, Moscow, Zelenograd, Sovetskaya st., 3)

1. McMurchie L., Ebeling C. PathFinder: A negotiation-based performance-driven router for FPGAs // 3rd International ACM Symposium on Field-Programmable Gate Arrays. Napa Valley, CA: IEEE, 1995. P. 111-117. DOI: 10.1109/FPGA.1995.242049

2. Zapletina M. A., Zheleznikov D. A. The acceleration techniques for the modified pathfinder routing algorithm on an island-style FPGA // 2022 Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg: IEEE, 2022. P. 920-923. DOI: 10.1109/ElConRus54750.2022.9755536 EDN: PKMIQY

3. 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: 10.1109/FCCM.2019.00017

4. VTR 7.0: Next generation architecture and CAD system for FPGAs /j. Luu, J. Goeders, M. Wainberg et al. // ACM Trans. Reconfigurable Technol. Syst. 2014. Vol. 7. Iss. 2. Art. No. 6. DOI: 10.1145/2617593

5. FCRoute: A fast FPGA connection router using soft routing-space pruning algorithm / D. Wang, J. Feng, W. Zhou et al. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2023. Vol. 42. No. 3. P. 887-899. DOI: 10.1109/TCAD.2022.3188964 EDN: WLFZEQ

6. A runtime optimization approach for FPGA routing / D. Wang, Z. Duan, C. Tian et al. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2018. Vol. 37. No. 8. P. 1706-1710. DOI: 10.1109/TCAD.2017.2768416

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: 10.1109/ASP-DAC47756.2020.9045175

8. 5400ТР094 ПАЦИС: Программируемая аналого-цифровая интегральная схема // Дизайн-центр "Союз" [Электронный ресурс]. URL: https://dcsoyuz.ru/products/pais/art/1605 (дата обращения: 20.11.2023).
5400ТР094 PATsIS: programmable analog-digital integrated circuit. Dizayn-tsentr “Soyuz”. (In Russian). Available at: https://dcsoyuz.ru/products/pais/art/1605 (accessed: 20.11.2023).

9. Контракт: 1770559633917000451 // ГосЗатраты [Электронный ресурс]. URL: https://clearspending.ru/contract/1770559633917000451/(дата обращения: 20.11.2023).
Contract: 1770559633917000451. ClearSpending. (In Russian). Available at: https://clearspending.ru/
contract/1770559633917000451/ (accessed: 20.11.2023).

10. 5510XC1T/2T/3T: ПЛИС емкостью 20, 50 и 100 тыс. вентилей // Микросхемы ПАО "Микрон" [Электронный ресурс]. М., 2020. С. 31. URL: https://413100.selcdn.ru/upload-153a6b408c99eadfc8d7d3c5576481d8/iblock/05d/05d7224966d072bbbc986716... (дата обращения: 20.11.2023).
5510XC1T/2T/3T: FPGA with a capacity of 20, 50 and 100 thousand gates. Mikroskhemy PAO “Mikron”. Moscow, 2020, p. 31. (In Russian). Available at: https://413100.selcdn.ru/upload-153a6b408c99eadfc8d7d3c5576481d8/iblock/05d/05d7224966d072bbbc986716f3e32ecc/katalog+VPK_2020.pdf (accessed: 20.11.2023).

11. Контракт: 1770559633917000449 // ГосЗатраты [Электронный ресурс]. URL: https://clearspending.ru/contract/1770559633917000449/#suppliers (дата обращения: 20.11.2023).
Contract: 1770559633917000449. ClearSpending. (In Russian). Available at: https://clearspending.ru/contract/1770559633917000449/#suppliers (accessed: 20.11.2023).

12. Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146. № 2. С. 263-266.
Adel’son-Vel’skii G. M., Landis E. M. An algorithm for organization of information. Dokl. Akad. Nauk SSSR, 1962, vol. 146, no. 2, pp. 263—266. (In Russian).

13. Wand M. P., Jones M. C. Kernel smoothing. Boca Raton, FL; London: Chapman & Hall/CRC, 1995. 226 p.

Information about the publication

Downloads: 0

UDK: 621.3.049.771.14:621.3.062
Publication type: Scientific article
DOI: 10.24151/1561-5405-2024-29-2-185-193
RISC id: NTQOYY

Download: File not found (594.88 Kb) JATS XML