Методы и алгоритмы биоинспирированного поиска при размещении компонентов СБИС

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 24-71-00035

НазваниеМетоды и алгоритмы биоинспирированного поиска при размещении компонентов СБИС

Руководитель Данильченко Владислав Иванович, Кандидат технических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Южный федеральный университет" , Ростовская обл

Конкурс №97 - Конкурс 2024 года «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-507 - Автоматические и автоматизированные системы проектирования, моделирования и сопровождения

Ключевые слова Математические модели, конструкторское проектирование, размещение компонентов, электрические характеристики, тепловые характеристики, алгоритмы оптимизации, искусственный интеллект, машинное обучение, генетические алгоритмы, CAD-системы, интеграция, новые материалы, роботизированные системы, интеллектуальные технологии.

Код ГРНТИ50.51.00

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Разработка новых микроэлектронных устройств требует сокращения сроков и стоимости проектирования, учитывая рост количества компонентов. Методы систем автоматизированного проектирования и компьютерного моделирования являются ключевыми для создания сверхбольших интегральных схем (СБИС) в соответствии с быстро растущими требованиями. Снижение стоимости заказных СБИС достигается благодаря применению систем автоматизированного проектирования (САПР). В этих условиях актуальной становится проблема темпов разработки узлов аппаратуры, представляющих собой СБИС. В решении данной проблемы важно учитывать существование двух разных классов интегральных схем: стандартных (или крупносерийных) и заказных (матричных). Регулярно возрастающая сложность задачи размещения обусловлена тем, что современные СБИС могут содержать 10^8 и более элементов или подсистем рассматриваемой схемы (логических блоков) в рабочем поле кристалла. Новые тенденции в проектировании СБИС приводят к необходимости разработки алгоритмов на основе новых эффективных методов в рамках решения задач конструкторского этапа автоматизированного проектирования, в частности задачи размещения. Методы, основанные на моделях естественных эвристик в живой природе, образуют эффективный инструмент автоматизированного проектирования. К одной из основных задач конструкторского этапа проектирования относится задача размещения, которая является комбинаторной и относится к классу NP-полных. Поэтому использование алгоритмов полного перебора больших массивов данных затруднительно. Для оценки эффективности выполнения проектной процедуры размещения компонентов СБИС введен вектор критериев: суммарная длина межсоединений, а также критерий количества линейных сегментов (ЛС). Производство сверхбольших интегральных схем (СБИС) занимает длительное время из-за сложности процесса, усугубляемой ростом числа компонентов. Это требует модернизации проектирования, включая программное обеспечение, с применением эффективных гибридных стратегий поиска на основе эволюционного моделирования и биоинспирированных методов. Использование параллельных архитектур позволяет значительно повысить качество и эффективность поиска оптимальных решений в условиях полиномиального времени вычислений. При условии, что рассматриваемая задача является комбинаторной и относится к классу NP-полных, найти точное решение позволяют только методы полного перебора. Использование алгоритмов полного перебора затруднительно, поскольку они не могут соответствовать требованиям по времени поиска, так как полный перебор всех возможных вариантов решений займет большое количество времени. В настоящее время производителям необходимо оптимизировать размеры электронных устройств, формируя новые стандарты в проектировании сверхбольших интегральных схем (СБИС). Эти изменения сопровождаются улучшением качества, эффективности, производительности и снижением себестоимости производства. Для адаптации к новым требованиям в проектировании СБИС требуются эффективные алгоритмы автоматизированного проектирования, включая многомерные методы оптимизации. Методы, основанные на процессах, происходящих в живой природе, в частности, эволюционные и биоинспирированные методы, в настоящее время образуют эффективный инструмент для решения задач конструкторского этапа проектирования. В условиях обработки больших объемов данных разработка эффективных методов и алгоритмов многомерного биоинспирированного поиска для решения задачи размещения компонентов СБИС позволяет улучшить показатели целевой функции (ЦФ) по критериям числа линейных сегментов и суммарной взвешенной длины межсоединений, что подтверждает актуальность и важность выбранной тематики для современных САПР. Научная новизна проекта заключается в решение актуальной научной задачи повышение качества и эффективности проектных решений процедуры размещения на основе модифицированных методов и алгоритмов поиска, инспирированных живой природой.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2025 году
В течение отчетного периода в рамках проекта, направленного на разработку новых методов размещения компонентов на конструкторском этапе проектирования СБИС, получены научные и прикладные результаты, которые могут обеспечить основу для дальнейших исследований в данной области. В рамках первого этапа был осуществлён анализ существующих методов и разработаны новые подходы, использующие биоинспирированные алгоритмы, что позволило повысить эффективность проектирования СБИС. На первом этапе работы был проведён систематический обзор методов размещения компонентов СБИС, включая как классические подходы, так и более современные, основанные на искусственном интеллекте и биоинспирированных алгоритмах. Рассмотрены алгоритмы, такие как метод Лехмана и Хартмана для минимизации площади размещения, а также более новые методы, использующие генетические алгоритмы и имитацию отжига для решения многокритериальных задач. Выявлены основные проблемы, такие как высокая вычислительная сложность и застревание в локальных оптимумах, что требует применения более гибких и адаптивных методов. Основное внимание было уделено разработке модифицированных биоинспирированных алгоритмов, таких как генетические алгоритмы, имитирующие поведение белых кротов и стволовых клеток. Эти методы продемонстрировали высокую эффективность в ускорении поиска решений при проектировании СБИС. В частности, алгоритм, моделирующий поведение колоний белых кротов, показал способность избегать локальных оптимумов и значительно ускорил процесс поиска решения, в то время как методы, основанные на стволовых клетках, оказались полезными для многокритериальной оптимизации, включая минимизацию расстояний и улучшение электрических характеристик схем. На основе полученных результатов была разработана гибридная архитектура, объединяющая различные подходы, включая генетический поиск и методы, ориентированные на многокритериальную оптимизацию. Внедрение таких методов в процесс проектирования СБИС позволило существенно улучшить качество размещения, что продемонстрировали тесты с использованием гиперграфовых моделей схем различной сложности. Разработанные алгоритмы показали улучшение качества на 13% по сравнению с существующими (известными) решениями, а также сократили время поиска решений на 8–16%, что позволяет повысить эффективность проектных решений при ограниченных вычислительных ресурсах. Для повышения эффективности работы с проектными решениями был разработан новый механизм кодирования и декодирования, который улучшает представление решений и позволяет сократить время обработки данных. Этот механизм повышает точность и позволяет интегрировать его в существующие системы автоматизированного проектирования, что в свою очередь ускоряет процесс разработки и верификации СБИС. Завершив этап разработки алгоритмов, была проведена их программная реализация и тестирование. Экспериментальные результаты показали, что предложенные методы, включая биоинспирированные и гибридные подходы, обеспечивают более высокое качество и ускорение процесса проектирования СБИС, а также повышают устойчивость системы к изменениям условий проектирования. В ходе тестов с гиперграфовыми моделями схем различной сложности было подтверждено, что предложенные методы работают значительно быстрее и с лучшими результатами. Реализованные в рамках проекта методы и алгоритмы значительно улучшили процесс проектирования СБИС, позволив ускорить и повысить качество размещения компонентов. Разработанные биоинспирированные и гибридные подходы продемонстрировали высокую эффективность и могут быть использованы для автоматизации проектирования в условиях современных вычислительных ограничений. Результаты проекта также нашли отражение в научных публикациях и в средствах массовой информации, что подтверждает актуальность и практическую значимость выполненных работ. Результаты проекта привлекли внимание научного сообщества и были освещены в СМИ, в том числе в публикации пресс-службы ЮФУ (ИКТИБ) под заголовком «В ИКТИБ ЮФУ разработана новая система биоинспирированного поиска при размещении компонентов СБИС», что способствовало распространению знаний о новых решениях в области проектирования СБИС. Подробности доступны по ссылке: https://ictis.sfedu.ru/news/2024/12/24-71-00035/.

