Одно из главных преимуществ проектирования пользовательских схем на ПЛИС - высокая скорость разработки, поэтому создание эффективных средств автоматизированного проектирования для современных микросхем этого класса имеет важное значение. Наиболее времязатратными этапами маршрута проектирования на ПЛИС являются размещение и трассировка. От качества результатов этих этапов зависят итоговые характеристики пользовательских цифровых схем, реализованных на ПЛИС. В работе рассмотрен подход к ускорению этапа трассировки в рамках маршрута топологического проектирования на ПЛИС за счет улучшения алгоритма трассировки. Исследован базовый алгоритм трассировки, представляющий собой модифицированный Pathfinder для смешанного графа трассировочных ресурсов. Этот алгоритм построен на основе согласования маршрутов цепей проектной схемы и работает по принципу итерационного устранения перегрузок трассировочных ресурсов базового кристалла ПЛИС. Для проведения экспериментальных запусков использованы наборы тестовых цифровых схем ISCAS’85, ISCAS’89, LGSynth’89 и несколько пользовательских промышленных проектов. Работа улучшенного алгоритма трассировки проанализирована на примере четырех архитектур ПЛИС. Вследствие усовершенствования алгоритма среднее уменьшение времени трассировки составило от 1,3 до 2,6 раза в зависимости от архитектуры ПЛИС без значительного отрицательного влияния на временные характеристики проектируемых схем.
-
Ключевые слова:
ПЛИС, САПР, топологическое проектирование, трассировка, Pathfinder, поиск кратчайшего пути
-
Библиографическая ссылка:
Заплетина М.А., Гаврилов С.В. Модификация алгоритма Pathfinder для этапа трассировки межсоединений ПЛИС // Изв. вузов. Электроника. 2021. Т. 26. № 5. С. 399–409. DOI: https://doi.org/ 10.24151/1561-5405-2021-26-5-399-409
-
Источник финансирования:
работа выполнена при финансовой поддержке РФФИ (проект № 20-37- 90046).
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).