Архитектурно-ориентированная модель расширенного смешанного коммутационного графа позволяет описать особенности трассировочных ресурсов современных программируемых логических интегральных схем (ПЛИС). Такая модель может применяться для решения задачи трассировки проектных межсоединений в составе маршрута топологического проектирования на основе ПЛИС. В работе рассмотрена архитектурно-ориентированная модель расширенного смешанного коммутационного графа. Предложены две модификации базового метода автоматической трассировки - классического алгоритма Pathfinder, адаптированного к смешанному графу коммутационных ресурсов. Первая модификация построена на применении идеи направленного поиска на графовой модели с использованием данных о пространственно-геометрических характеристиках базового кристалла, вторая - сочетает стратегию направленного поиска с учетом предварительной оценки перегруженности коммутационных ресурсов ПЛИС по результатам процедуры размещения. Показано, что предложенные модификации позволяют ускорить сходимость базового метода к трассировочному решению в среднем на 50,6 и 38,6 % соответственно. При сохранении полной трассируемости тестовых наборов IWLS’2005, ISCAS’89 и LGSynth’89 применение только направленного поиска привело к улучшению временных характеристик имплементаций проектных схем на 5,2 % в среднем, а использование его совместно с оценкой перегруженности перед началом трассировки позволило улучшить их на 9,3 % в среднем относительно результатов базового метода Pathfinder.
1. Wu Y.-L., Chang D. On the NP-completeness of regular 2-d FPGA routing architectures and a novel solution // IEEE/ACM International Conference on Computer-Aided Design. San Jo-se, CA: IEEE, 1994. P. 362–366. https://doi.org/10.1109/ICCAD.1994.629819
2. 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. https://doi.org/10.1109/FCCM.2019.00017
3. 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. https://doi.org/10.1109/ASP-DAC47756.2020.9045175
4. VTR 8: High-performance CAD and customizable FPGA architecture modeling / K. E. Murray, O. Petelin, Sh. Zhong et al. // ACM Trans. Reconfigurable Technol. Syst. 2020. Vol. 13. Iss. 2. Art. No. 9. https://doi.org/10.1145/3388617
5. Заплетина М. А. Методы ускорения работы модифицированного алгоритма трас-сировки Pathfinder для ПЛИС островного типа // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2021. № 4. C. 27–33. https://doi.org/10.31114/2078-7707-2021-4-27-33
6. Zhou Y., Vercruyce D., Stroobandt D. Accelerating FPGA routing through algorithmic enhancements and connection-aware parallelization // ACM Trans. Reconfigurable Technol. Syst. 2020. Vol. 13. Iss. 4. Art. No. 18. https://doi.org/10.1145/3406959
7. 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). Westminster, CO: IEEE, 2019. P. 1–8. https://doi.org/10.1109/ICCAD45719.2019.8942105
8. Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math. 1959. Vol. 1. P. 269–271. https://doi.org/10.1007/BF01386390
9. Moore E. F. The shortest path through a maze // Proceedings of an International Sympo-sium on the Theory of Switching. Part II. Cambridge, MA: Harvard University Press, 1959. P. 285–292.
10. Lee C. Y. An algorithm for path connections and its applications // IRE Transactions on Electronic Computers. 1961. Vol. EC-10. No. 3. P. 364–365. https://doi.org/10.1109/TEC.1961.5219222
11. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. 1968. Vol. 4. Iss. 2. P. 100–107. https://doi.org/10.1109/TSSC.1968.300136
12. McMurchie L., Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs // Proceedings of the 1995 ACM Third International Symposium on Field-Programmable Gate Arrays (FPGA’95). New York: ACM, 1995. P. 111–117. https://doi.org/10.1145/201310.201328
13. Yang S. Logic synthesis and optimization benchmarks: Technical report, MCNC, 1988 // Proceedings of 1989 MCNC International Workshop on Logic Synthesis. Raleigh, NC: MCNC, 1989. P. 14.
14. IWLS 2005 benchmarks / initiated by C. Albrecht // International Workshop on Logic & Synthesis [Электронный ресурс]. URL: https://iwls.org/iwls2005/benchmarks.html (дата об-ращения: 05.10.2022).
15. Оре О. Графы и их применение / пер. с англ. Л. И. Головиной; под ред. И. М. Яглома. М.: Мир, 1965. 174 с.
16. Spindler P., Johannes F. M. Fast and accurate routing demand estimation for efficient routability-driven placement // 2007 Design, Automation & Test in Europe Conference & Exhi-bition. Nice: IEEE, 2007. P. 1–6. https://doi.org/10.1109/DATE.2007.364463
17. Маршрут топологического синтеза для реконфигурируемых систем на кристалле специального назначения / С. В. Гаврилов, Д. А. Железников, М. А. Заплетина и др. // Микроэлектроника. 2019. Т. 48. № 3. С. 211–223. https://doi.org/10.1134/S0544126919030050
18. Corno F., Reorda M. S., Squillero G. RT-level ITC’99 benchmarks and first ATPG re-sults // IEEE Design & Test of Computers. 2000. Vol. 17. Iss. 3. P. 44–53. https://doi.org/10.1109/54.867894
19. Zapletina M. A., Zheleznikov D. A., Gavrilov S. V. Improving pathfinder algorithm per-formance for FPGA routing // 2021 IEEE Conference of Russian Young Researchers in Electri-cal and Electronic Engineering (ElConRus 2021). St. Petersburg; Moscow: IEEE, 2021. P. 2054–2057. https://doi.org/10.1109/ElConRus51938.2021.9396608