Публикации

1. Данильченко В.И., Курейчик В.В. Оценка эффективности и качества проектных решений при размещении фрагментов СБИС Журнал «Программные продукты и системы» Акционерное общество "Научно-исследовательский институт "Центрпрограммсистем" (Тверь), Данильченко В. И. Оценка эффективности и качества проектных решений при размещении фрагментов сверхбольших интегральных схем / В. В. Курейчик, В. И. Данильченко // Программные продукты и системы. – 2025. – № 4. – С. 617-629. – DOI 10.15827/0236-235X.152.617-629. (год публикации - 2025)
10.15827/0236-235X.152.617-629

2. Курейчик В.В., Данильченко В.И. Прогнозирование аномалий при проектировании СБИС научно-технический журнал "Информационные технологии", издательство «Новые технологии», Данильченко В. И. Прогнозирование аномалий при проектировании СБИС / В. В. Курейчик, В. И. Данильченко // Информационные технологии. – 2025. – Т. 31, № 12. – С. 659-669. – DOI 10.17587/it.31.659-669. (год публикации - 2025)
10.17587/it.31.659-669

3. Данильченко В.И., Данильченко Е.В., Гудков М.С., Кудрявцев И.А. Применение конволюционных нейронных сетей для решения задач автоматизированной диагностики и мониторинга технического состояния инженерных систем на основе методов машинного зрения Проблемы автоматизации. Региональное управление. Связь и акустика : сборник трудов XIII Всероссийской научной конференции и молодежного научного форума (Геленджик, 13–15 ноября 2024 года), Применение конволюционных нейронных сетей для решения задач автоматизированной диагностики и мониторинга технического состояния инженерных систем на основе методов машинного зрения / В. И. Данильченко, Е. В. Данильченко, М. С. Гудков, И. А. Кудрявцев // Проблемы автоматизации. Региональное управление. Связь и акустика : сборник трудов XIII Всероссийской научной конференции и молодежного научного форума, Геленджик, 13–15 ноября 2024 года. – Ростов-на-Дону - Таганрог: Южный федеральный университет, 2024. – С. 287-292. (год публикации - 2024)

4. Данильченко В.И. Оптимизация процедур размещения компонентов СБИС с использованием адаптивного алгоритма роя частиц с локальными лидерами ТРУДЫ МЕЖДУНАРОДНОГО НАУЧНО-ТЕХНИЧЕСКОГО КОНГРЕССА «ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ - 2024», Труды Международного научно-технического конгресса «Интеллектуальные системы и информационные технологии - 2024» («ИС & ИТ-2024», «IS&IT’24»). Научное издание в 2-х т. Т. 1. – Таганрог: Изд-во Ступина С.А., 2024. – 385 с. ISBN 978-5-6050434-47 ISBN 978-5-6050434-5-4 (Т. 1) (год публикации - 2024)

5. Курейчик В.В., Данильченко В.И., Данильченко Е.В. Маршрутизация автономных устройств в трёхмерном пространстве Труды СПИИРАН Санкт-Петербургский Федеральный исследовательский центр РАН (Санкт-Петербург) , Курейчик, В. В. Маршрутизация автономных устройств в трёхмерном пространстве / В. В. Курейчик, В. И. Данильченко, Е. В. Данильченко // Информатика и автоматизация. – 2025. – Т. 24, № 2. – С. 492-525. – DOI 10.15622/ia.24.2.5. (год публикации - 2025)
10.15622/ia.24.2.5