Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70221410.17587/it.31.115-123Cad-systemsСистемы автоматизированного проектированияResearch ArticleModified signal routing algorithm in VLSI designМодифицированный алгоритм маршрутизации сигналов при проектировании СБИСKureichikV. V.КурейчикВ. В.
Russian Federation

Dr. of Eng. Sc., Professor

д-р техн. наук, проф.

vkur@sfedu.ruDanilchenkoV. I.ДанильченкоВ. И.
Russian Federation

Ph.D. Tech. Sc.,Associate Professor

канд. техн. наук, доц.

vdanilchenko@sfedu.ruBovaV. V.БоваВ. В.
Russian Federation

Associate Professor

доц.

vvbova@sfedu.ruSouthern Federal UniversityЮжный федеральный университет150320253131151230502202605022026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702214

The research is devoted to the modification of the routing algorithm to optimize signal routing at the design stage of designing ultra-large integrated circuits (VLSI). The relevance of the study is due to the need to improve the design efficiency and improve the operational characteristics of VLSI. А modified genetic algorithm with improved encoding and decoding mechanisms has been developed, which increases the accuracy and efficiency of signal routing in conditions of limited computing resources. As a modification, a block for dynamically changing time delays at the stages of implementation of selection and crossing operators is integrated into the algorithm, due to the adjustment of coefficients depending on the current state of the network. А software environment was built and a computational experiment was conducted. А comparative analysis with known methods has shown that the developed modified algorithm minimizes delays in signal routing and improves overall network efficiency, which confirms its high adaptability and potential for integration into modern VLSI design systems.

Исследование посвящено модификации алгоритма маршрутизации для оптимизации маршрутизации сигналов на конструкторском этапе проектирования сверхбольших интегральных схем (СБИС). Актуальность исследования обусловлена необходимостью повышения эффективности проектирования и улучшения эксплуатационных характеристик СБИС. Разработан модифицированный генетический алгоритм с усовершенствованными механизмами кодирования и декодирования, что повышает точность и эффективность маршрутизации сигналов в условиях ограниченных вычислительных ресурсов. В качестве модификации в алгоритм интегрирован блок динамического изменения временных задержек на этапах реализации операторов селекции и кроссинговера за счет подстройки коэффициентов в зависимости от текущего состояния сети. Построена программная среда и проведен вычислительный эксперимент. Сравнительный анализ с известными методами показал, что разработанный модифицированный алгоритм обеспечивает минимизацию задержек при маршрутизации сигналов и улучшает общую эффективность сети, что подтверждает его высокую адаптивность и потенциал для интеграции в современные системы проектирования СБИС.

