1561-5405 10.24151/1561-5405 Proceedings of Universities. Electronics Scientifical and technical journal "Proceedings of Universities. Electronics" Научно-технический журнал «Известия высших учебных заведений. Электроника» 1561-5405 2587-9960 National Research University of Electronic Technology Национальный исследовательский университет "Московский институт электронной техники" 10.24151/1561-5405-2021-26-5-399-409621.3.049.771.14:621.3.062:[658.512:004]Pathfinder Algorithm Modification for CPLD and FPGA Routing StageМодификация алгоритма Pathfinder для этапа трассировки межсоединений ПЛИСЗаплетина Мария АндреевнаЗаплетинаМария АндреевнаZapletinaMariya A.Mariya A. ZapletinaГаврилов Сергей Витальевич ГавриловСергей Витальевич VitalevichGavrilov SergeyGavrilov Sergey VitalevichИнститут проблем проектирования в микроэлектронике Российской академии наук, г. Москва, РоссияИнститут проблем проектирования в микроэлектронике Российской академии наук, г. Москва, Россия399409http://ivuz-e.ru/issues/5-_2021/modifikatsiya_algoritma_pathfinder_dlya_etapa_trassirovki_mezhsoedineniy_plis/

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.

Одно из главных преимуществ проектирования пользовательских схем на ПЛИС - высокая скорость разработки, поэтому создание эффективных средств автоматизированного проектирования для современных микросхем этого класса имеет важное значение. Наиболее времязатратными этапами маршрута проектирования на ПЛИС являются размещение и трассировка. От качества результатов этих этапов зависят итоговые характеристики пользовательских цифровых схем, реализованных на ПЛИС. В работе рассмотрен подход к ускорению этапа трассировки в рамках маршрута топологического проектирования на ПЛИС за счет улучшения алгоритма трассировки. Исследован базовый алгоритм трассировки, представляющий собой модифицированный Pathfinder для смешанного графа трассировочных ресурсов. Этот алгоритм построен на основе согласования маршрутов цепей проектной схемы и работает по принципу итерационного устранения перегрузок трассировочных ресурсов базового кристалла ПЛИС. Для проведения экспериментальных запусков использованы наборы тестовых цифровых схем ISCAS’85, ISCAS’89, LGSynth’89 и несколько пользовательских промышленных проектов. Работа улучшенного алгоритма трассировки проанализирована на примере четырех архитектур ПЛИС. Вследствие усовершенствования алгоритма среднее уменьшение времени трассировки составило от 1,3 до 2,6 раза в зависимости от архитектуры ПЛИС без значительного отрицательного влияния на временные характеристики проектируемых схем.

ПЛИССАПРтопологическое проектированиетрассировкаPathfinderпоиск кратчайшего путиработа выполнена при финансовой поддержке РФФИ (проект № 20-37- 90046). 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.201328Zhou 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/3406959VTR 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/3388617Pan 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/608362He 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.8942105Vercruyce 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.00017Murray 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.9045175Hoo 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.3174246Fraisse H. Incremental routing for circuit designs using a SAT router. U.S. Patent No. 10445456. Filed: 14.06.2017. Publ.: 15.10.2019.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.9045178Li 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.3293897Kannan 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_25Liu 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.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.Змеев Д.Н., Левченко Н.Н., Окунев А.С., Стемпковский А.Л. Влияние особенно-стей модели вычислений и архитектуры на надежность параллельной потоковой вычислительной системы // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2020. № 1. С. 64–69. DOI: https://doi.org/10.31114/2078-7707-2020-1-64-69Brglez 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.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.100747Yang S. Logic synthesis and optimization benchmarks: Technical report, MCNC, Dec. 1988 // 1989 MCNC International Workshop on Logic Synthesis. S. l.: MCNC, 1989. P. 14.Железников Д.А., Заплетина М.А., Хватов В.М. Исследование механизма разры-ва и перетрассировки на этапе топологического синтеза в базисе реконфигурируемых систем на кристалле // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2018. № 1. С. 188–192. DOI: https://doi.org/10.31114/2078-7707-2018-1-188-192Маршрут топологического синтеза для реконфигурируемых систем на кристалле специального назначения / С.В. Гаврилов, Д.А. Железников, М.А. Заплетина и др. // Микроэлектроника, 2019. Т. 48. № 3. С. 211–223. DOI: https://doi.org/10.1134/S0544126919030050ПАЦИС 5400ТР094 // Дизайн центр «Союз»: [Электронный ресурс]. URL: https://dcsoyuz.ru/search/art/1605 (дата обращения: 06.04.2021).ProASIC3 series // Microsemi: [Web] / Microchip Technology Inc. URL: https://www.microsemi.com/product-directory/fpgas/1690-proasic3 (дата обращения: 06.04.2021).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).