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

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

 

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


Номер проекта 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


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

 

Возможность практического использования результатов
Разработанные в рамках проекта методы и алгоритмы биоинспирированного поиска, архитектура комбинированного и многомерного поиска, а также созданный программно-алгоритмический комплекс ориентированы на автоматизацию конструкторского этапа проектирования сверхбольших интегральных схем (СБИС). Полученные результаты имеют высокий потенциал для практического использования в следующих направлениях. В промышленности полупроводниковых приборов и микроэлектроники разработанные методы позволяют существенно повысить качество размещения компонентов СБИС на кристалле, сократить время проектирования и снизить себестоимость разработки за счёт автоматизации трудоёмких проектных процедур. Применение предложенной метрики линейных сегментов и адаптивного механизма параметризации обеспечивает снижение энергопотребления и тепловыделения проектируемых схем, что особенно востребовано при создании энергоэффективных устройств для мобильной и встраиваемой электроники. Программно-алгоритмический комплекс может быть интегрирован в существующие системы автоматизированного проектирования для улучшения их функциональных характеристик. В сфере высокотехнологичного производства внедрение разработанных алгоритмов позволяет создать научно-технический задел для перехода к передовым технологиям проектирования микроэлектронной продукции, основанным на интеллектуальных производственных решениях и высокопроизводительных вычислительных системах. Это соответствует приоритетным направлениям научно-технологического развития Российской Федерации и способствует достижению технологического суверенитета в области микроэлектроники. В образовательной деятельности разработанные методы и алгоритмы внедрены в учебный процесс кафедры САПР им. В.М. Курейчика ИКТИБ Южного федерального университета при подготовке бакалавров и магистров по направлениям 09.03.02 «Информационные системы и технологии», 09.04.01 «Информатика и вычислительная техника», 09.06.01 «Информатика и вычислительная техника». Материалы проекта используются в лекционных курсах и лабораторных работах по дисциплинам, связанным с автоматизацией проектирования, интеллектуальными системами и методами оптимизации. В том числе при реализации авторского курса руководителя данного проекта ВПК 17 «Промышленные САПР» для бакалавриата 3 курса. Таким образом, результаты проекта обладают высокой практической значимостью и могут быть использованы для модернизации существующих и создания новых систем автоматизированного проектирования СБИС, а также для подготовки высококвалифицированных кадров в области микроэлектроники и информационных технологий.