signal routingoptimizationgenetic algorithmsencoding and decoding mechanismsselection and crossing operatorscomputer-aided designмаршрутизация сигналовоптимизациягенетические алгоритмымеханизмы кодирования и декодированияоператоры селекции и кроссинговераавтоматизированное проектированиеРоссийский научный фондRussian Science Foundation24-71-00035The research was funded by the Russian Science Foundation project No. 24-71-00035, https://rscf.ru/project/24-71-00035/ implemented by the Southern Federal University.Исследование выполнено за счет гранта Российского научного фонда No 24-71-00035, https://rscf.ru/project/24-71-00035/ в Южном федеральном университете.Danilchenko V. I., Danilchenko E. V., Kureichik V. M. Multidimensional Search in the Problem of Placing Elements of Integrated Circuits Based on Genetic Algorithm, Izvestiya of South Federal University. Technical Sciences, 2021, no. 2(219), pp. 31—39, doi: 10.18522/2311-3103-2021-2-31-39 (in Russian).Данильченко В. И., Данильченко Е. В., Курейчик В. М. Многомерный поиск в задаче размещении элементов СБИС на основе генетического алгоритма // Известия ЮФУ. Технические науки. 2021. № 2(219). С. 31—39. DOI: 10.18522/2311-3103-2021-2-31-39.Kureichik V. V., Gladkov L. A., Kravchenko Y. A., Rodzin S. I. Intelligent Systems: Models and Methods of Metaheuristic Optimization, Cheboksary, Publishing House "Sreda," 2024, 228 p., doi: 10.31483/a-10639 (in Russian).Курейчик В. В., Гладков Л. А., Кравченко Ю. А., Родзин С. И. Интеллектуальные системы: модели и методы метаэвристической оптимизации. Чебоксары: ООО "Издательский дом "Среда", 2024. 228 с. DOI: 10.31483/a-10639.Fakhmi Sh. S., Ryzhov N. G., Khasan Kh. А., Kalinina E. S. Adaptive Algorithm for Image Coding and Decoding in Transport Monitoring Systems, Informacionnye Tehnologii, 2019, vol. 25, no. 8, pp. 475—481, doi: 10.17587/it.25.475-481 (in Russian).Фахми Ш. С., Рыжов Н. Г., Хасан Х. А., Калинина Е. С. Адаптивный алгоритм кодирования и декодирования изображений в транспортных системах наблюдения // Информационные технологии. 2019. Т. 25, № 8. С. 475—481. DOI: 10.17587/it.25.475-481.Danilchenko V. I., Danilchenko Y. V., Kureichik V. M. Bio-inspired Approach to Microwave Circuit Design, IEEE EAST-WEST DESIGN & TEST SYMPOSIUM. EWDTS, 2020, pp. 362—366, doi: 10.1109/EWDTS50664.2020.9224737.Danilchenko V. I., Danilchenko Y. V., Kureichik V. M. io-inspired Approach to Microwave Circuit Design // IEEE EAST-WEST DESIGN & TEST SYMPOSIUM. EWDTS 2020. P. 362—366. DOI: 10.1109/EWDTS 50664.2020.9224737.Danilchenko V. I., Danilchenko Y. V., Kureichik V. M. Application of Genetic Algorithms in Solving the Problem of Placing Elements on a Crystal Considering the Criterion of Maximum Number of Linear Segments, 5th International Scientific Conference "Intelligent Information Technologies for Industry", 2021, pp. 10—14.Danilchenko V. I., Danilchenko Y. V., Kureichik V. M. Application of genetic algorithms in solving the problem of placing elements on a crystal taking into account the criterion of the maximum number of linear segments // 5th International Scientific Conference "Intel Ligent Information Technologies for Industry". 2021. P. 10—14.Gladkov L. A., Gladkova N. V. Evolving Multi-agent Systems and Evolutionary Design, Izvestiya of South Federal University. Technical Sciences, 2020, no. 4 (214), pp. 48—59, doi 10.18522/2311-3103-2020-4-48-59 (in Russian).Гладков Л. А., Гладкова Н. В. Эволюционирующие многоагентные системы и эволюционное проектирование // Известия ЮФУ. Технические науки. 2020. № 4(214). С. 48—59. DOI: 10.18522/2311-3103-2020-4-48-59.Plesovskikh I. B. Genetic Algorithm for Optimization of the Topology of Global Computing Networks, Informacionnye Tehnologii, 2013, no. 10, pp. 20—23 (in Russian).Плесовских И. Б. Генетический алгоритм оптимизации топологии глобальной вычислительной сети // Информационные технологии. 2013. № 10. С. 20—23.Romanov А. Yu., Siderenko M. V., Monakhova E. A. Routing in Networks-on-Chip with Three-dimensional Circulant Topology, Informacionnye Tehnologii, 2020, vol. 26, no. 1, pp. 22—29, doi: 10.17587/it.26.22-29 (in Russian).Романов А. Ю., Сидоренко М. В., Монахова Э. А. Маршрутизация в сетях-на-кристалле с топологией трехмерный циркулянт // Информационные технологии. 2020. Т. 26, № 1. С. 22—29. DOI: 10.17587/it.26.22-29.Sherwani N. A. Algorithms for VLSI Physical Design Automation, Third Edition, USA, Kluwer Academic Publishers, 2013, 567 p.Sherwani N. A. Algorithms for VLSI Physical Design Automation. Third Edition. USA: Kluwer Academic Publisher, 2013. 567 p.Gladkov L. A. New Approaches to the Development and Creation of Hybrid Artificial Systems Components, Moscow, Fizmatlit, 2010, pp. 143—163 (in Russian).Гладков Л. А. Новые подходы к разработке и созданию компонентов гибридных искусственных систем. М.: Физматлит, 2010. С. 143—163.Nemyudrov V. N., Martin G. Systems on a Chip, Design and Development, Moscow, Tekhnosfera, 2004, 216 p. (in Russian).Немудров В. Н., Мартин Г. Системы на кристалле // Проектирование и развитие. М.: Техносфера, 2004. 216 с.Perepelkin D. A., Ivanchikova M. A., Nguyen V. T. Neural Network Multi-path Routing in Software-configurable Networks Based on Genetic Algorithm, Informacionnye Tehnologii, 2023, vol. 29, no. 12, pp. 622—629, doi: 10.17587/it.29.622-629 (in Russian).Перепелкин Д. А., Иванчикова М. А., Нгуен В. Т. Нейросетевая многопутевая маршрутизация в программно-конфигурируемых сетях на основе генетического алгоритма // Информационные технологии. 2023. Т. 29, № 12. С. 622—629. DOI: 10.17587/it.29.622-629.Kazennov G. G. Fundamentals of Integrated Circuit and System Design, Moscow, Binom. Knowledge Laboratory, 2005, 295 p. (in Russian).Казеннов Г. Г. Основы проектирования интегральных схем и систем. М.: Бином. Лаборатория знаний, 2005. 295 с.Nuzhnov E. V., Kureichik L. V., Kureichik Vl. Vl. Tools Supporting Topological Design of Custom Mixed-Signal ICs in CAD Cadence, Izvestiya TSTU, 2007, no. 1, pp. 109—113 (in Russian).Нужнов Е. В., Курейчик В. В., Полупанов А. А. Средства поддержки топологического проектирования заказных цифро-аналоговых ИС в САПР Cadence // Известия ТРТУ. 2007. № 1. С. 109—113.Wilson R. Introduction to Graph Theory, Moscow, Williams, 2019, 240 p. (in Russian).Уилсон Р. Введение в теорию графов. М.: Вильямс, 2019. 240 с.Romanov А. Yu., Vedmid E. A., Monakhova E. A. Design of Networks-on-Chip with Ring Circulant Topology with Three Generators: Development of Routing Algorithms, Informacionnye Tehnologii, 2019, vol. 25, no. 9, pp. 522—530, doi: 10.17587/it.25.522-530 (in Russian).Романов А. Ю., Ведмидь Е. А., Монахова Э. А. Проектирование сетей на кристалле с топологией кольцевой циркулянт с тремя образующими: разработка алгоритмов маршрутизации // Информационные технологии. 2019. Т. 25, № 9. С. 522—530. DOI: 10.17587/it.25.522-530.Gladkov L. A., Kureichik V. V., Kureichik V. M. Genetic Algorithms, Moscow, Fizmatlit, 2010, 368 p. (in Russian).Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит, 2010. 368 с.Akopov A. S., Beklaryan L. A., Beklaryan А. L. Optimization of Characteristics of Intelligent Transport Systems Using Genetic Algorithm with Real Coding Based on Adaptive Mutation, Informacionnye Tehnologii, 2023, vol. 29, no. 3, pp. 115—125, doi: 10.17587/it.29.115-125 (in Russian).Акопов А. С., Бекларян Л. А., Бекларян А. Л. Оптимизация характеристик интеллектуальной транспортной системы с использованием генетического алгоритма вещественного кодирования на основе адаптивной мутации / // Информационные технологии. 2023. Т. 29, № 3. С. 115—125. DOI: 10.17587/it.29.115-125.Rapoport G. N., Hertz А. G. Artificial and Biological Intelligences. Structural Similarity, Evolution, and Cognitive Processes, Moscow, Komkniga, 2005, 310 p. (in Russian).Рапопорт Г. Н., Герц А. Г. Искусственный и биологические интеллекты. Общность структуры, эволюция и процессы познания. М.: Комкнига, 2005. 310 с.Danilchenko V. I., Danilchenko E. V., Kureichik V. M. Representation of Matrix Architecture as a Work Field in the Problem of Initial Placement of VLSI Components, Problems of Develo ping Advanced Micro- and Nanoelectronic Systems (MES), 2022, no. 2, pp. 20—25, doi: 10.31114/2078-7707-2022-2-20-25 (in Russian).Данильченко В. И., Данильченко Е. В., Курейчик В. М. Представление матричной архитектуры в виде рабочего поля в задаче начального размещения компонентов СБИС / // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2022. № 2. С. 20—25. DOI: 10.31114/2078-7707-2022-2-20-25.