Адаптивная параметризация метаэвристического алгоритма при размещении компонентов СБИС
Ключевые слова:
метаэвристические алгоритмы, адаптивная параметризация, динамическая модель, размещение компонентов СБИС, комбинаторная оптимизация, метрики поиска, топологический синтез, многомерное дискретное пространство, интеллектуальные системы проектированияАннотация
В работе рассматривается задача параметризации метаэвристического алгоритма размещения компонентов сверхбольших интегральных схем (СБИС) в условиях усложняющихся топологий и ограничений современных технологических норм. Актуальность исследования обусловлена ростом размерности проектируемых схем, увеличением плотности межсоединений и усложнением структуры пространства проектных решений, что ограничивает эффективность применяемых алгоритмов со статическими параметрами. Постановка задачи включает формирование комплекса проектных метрик, таких как длина соединений, плотность, площадь размещения, индекс пересечений и другие. Фиксированная параметризация метаэвристических алгоритмов не в полной мере учитывает динамику пространства поиска, что ограничивает качество принимаемых проектных решений. На основе анализа комплекса проектных метрик предложена динамическая модель, отражающая текущее состояние поискового процесса, включая уровень структурного разнообразия популяции и признаки стагнации. С учетом предложенной модели разработана структура адаптивного метаэвристического алгоритма с замкнутым контуром параметрического управления, где выполняется корректировка параметров для согласования интенсивности глобального и локального поиска. Научная новизна заключается в оригинальной конфигурации набора метрик (скорость улучшения целевой функции δt, разнообразие популяции Dt, локальная неоднородность ландшафта поиска Ht, индикатор стагнации St) и способе их интеграции в контур параметрического управления. В отличие от ресурсоёмких нейросетевых архитектур, требующих значительных вычислительных затрат и обучающих выборок, предложенная аналитическая модель обеспечивает интерпретируемость процесса адаптации и высокую вычислительную эффективность. Для подтверждения эффективности подхода построена программная подсистема, реализующая процесс моделирования и вычислительного эксперимента. Результаты экспериментов на тестовых топологиях различной размерности и плотности связей показали, что по сравнению с алгоритмами с фиксированной многоэтапной настройкой применение разработанного алгоритма позволило повысить интегральный показатель качества размещения на 8-15 % для структур с низкой плотностью связей и на 12-25 % для структур с высокой плотностью связей, уменьшить дисперсию результатов при множественных итерациях в 1,3-2,2 раза, сократить число циклов стагнации и снизить чувствительность к начальному состоянию популяции. Полученные результаты подтверждают повышение качества и эффективности проектных решений, устойчивость разработанного алгоритма размещения и свидетельствуют о практической применимости предложенного подхода. Статья будет полезна специалистам, занимающимся автоматизацией проектирования и интеллектуальным анализом при разработке.
Литература
2. Qiu Y., Xing Y., Zheng X., Gao P., Cai S., Xiong X. Progress of Placement Optimization for Accelerating VLSI. Physical Design // Electronics. 2023. vol. 12. no. 2. pp. 1–23. DOI: 10.3390/electronics12020337.
3. Курейчик В.В. Вычислительные модели эволюционных и роевых биоэвристик (обзор) / В.В. Курейчик, С.И. Родзин // Информационные технологии. 2021. Т. 27. №10. С. 507–520. DOI: 10.17587/it.27.507-520.
4. Курейчик В.М., Данильченко В.И. Генетический алгоритм планирования размещения СБИС / В.М. Курейчик, В.И. Данильченко // Известия ЮФУ. Технические науки. 2019. №2. С. 26–34.
5. Данильченко В.И., Курейчик В.В. Оценка эффективности и качества проектных решений при размещении фрагментов сверхбольших интегральных схем // Программные продукты и системы. 2025. Т. 38. №4. С. 617–629. DOI: 10.15827/0236-235X.152.617-629.
6. Agnesina A., Chang K., Lim S.K. VLSI Placement Parameter Optimization using Deep Reinforcement Learning // Proceedings of the 2020 International Conference on Computer-Aided Design (ICCAD '20). 2020. pp. 1–9. DOI: 10.1145/3400302.3415690.
7. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой / 3-е изд., испр. // М.: Издательство МГТУ им. Н. Э. Баумана. 2021. 448 с.
8. Курейчик В.В. Вычислительные модели биоэвристик, основанных на физических и когнитивных процессах (обзор) / В.В. Курейчик, С.И. Родзин // Информационные технологии. 2021. Т. 27. №11. С. 563–574. DOI: 10.17587/it.27.563-574.
9. Абас В.М.А. Приближенные методы оптимального размещения элементов электрических и электронных цепей // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. 2021. №2. С. 18–26. DOI: 10.17213/1560-3644-2021-2-18-26.
10. Родзин С.И. Биоэвристики: теория, алгоритмы и приложения: Монография / С.И. Родзин, Ю.А. Скобцов, С.А. Эль-Хатиб / Чебоксары: ИД «Среда». 2019. 224 с. DOI: 10.31483/a-54.
11. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР / Учеб. для вузов по спец. "Конструирование и технология радиоэлектрон. средств", "Конструирование и технология электрон. вычисл. средств" // Москва: Радио и связь. 1990. 52 с.
12. Sherwani N.A. Algorithms for VLSI Physical Design Automation / New York: Springer Science & Business Media. 2013. 488 p.
13. Амирханов А.В., Волков С.И., Кизиев С.А., Макарчук В.В., Сухов А.Г., Шахнов В.А. Методы оценки качества конструктивных решений, применяемых в СБИС / Международный форум "Микроэлектроника-2016". Тезисы докладов 2-ой научной конференции форума // М.: Рекламно-издательский центр "ТЕХНОСФЕРА". 2016. С. 321–323.
14. Иванов В.К., Думина Д.С., Семенов Н.А. Определение весовых коэффициентов для аддитивной фитнес-функции генетического алгоритма // Программные продукты и системы. 2020. Т. 33. №1. С. 47–53.
15. Plummer J.D., Griffin, P.B. Integrated Circuit Fabrication: Science and Technology // Cambridge University Press. 2023 678 p.
16. Bykovsky N.V., Harutyunyan R.V., Nasedkin A.V. Numerical modeling and optimization results for the placement of irregularly shaped elements on a multidimensional switching field with complex topology // T-Comm. 2024. vol. 18. no. 9. pp. 48–54.
17. de Souza L.A.M., da Silva J.E.H., Chaves L.J., Bernardino H.S. A benchmark suite for designing combinational logic circuits via metaheuristics // Applied Soft Computing. 2020. vol. 91. 106246 p.
18. Govia L.C.G., Jurcevic P., Wood C.J., et al. A randomized benchmarking suite for mid-circuit measurements // New Journal of Physics. 2023. vol. 25. no. 12. pp. 1-28.
19. Гладков Л.А., Лейба С.Н., Тарасов В.Б. Разработка и программная реализация гибридного алгоритма решения оптимизационных задач автоматизированного проектирования // Программные продукты и системы. 2018. Т. 31. №3. С. 569–580. DOI: 10.15827/0236-235X.031.3.569-580.
20. Лобанов А.В., Егоров А.А., Викторова В.В. Использование пакета DEAP для решения задач оптимизации / Актуальные вопросы современных научных исследований: сборник статей IX Международной научно-практической конференции // Пенза: Наука и Просвещение. 2024. С. 63–66.
Опубликован
Как цитировать
Раздел
Copyright (c) Владислав Иванович Данильченко, Владимир Викторович Курейчик, Евгения Владимировна Данильченко
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).