Методика и алгоритмы размещения библиотечных элементов с применением машинного обучения для автоматизации проектирования микросхем на базовых структурированных кристаллах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Можжухина Арина Валерьевна

• Можжухина Арина Валерьевна
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Можжухина Арина Валерьевна

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

ВВЕДЕНИЕ

Глава 1. Обзор современного состояния методов и средств размещения библиотечных элементов микросхем на этапе топологического проектирования

1.1. Общие методы размещения библиотечных элементов на этапе топологического проектирования

1.2. Программные средства создания топологии БИС

1.3. Особенности проектирования БИС на БСК

1.4. Постановка задач диссертационного исследования

Выводы по главе1

Глава 2. Формализация задачи о размещении библиотечных элементов на БСК на этапе топологического проектирования

2.1. Формализация процесса поиска аппроксимированной оптимальной стратегии размещения библиотечных элементов

2.2. Разработка окружающей среды размещения библиотечных элементов на БСК для агента обучения с подкреплением

2.3. Выбор архитектуры нейронных сетей актора для предсказания размещения библиотечных элементов БИС и критика для оценивания

текущей стратегии

Выводы по главе

Глава 3. Разработка методики, графовой структуры и алгоритмов размещения библиотечных элементов на БСК

3.1. Разработка методики размещения библиотечных элементов на БСК

3.2. Разработка графовой структуры и алгоритма конвертации характеристик проекта БИС и БСК

3.3. Разработка алгоритма оценки результатов размещения библиотечных элементов на основе граничных критериев

3.4. Модификация алгоритма послойной кластеризации графа БИС

Выводы по главе

Глава 4. Программная реализация разработанных решений в виде тестового модуля

4.1. Разработка схемы данных окружающей среды и накопления данных о полученных конечных размещениях

4.2. Разработка структурной схемы и программная реализация предложенных методики и алгоритмов

4.3. Верификация предложенного решения на основе оценок

эффективности и достоверности

Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. Акты внедрения

ПРИЛОЖЕНИЕ 2. Результаты интеллектуальной деятельности

ПРИЛОЖЕНИЕ 3. Листинги фрагментов программы

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ БИС - большая интегральная схема БК - базовый кристалл БМК - базовый матричный кристалл БСК - базовый структурированный кристалл ГЖПП - гибко-жёсткая печатная плата МК - Монте-Карло МО - машинное обучение ОИС - обобщенная итерация по стратегиям ОП - оперативная память

ПЛИС - программируемые логические интегральные схемы

САПР - система автоматизированного проектирования

СФ-блоки - сложно функциональные блоки

ТЗ - техническое задание, в данном случае, на микросхему

ЭВМ - электронная вычислительная машина

CNN - сверточная нейронная сеть (convolutional neural network)

DRL - глубокое обучение с подкреплением (deep reinforcement learning)

FCNN - полносвязная нейронная сеть (full-connected neural network)

GIL - глобальная блокировка интерпретатора (global interpreter lock)

GNN - графовая нейронная сеть (graf neural network)

HPWL - полупериметр соединения (half perimeter wire length)

PPO - ближайшая оптимизация стратегии (proximal policy optimization)

RNN - рекурентные нейронная сеть (recurrent neural network)

SAC - мягкий актор-критик (soft actor-critic)

TD - временная разница (temporal differences)

WNS - худшее время запаздывания (worst negative slack)

Введение диссертации (часть автореферата) на тему «Методика и алгоритмы размещения библиотечных элементов с применением машинного обучения для автоматизации проектирования микросхем на базовых структурированных кристаллах»

ВВЕДЕНИЕ

Актуальность диссертационного исследования

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

При проектировании специализированных больших интегральных схем (БИС) появляются дополнительные сложности, особенно при работе с новой моделью конструкции кристаллов, а именно с базовым структурированным кристаллом (БСК). Данное направление развивается на ряде предприятий, в частности в НПК «Технологический центр» и ОАО «МНИПИ». БСК состоит из зафиксированных посадочных мест по периметру кристалла и регулярной матрицы разрешенных точек привязки библиотечных ячеек. Таким образом, в зависимости от размещаемых элементов, можно получить как топологию базовых слоев базового или базового матричного кристалла (БК или БМК), так и заказную микросхему. Основную сложность представляет то, что в качестве библиотечных элементов в одном проекте выступают не только стандартные функциональные ячейки, но и сложно-функциональные блоки (СФ-блоки) [3, 4]. Это приводит к необходимости применять вместо алгоритмов для стандартных элементов (standart cells), которые подходят для большинства других кристаллов, алгоритмы для разноразмерных элементов (mixed-sized).

Наравне с детерминированными алгоритмами размещения существует возможность применения вероятностных подходов, в частности методов машинного обучения (МО) [5]. В настоящее время применение МО на производстве неуклонно растет. Успешный опыт по применению МО в разработке САПР микроэлектроники таких крупных зарубежных компаний, как Google [6] и Cadence [7], подтверждают необходимость исследований в этом направлении. Одним из вариантов, выбранным в данной диссертационной работе, является применение глубокого обучения с подкреплением. В этом случае обучение происходит на опыте - данных от пошагового размещения элементов одной микросхемы. В качестве аппроксиматора [8, 9] для поиска зависимостей в этих данных и обобщения выбрана нейронная сеть. На каждой эпохе обучения улучшаются веса этой нейронной сети, которые и являются стратегией. В процессе размещения эти веса используются вместе с маской открытых областей для предсказания наилучшего положения для конкретного элемента. Улучшение происходит на основе оценки размещения, полученного после генерации данных текущей микросхемы. Таким образом, в процессе обучения выполняется поиск аппроксимированной оптимальной стратегии размещения. Так как большинство алгоритмов размещения работает со случайного начального распределения элементов, то использование МО для генерации начального приближения позволит сократить время на оптимизацию. В связи с этим, актуальность обретает разработка методики и алгоритмов на базе глубокого обучения с подкреплением для повышения скорости и качества размещения элементов БИС на БСК

Степень разработанности темы исследования

Указанными проблемами на протяжении ряда последних лет занимались известные зарубежные ученые и разработчики САПР Yibo Lin, David Z. Pan, Haoxing Ren, Brucek Khailany, Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu, Peiyu Liao, Siting Liu, Zhitang Chen, Wenlong Lv, Yibo Lin, Bei Yu, Duane S. Boning, Ibrahim (Abe) M. Elfadel, Xin Li, G. Lu, S. Areibi, а также коллективы

российских разработчиков под руководством крупных отечественных ученых и разработчиков САПР С.В. Гаврилова, М.М. Соколовской, Е.В. Кузнецова, М.Н. Рычагова, М.В. Макушина, А.В. Фоминой, В.В. Мартынова и др. Кроме этого, в исследованиях участвовали такие крупные компании, как Google (в т.ч. Goldie A., Mirhoseini A.), Cadence (САПР Innovus и САПР с МО Cerebrus), Synopsys (САПР с МО DSO.ai) и др.

Цель работы и задачи исследования

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

В соответствии с поставленной целью в работе решаются следующие задачи:

1) разработка методики поиска аппроксимированной оптимальной стратегии размещения библиотечных элементов на БСК с использованием глубокого обучения с подкреплением;

2) разработка алгоритма конвертирования характеристик исходного проекта БИС, БСК и граничных критериев в модель окружающей среды и графовую структуру;

3) разработка алгоритма оценки полученного размещения на основе граничных критериев для формирования награды агента в процессе обучения;

4) модификация алгоритма послойной кластеризации графовой структуры БИС из плоских и иерархических списков соединений для параллельного размещения элементов.

Методы исследования

Решение поставленных задач основано на использовании теории графов, теории управления, теории вероятностей, методов математического анализа и методов оптимизации, теории вычислительных процессов, дискретной математики, эвристических и стохастических подходов, математического и

функционального моделирования, теории искусственных нейронных сетей, глубокого обучения с подкреплением.

Научная новизна работы

1. Предложена методика поиска аппроксимированной оптимальной стратегии размещения библиотечных элементов на БСК с использованием обучения с подкреплением. Это позволяет обобщить опыт размещения различных схем, что в процессе тестирования на реальных проектах БИС повысило качество итогового решения.

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

3. Предложен алгоритм оценки полученного размещения на основе граничных критериев. Состав и веса граничных критериев подбирались исходя из специфики БСК и требований к конечному размещению с целью достижения компромисса по точности и скорости процесса корректировки аппроксимированной стратегии в процессе глубокого обучения с подкреплением.

Достоверность полученных результатов подтверждается соответствием результатов теоретического анализа реальному функционированию разработанного автором диссертации тестового модуля и верификацией экспериментальных данных, полученных при размещении элементов БИС специалистами НПК «Технологический центр». Результаты работы подтверждены свидетельствами об официальной регистрации программ для ЭВМ №2025612080, №2024691898, №2023664943. Диссертационная работа является составной частью исследовательских мероприятий в составе ОКР «Разработка и освоение в производстве комплекта доверенных микросхем и микромодулей специального назначения, а также

средств обеспечения доверенности процесса их проектирования и изготовления», шифр «Доверие» (идентификационный код закупки № 201770559633977030100101600017219000), дата подписания 28.12.2020.

Практическая ценность работы заключается в следующем:

1. Применение методики поиска аппроксимированной оптимальной стратегии размещения библиотечных элементов на БСК показывает стабильный результат работы на широком наборе промышленных проектов БИС до 20 тысяч элементов при сохранении или улучшении показателей размещения по сравнению с некоторыми действующими САПР после 2 эпохи обучения.

2. Алгоритмы конвертирования и оценки полученного размещения позволили обучаться и размещать проекты БИС с разными кристаллами, в том числе БСК.

3. Модифицированный алгоритм кластеризации позволил работать на больших схемах (от 200 тысяч элементов) на ЭВМ с малыми ресурсами (процессор с 6 ядрами 4.10 ГГц и технологией гиперпоточности, объем ОП 64 Гб).

4. Предложенные в диссертации методика и алгоритмы положены в основу программного модуля и внедрены для адаптации к специфике проектирования в НПК «Технологический центр» и в учебный процесс СПИНТех МИЭТ, что подтверждено актами о внедрении.

Личный вклад автора

Все основные результаты диссертационной работы получены автором лично, а именно:

1) методика поиска аппроксимированной стратегии размещения библиотечных элементов на БСК;

2) алгоритм конвертирования характеристик проекта микросхемы и граничных критериев в модель окружающей среды и графовую структуру;

3) алгоритм оценки полученного размещения на основе граничных критериев;

4) модифицированный алгоритм послойной кластеризации графовой структуры БИС из плоских и иерархических списков соединений;

5) тестовый модуль.

Реализация полученных результатов

Все работы по разработке и модификации алгоритмов и методики, а также программной реализации проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе СПИНТех НИУ «МИЭТ» в материалах курсов «Большие данные», «Введение в обучение с подкреплением», а также в НПК «Технологический центр» на территории отдела интегральных микросхем.

Результаты и положения, выносимые на защиту

1. Методика поиска аппроксимированной стратегии размещения библиотечных элементов на БСК для обобщения опыта предыдущих размещений.

2. Алгоритм конвертирования характеристик проекта БИС с БСК и граничных критериев в графовую структуру хранения и модель окружающей среды для преобразования начальных данных размещения.

3. Алгоритм оценки полученного размещения на основе граничных критериев, основанных на базовых и дополнительных требованиях к микросхемам.

4. Модифицированный алгоритм послойной кластеризации графовой структуры микросхемы для параллельного размещения элементов.

Апробация результатов

Результаты диссертационной работы докладывались и обсуждались на следующих конференциях:

1. Тринадцатая международная конференция «Управление развитием крупномасштабных систем» (MLSD'2020), г. Москва, 2020.

2. Международная научно-техническая конференция ТРИС-2020, г. Москва, 2020.

3. Юбилейная Х Международная научно-практическая конференция имени А.И. Китова «Информационные технологии и математические методы в экономике и управлении» ИТиММ-2020, г. Москва, 2020.

4. Международная научно-практическая конференция «Актуальные проблемы информатизации в цифровой экономике и научных исследованиях», г. Москва, 2021.

5. XXIV международная научная конференция "Инжиниринг предприятий и управление знаниями (ИП&Уз-2021)", г. Москва, 2021.

6. XXXIII Международная научная конференция «Исследования молодых ученых», г. Казань, 2022.

7. Открытая конференция ИСП РАН им. В.П. Иванникова, г. Москва, РАН, 2022.

8. International Conference on Advances in Environment Research. Conference proceedings. Madrid, Spain. 30 марта 2023.

9. XXX Всероссийская межвузовская научно-техническая конференция студентов, аспирантов и молодых ученых «МИКРОЭЛЕКТРОНИКА и ИНФОРМАТИКА-2023», г. Москва, 2023.

10. XXV Международная научная конференция «Системы компьютерной математики и их приложения», г. Смоленск, 2024.

11. Открытая конференция ИСП РАН им. В.П. Иванникова, г. Москва, РАН, 2024.

Публикации

Основное содержание диссертации отражено в 21 работах, в том числе 3 статьи в журналах, входящих в перечень, утвержденный ВАК и 1 статья в журнале, входящем в базы научного цитирования GeoRef (ВАК), 3 свидетельства о государственной регистрации программы для ЭВМ, 8 - в журналах, входящих в базы научного цитирования РИНЦ; 1 - в журнале, входящем в базы научного цитирования SCOPUS.

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения, списка использованной литературы и приложений, содержащих результаты интеллектуальной деятельности, листинги программ и акты о внедрении результатов работы. Общий объем диссертационной работы - 161 страница текста, в том числе 10 таблиц и 27 рисунков.

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

В первой главе рассмотрены методы и средства размещения библиотечных элементов микросхем на этапе топологического проектирования, приведен анализ широкого спектра различных существующих открытых и анонсированных на момент проведения исследований решений в целевой области. Кроме этого приведены отличительные особенности кристаллов БСК от остальных используемых в НПК ТЦ.

Вторая глава посвящена формализации поиска аппроксимированной оптимальной стратегии размещения библиотечных элементов на БСК с целью повышения скорости генерации и качества размещения библиотечных элементов на БСК в процессе топологического проектирования с применением марковских процессов принятия решений и обобщенной итерации по стратегиям.

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

Четвертая глава содержит сведения о программной реализации разработанных методики и алгоритмов в виде тестового модуля в составе

САПР «Ковчег». Рассматривается подтверждение эффективности полученных результатов на основе проведенных экспериментов.

В заключении диссертации отражены наиболее значимые результаты выполненной диссертационной работы в рамках решения поставленной научно-технической проблемы исследования.

В приложениях представлены фрагменты программной реализации агента обучения с подкреплением, свидетельства о государственной регистрации программы для ЭВМ и акты о внедрении результатов работы.

Глава 1. Обзор современного состояния методов и средств размещения библиотечных элементов микросхем на этапе топологического проектирования

В главе представлен аналитический обзор основных классических и современных методов [10], используемых в задаче размещения библиотечных элементов больших интегральных схем (БИС) на кристалле. Кроме этого, приведены некоторые алгоритмы, программные средства и основные особенности подходов к размещению элементов [11, 12] и последующей трассировке. Особое внимание уделяется направлению, связанному с машинным обучением (МО) [13]. Также приведены особенности новой модели конструкции кристалла - базового структурированного кристалла (БСК) - и его отличия от других кристаллов специализированных БИС.

1.1. Общие методы размещения библиотечных элементов на этапе топологического проектирования

Для создания полноценной БИС необходимо разместить библиотечные элементы микросхемы на кристалл согласно их связям между собой и определенным критериям, а затем соединить их - выполнить трассировку. Граничные критерии формируются на основе требований к микросхеме. Например, требование минимизации расстояния между элементами. За все время существования микроэлектроники [14, 15] задача размещения решалась разными способами [16, 17]. Несмотря на то, что трассировка выполняется после размещения, многие проблемы размещения удается выявить только в разведенной топологии [18]. Это в частности усложняет процесс.

На настоящий момент основные этапы размещения [19] и трассировки выполняются чаще всего в следующем порядке.

- Планировка кристалла. В этот этап входит разбиение кристалла на посадочные места, определение точек привязки, разводка шин земли и питания, размещение посадочных мест под периферийные элементы [20, 21] и другое в соответствии с моделью конструкции кристалла. Этот этап выполняется один раз, а кристалл используется при проектировании

микросхем. Чаще всего в семейство входит ряд кристаллов разного размера. Например, в семействе БИС НПК ТЦ 5529 всего 17 БСК разного типа с 10 разными размерами [22] с разным количеством посадочных мест под элементы и периферию. Этапы далее осуществляются при проектировании каждой микросхемы.

- Препланирование. На этом этапе выполняется предразмещение и закрепление на кристалле каких-то элементов (например, периферии, элементов памяти) или общее определение областей, выделяемых разработчиком для тех или иных крупных составляющих микросхемы. Дополнительно выполняется удаление из схемы всех буферов, добавленных на этапе логического синтеза.

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

- Детальное размещение. В процессе выполнения этого этапа размещение корректируется, снижается процент возможного перекрытия элементов и осуществляется оптимизация характеристик размещения (например, снижение суммарного расстояния между элементами, путем локальных перестановок или обмена элементов).

- Легализация. Данный этап чаще всего проводится в процессе детального размещения. В него в том числе входит устранение перекрытий, проверка элементов на размещение согласно точкам привязки и шинам земли и питания.

- Проверка на соответствие временным задержкам. На этом этапе в полученном размещении проверяется, успевают ли все сигналы прийти в

нужные промежутки времени. В случае нарушения задержек сигнала выполняется повышение мощности элементов и/или добавление буферов.

- Детальное размещение - корректировка размещения добавленных буферов и элементов.

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

- Размещение цепей синхронизации. В ходе этого этапа выполняется размещение инверторов и буферов дерева синхронизации.

- Детальное размещение элементов, добавленных в размещение на предыдущем этапе.

- Трассировка.

В данной диссертационной работе основное внимание уделяется глобальному и детальному размещениям и легализации. В рамках этого рассматривались основные подходы, приведенные в табл. 1.1 [23, 24].

Самыми эффективными и при этом первыми, но самыми медленными и затратными, в поиске решения задачи размещения библиотечных элементов микросхем являются жадные алгоритмы. Жадные алгоритмы - одна из разновидностей эвристических методов. Эвристические методы отличаются тем, что основаны на каких-либо практических методах или явлениях и не являются гарантированно точными или оптимальными. Они находят решение, достаточное для поставленной задачи. Жадные алгоритмы действуют, согласно жадной стратегии принятия решений, т.е. на каждом шаге выбирают локальное оптимальное решение, не задумываясь о будущем. Кроме этого их выбор не опирается на действия, принятые в прошлом.

Табл. 1.1 - Анализ методов и средств размещения элементов микросхем

Методы, основные характеристики Средства Недостатки

Метод имитации отжига. Случайный перебор вариантов распределения элементов БИС. Dragon Алгоритм стохастический и не гарантирует нахождения оптимального состояния. Требует много времени и ресурсов.

Генетические алгоритмы. Основаны на эволюционных процессах. Обладают горизонтальной масштабируемостью (возможности процессора). Synchronous Island GA Стойкость к попаданию в локальные оптимумы. Все еще медленно находит глобальное решение и требует много ресурсов.

Итерационный подход, в частности дихотомический. Основан на понижении размерности задачи. CAPO Feng Shui Требует решения внутренней NP-полной задачи. Отсутствие гарантии нахождения решения. Требует много времени и ресурсов.

Аналитические и силовые методы. Задача преобразуется в задачу механики или физики. Например, «растаскивание» элементов-частиц электромагнитными силами. FastPlace ePlAce RePlace NTUplace3 DREAMPlace Сложная реализация. Требует много времени и ресурсов при большом количестве элементов и соединений.

Методы на основе обучения с подкреплением. Предсказывают начальное или конечное положение элементов. AlphaChip (Google) Cerebrus (Cadence) Текущая реализация AlphaChip (Google) выполнена для процессоров, а Cerebrus (Cadence) - для всего процесса разработки микросхемы. Нет возможности влиять на наградную функцию и стратегию (нейронную сеть) для включения специфических требований. Все схемы хранятся не в виде netlist, а в protocol buffer (Google).

Однако жадные алгоритмы показывают себя более быстрыми в сравнении с альтернативными вариантами: динамическое программирование и алгоритмы такого типа, как разделяй и властвуй. Для применения жадного алгоритма, задача должна обладать следующими свойствами:

- применимость принципа жадного выбора, т.е. локальные оптимальные выборы могут привести к глобальному оптимальному решению;

- оптимальность подзадач, т.е. наличие локального оптимального решения на каждом шаге.

С ростом количества элементов в микросхемах, такие алгоритмы

становятся крайне неэффективными - в худшем случае необходимо перебрать к

N

различных вариантов постановок элементов (1.1)

(1.1)

™ (Ы-К)! К }

где А^ - количество вариантов размещений, N - количество посадочных мест БСК, К - количество элементов БИС.

Одним из улучшений жадных алгоритмов является метод имитации отжига [25], также относящийся к эвристическим алгоритмам. Он основывается на физическом процессе, происходящем при отжиге металлов во время кристаллизации веществ. Общий алгоритм действий похож: на каждом шаге алгоритм выбирает локальное оптимальное решение или с некоторой вероятностью выбирает неоптимальное, т.е. в основе используется так называемая е-жадная стратегия принятия решений. Процесс происходит до некоторого значения к. Применительно к задаче о размещении: берется начальное размещение элементов, которое путем перестановок элементов пытаются улучшить, принимая или отвергая преобразования в соответствии с критериями оптимизации и вероятностями. Элемент для перестановки выбирается на основе выбранного вероятностного распределения. Основная часть используемых стандартных алгоритмов размещения элементов является модификацией эвристических алгоритмов или их распараллеленным вариантом.

Из основных минусов использования данного метода можно выделить значительные затраты времени на его работу, так как метод работает до тех пор, пока сумма длин расстояний между элементами не станет близка к заданной. При большом количестве элементов алгоритм может минимизировать сумму до бесконечности даже при использовании технологий параллелизма. Соответственно, суждение об оптимальности получаемого размещения является субъективным. Однако, по сравнению с генетическими алгоритмами, по Ингбергу, в большинстве задач метод не проигрывает, а на многих - даже выигрывает.

Основные алгоритмы данного вида: Dragon, TimberWolf.

Отдельный интерес в методах размещения элементов представляют генетические алгоритмы [26]. Хотя они и не получили широкого распространения и основной пик интереса к ним был в 2000-х годах, все еще предпринимаются попытки совершенствования данных методов за счет развития процессоров, так как в их основе лежит процесс параллелизма, т.е. использования возможностей компьютера по выполнению нескольких операций одновременно за счет высокой тактовой частоты, количества ядер и технологии hyperthreading у процессора [27]. Помимо параллелизма отличительной чертой этих методов является большой набор пространства для решений за счет скрещиваний и мутаций. Этот механизм, в частности, спасает от застревания в локальных оптимумах позволяя искать различные варианты.

Основное преимущество генетических алгоритмов заключается в относительной стойкости к попаданиям в локальные оптимумы. Главным недостатком является медлительность при поиске даже приближенного глобального оптимума. Это связано со сложностью задачи и необходимости создавать достаточно большие популяции в процессе поиска решения.

Основные алгоритмы данного вида: Synchronous, Island GA, алгоритм размещения элементов на гибко-жёсткой печатной плате (ГЖПП).

Одним из широко используемых базовых методов является итерационный подход, и его частность - дихотомический. В их основе стоит

процесс постепенного понижения размерности задачи. Применительно к задаче размещения:

- разбить множество элементов на подмножество так, чтобы число связей между ними было минимально;

Список литературы диссертационного исследования кандидат наук Можжухина Арина Валерьевна, 2025 год

Список литературы

1. Шведов С.В., Солодуха В.А. Программные и аппаратные трояны -способы внедрения и методы противодействия. Первая техническая энциклопедия В 2-х книгах. М.: Техносфера, 2018. 1318 с. ISBN: 9785-94836-524-4.

2. Гагарина Л.Г., Гайдук И.О., Кремер Е.А., Можжухина А.В. Эффективный метод локализации ошибок при проектировании специализированных БИС. Изв. вузов. Электроника. - 2019. - Т. 24. - № 5.

3. Шведов С.В., Солодуха В.А. Программные и аппаратные трояны -способы внедрения и методы противодействия. Первая техническая энциклопедия В 2-х книгах. М.: Техносфера, 2018. 1318 с. ISBN: 9785-94836-524-4.

4. Отдел интегральных микросхем [Электронный ресурс]: Общие сведения о БСК и его особенностях. URL: http://asic.ru/design/design_on_29/General_BSC (дата обращения: 10.02.2025).

5. Отдел интегральных микросхем [Электронный ресурс]: Общие сведения о специализированных БИС. URL: http://asic.ru/design/general_information/ (дата обращения: 10.02.2025).

6. Dan Garisto Google AI beats top human players at strategy game StarCraft II // Nature. - 2019. DOI: https://doi.org/10.1038/d41586-019-03298-6.

7. Goldie A., Mirhoseini A. Placement Optimization with Deep Reinforcement Learning // Proceedings of the International Symposium on Physical Design. - 2020. - C. 2-7. DOI: https://doi.org/ 10.1145/3372780.3378174.

8. Cadence Design Systems, Inc. [Электронный ресурс]: AI in Chip Design URL: https://www.cadence.com/en_US/home/explore/ai-chip-design.html (дата обращения: 10.02.2025).

9. Liu D., Wei Q., Yan P. Generalized Policy Iteration Adaptive Dynamic Pro-gramming for Discrete-Time Nonlinear Systems // IEEE Transactions on Sys-tems, Man, and Cybernetics: Systems. - vol. 45, no. 12, 2015. - P. 1577-1591. doi: 10.1109/TSMC.2015.2417510.

10.Morales M. grokking Deep Reinforcement Learning. Manning Publications Co, 2020. 472 c. ISBN: 9781617295454.

11.Черников Б.В., Можжухина А.В., Черникова Е.А. Методы решения задачи о размещении элементов БИС // Информатизация и связь. -2020. - № 2. - С. 52-60.

12.Черников Б.В., Можжухина А.В., Черникова Е.А. Критерии и методы размещения элементов для проектирования БИС // Технологии разработки информационных систем ТРИС2020: материалы конференции. - Таганрог: Издательство ЮФУ, 2020. - С. 11-16.

13.Черников Б.В., Можжухина А.В., Черникова Е.А. Анализ методов размещения элементов при проектировании специализированных БИС // Управление развитием крупномасштабных систем MLSD'2020: труды тринадцатой международной конференции, 28-30 сентября 2020 г., Москва / под общей редакцией С.Н. Васильева, А.Д. Цвиркуна / - С. 792-798. DOI: 10.25728/mlsd.2020.0792.

14.Макушин М.В., Фомина А.В. Искусственный интеллект и рентабельность как движущие факторы развития САПР // Электроника: наука, технология, бизнес. - 2019. - №4 (185). - С. 90100. DOI: 10.22184/1992-4178.2019.185.4.90.100.

15. Макушин М., Мартынов В. Некоторые аспекты развития САПР // Электроника: наука, технология, бизнес. - 2020. - №1 (192). - С. 9099. DOI: 10.22184/1992-4178.2020.192.1.90.99.

16.Макушин М.В. Состояние рынка микроэлектроники с 1989 года по настоящее время // ЭКСПРЕСС-ИНФОРМАЦИЯ по зарубежной электронной технике - 50 лет с отраслью. - 2021. - №24-25 (67486749). - С. 23-28. ISSN: 2500-3844.

17.Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure. Second Edition. -Springer Cham, 2022. - 317 c.

18.G. Lu, S. Areibi An island-based GA implementation for VLSI standard-cell placement // Genetic and Evolutionary Computation Conference. Seattle, WA, USA, Proceedings, Part II, Июнь 26-30. - 2004. - С. 11381150. DOI: https://doi.org/10.1007/978-3-540-24855-2_123.

19.Гаврилов С.В., Денисов А.Н., Коняхин В.В., Соколовская М.М. [под ред. Саурова А.Н.] Полузаказные БИС на БМК серий 5503 и 5507. В 4 кн. Кн.2: Система автоматизированного проектирования «Ковчег 3.04». М.: Техносфера, 2019. 308 с. ISBN: 978-5-94836-443-8.

20. Черников Б.В., Можжухина А.В., Черникова Е.А. The current state of the problem on the placement of LSI elements // Information Technologies and Mathematical Methods in Economics and Management IT&MM 2020: Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)". - С. 249-260.

21. Денисов А.Н., Коняхин В.В. [под ред. Саурова А.Н.] Полузаказные БИС на БМК серий 5503 и 5507. В 4 кн.: Практическое пособие. Кн. 1: Методология проектирования и освоение производства. М.: Техносфера, 2019. 200 с. ISBN: 978-5-94836-442-1.

22.Jinjun Xiong, Yiu-Chung Wong, E. Sarto, Lei He Constraint driven I/O planning and placement for chip-package co-design // Asia and South Pacific Conference on Design Automation. - 2006. - C. 6. DOI: 10.1109/ASPDAC.2006.1594683.

23.Гаврилов С. В., Денисов А. Н., Коняхин В. В., Малашевич Н. И., Фёдоров Р. А. СЕМЕЙСТВО СЕРИЙ БАЗОВЫХ МАТРИЧНЫХ КРИСТАЛЛОВ // Известия вузов. Электроника. 2015. №5. URL:

https://cyberleninka.ru/article/n/semeystvo-seriy-bazovyh-matrichnyh-kristallov (дата обращения: 23.06.2025).

24.Гайдук И.О., Можжухина А.В. Методы машинного обучения в области разработки отечественных систем автоматизированного проектирования // Актуальные проблемы информатизации в цифровой экономике и научных исследованиях. Сборник статей IV Научно-практической конференции с международным участием. Москва, 2024. С. 49-54.

25.Gi-Joon Nam, Jason Cong Modern Circuit Placement. Best Practices and Results. Springer Science+Business Media, 2007. 327 с. ISBN: 978-0387-36837-5 DOI: https://doi.org/10.1007/978-0-387-68739-1.

26.Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing // Science. - 1983. - Т. 220, № 4598. - C. 671-680. DOI: https://doi.org/10.1126/science.220.4598.671.

27.Cohoon J.P., Paris W.D. Genetic Placement // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1987. - Т. 6, № 6. - C. 956-964. DOI: 10.1109/TCAD.1987.1270337.

28.Esbensen H. A genetic algorithm for macro cell placement // Proceedings EURO-DAC '92: European Design Automation Conference. - 1992. - С. 52-57. DOI: 10.1109/EURDAC.1992.246265.

29. Shahookar K., Mazumder P. A genetic approach to standard cell placement using meta-genetic parameter optimization // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1990. - Т. 9, №. 5. - С. 500-511. DOI: 10.1109/43.55180.

30.Kleinhans J.M. et al. GORDIAN: VLSI placement by quadratic programming and slicing optimization //IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1991. - Т. 10, №. 3. -С. 356-365. DOI: 10.1109/43.67789.

31.Obermeier B., Ranke H., Johannes F.M. Kraftwerk: a versatile placement approach // Proceedings of the 2005 international symposium on Physical

design. - 2005. - C. 242-244. DOI: https://doi.org/10.1145/1055137.1055190.

32.Kahng A.B., Reda S., Wang Q. Aplace: A general analytic placement framework // Proceedings of the 2005 international symposium on Physical design. - 2005. - C. 233-235. DOI: https://doi.org/10.1145/1055137.1055187.

33.Chan T.F. et al. An enhanced multilevel algorithm for circuit placement // ICCAD-2003. International Conference on Computer Aided Design (IEEE Cat. No. 03CH37486). - 2003. - C. 299-306. DOI: 10.1109/ICCAD.2003.159704.

34.Jingwei Lu, Pengwen Chen, Chin-Chih Chang, Lu Sha et al. ePlace: Electrostatics Based Placement Using Nesterov's Method // 51st ACM/EDAC/IEEE Design Automation Conference (DAC). - 2014. - C. 1-6. DOI: 10.1145/2593069.2593133.

35.Chung-Kuan Cheng, Andrew B. Kahng, Ilgweon Kang, Lutong Wang RePlAce: Advancing Solution Quality and Routability Validation in Global Placement // IEEE transactions on computer-aided design of integrated circuits and systems. - 2019. - T. 38, № 9. - C. 1717-1730. DOI: 10.1109/TCAD.2018.2859220.

36.Chen T.C., Hsu T.C., Jiang Z.W., Chang Y.W. NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs // Proceedings of the 2005 international symposium on Physical design. -2005. - C. 236-238. DOI: https://doi.org/10.1145/1055137.1055188.

37.Chen T.C., Jiang Z.W., Hsu T.C.et al. NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2008. - T. 27. - №. 7. - C. 1228-1240. DOI: 10.1109/TCAD.2008.923063.

38.Lin Y., Dhar S., Li W., Ren H., Khailany B., Pan D.Z. DREAMPIace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI

Placement // 56th ACM/IEEE Design Automation Conference (DAC). -2019. - С. 1-6.

39.Авдонин Б. Н., Макушин М. В., Мартынов В. В., Орлов О. М., Стяжкин А. Н., Фомина А. В. Перспективные направления дальнейшего развития отечественной микроэлектроники с учетом зарубежного опыта // Радиопромышленность. - 2016. - № 3. - С. 131— 142. DOI: 10.21778/2413-9599-2016-3-131-142.

40.Макушин М., Мартынов В. Современные тенденции развития микроэлектроники. Часть 1 // Электроника: наука, технология, бизнес. - 2018. - №8 (179). - С. 150-158. DOI: 10.22184/19924178.2018.179.8.150.158.

41.Абасов, Р. К., Силла А. Анализ методов искусственного интеллекта САПР технологических процессов производства электронной аппаратуры // Молодой ученый. - 2016. - № 24 (128). - С. 41-48. URL: https://moluch.ru/archive/128/35423/ (дата обращения: 02.11.2022).

42. Познер М. «Переплетение» трендов создает фантастические возможности для микроэлектроники // Электроника: наука, технология, бизнес. - 2018. - №10 (181). - С. 12-16. DOI: 10.22184/1992-4178.2018.181.10.12.16.

43.Mirhoseini A. et al. Device placement optimization with reinforcement learning // International Conference on Machine Learning, PMLR. - 2017. - С. 2430-2439. DOI: https://doi.org/10.48550/arXiv.1706.04972.

44.Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori et al. Chip Placement with Deep Reinforcement Learning //arXiv preprint arXiv:2004.10746. - 2020. DOI: https://doi.org/10.48550/arXiv.2004.10746.

45.Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori et al. A graph placement methodology for fast chip design // Nature. - 2021. - № 594. - C. 207-212. DOI: https://doi.org/10.1038/s41586-021-03 544-w.

46. Иванова Е. Synopsys: тренды, решения, мифы // Электроника: наука, технология, бизнес. - 2019. - №7 (188). - С. 16-21. DOI: 10.22184/1992-4178.2019.188.7.16.20.

47.Shahookar K., Mazumder P. VLSI cell placement techniques // ACM Computing Surveys (CSUR). - 1991. - Т. 23, № 2. - С. 143-220. DOI: https://doi.org/10.1145/103724.103725.

48.Ibrahim (Abe) M. Elfadel, Duane S. Boning Xin Li Machine Learning in VLSI Computer Aided Design. Springer Nature Switzerland AG, 2019. 716 c. DOI: 10.1007/978-3-030-04666-8.

49.Bansal, M., Priya Machine Learning Perspective in VLSI Computer-Aided Design at Different Abstraction Levels // Shakya, S., Bestak, R., Palanisamy, R., Kamel, K.A. (eds) Mobile Computing and Sustainable Informatics. Lecture Notes on Data Engineering and Communications Technologies. Springer, Singapore. - 2022. - Т. 68. DOI: https://doi.org/10.1007/978-981-16-1866-6_6.

50.Fu-Chieh Chang, Yu-Wei Tseng, Ya-Wen Yu, Ssu-Rui Lee et al. Flexible Multiple-Objective Reinforcement Learning for Chip Placement // Proceedings of the 59th ACM/IEEE Design Automation Conference. -2022. - C. 1392-1393. DOI: https://doi.org/10.1145/3489517.3530617.

51.Sutton Richard S., Barto Andrew G. Reinforcement Learning, Second Edition. An Introduction. The MIT Press, 2018. 552 с. ISBN: 9780262039246.

52.Li A.C., Pinto L., Abbeel P. Generalized Hindsight for Reinforcement Learning // Advances in Neural Information Processing Systems 33 (NPS 2020). - Neural Information Processing Systems Foundation, Inc. (NeurIPS), 2020. - P. 7754-7767.

53.Maogang Wang, Xiaojian Yang, Majid Sawafzadeh DRAGON2000: standard-cell placement tool for large industry circuits // IEEE/ACM International Conference on Computer Aided Design. ICCAD - 2000.

IEEE/ACM Digest of Technical Papers (Cat. No.00CH37140). - 2000. -C. 260-263. DOI: 10.1109/ICCAD.2000.896483.

54.Wong D.F., Leong H.W., Liu C.L. Simulated Annealing for VLSI Design. Springer, 1988. 214 c. ISBN-13: 978-0898382563.

55.Sechen C., Sangiovanni-Vincentelli A. The TimberWolf placement and routing package // IEEE Journal of Solid-State Circuits. - 1985. - T. 20, № 2. - C. 510-522. DOI: 10.1109/JSSC.1985.1052337.

56.Sechen C., Sangiovanni-Vincentelli A. The TimberWolf placement and routing package // IEEE Journal of Solid-State Circuits. - 1985. - T. 20, № 2. - C. 510-522. DOI: 10.1109/JSSC.1985.1052337.

57.Sarrafzadeh M., Wang M., Yang X. Dragon: A Placement Framework // Modern Placement Techniques. - Springer, Boston, MA, 2003. - C. 5789. DOI: 10.1007/978-1-4757-3781-3_3.

58.Adya S. N. et al. Benchmarking for large-scale placement and beyond // Proceedings of the 2003 international symposium on Physical design. -2003. - C. 95-103. DOI: https://doi.org/10.1145/640000.640022.

59.Agnihotri A.R., Ono S., Madden P.H. Recursive bisection placement: Feng Shui 5.0 implementation details // Proceedings of the 2005 international symposium on Physical design. - 2005. - C. 230-232. DOI: https://doi.org/10.1145/1055137.1055186.

60.Roy J.A., Papa D.A., Adya S.N. et al. Capo: robust and scalable open-source min-cut floorplacer // Proceedings of the 2005 international symposium on Physical design. - 2005. - C. 224-226. DOI: https://doi.org/10.1145/1055137.1055184.

61.Roy J.A., Papa D.A., Markov I.L. Capo: Congestion-driven placement for standard-cell and rtl netlists with incremental capability // Modern Circuit Placement. - Springer, Boston, MA, 2007. - C. 97-133.

62.Agnihotri A. et al. Fractional cut: Improved recursive bisection placement //ICCAD-2003. IEEE International Conference on Computer Aided

Design (IEEE Cat. No. 03CH37486). - 2003. - C. 307-310. DOI: 10.1109/ICCAD.2003.1257685.

63.Liu D. et al. Global density smoothing technique for analytical placement algorithm //2009 11th IEEE International Conference on Computer-Aided Design and Computer Graphics. - 2009. - C. 389-393. DOI: 10.1109/CADCG.2009.5246870.

64.Luo T., Pan D.Z. DPlace: Anchor Cell-Based Quadratic Placement with Linear Objective //Modern Circuit Placement. - Springer, Boston, MA, 2007. - C. 39-58.

65.Ray BN. B. et al. An optimized HPWL model for VLSI analytical placement // IEEE, International Conference on Information Technology (ICIT). - 2015. - C. 7-12. DOI: 10.1109/ICIT.2015.32.

66.Ray BN. B. et al. HPWL Formulation for Analytical Placement using Gaussian Error Function // IEEE, International Conference on Information Technology (ICIT). - 2017. - C. 56-61. DOI: 10.1109/ICIT.2017.34.

67.Viswanathan N., Pan M., Chu C. FastPlace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control // 2007 IEEE Asia and South Pacific Design Automation Conference. - 2007. - C. 135-140. DOI: 10.1109/ASPDAC.2007.357975.

68.Lin Y. et al. Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement // Proceedings of the 56th Annual Design Automation Conference 2019. - 2019. - C. 1-6. DOI: https://doi.org/10.1145/3316781.3317803.

69.Gu J. et al. DreamPlace 3.0: Multi-electrostatics based robust VLSI placement with region constraints //2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD). - 2020. - C. 1-9.

70.Liao P. et al. DREAMPlace 4.0: timing-driven global placement with momentum-based net weighting //2022 Design, Automation & Test in Europe Conference & Exhibition (DATE). - IEEE, 2022. - C. 939-944.

71.Hamilton W. Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Springer Nature, vol. 14( 3), 2020, C. 1-141. DOI: 10.1007/978-3-031-01588-5.

72.Yao Ma, Jiliang Tang. Deep learning on Graphs. Cambridge University press, 2021. 339 c. ISBN: 978-1-108-83174-1.

73.Гагарина Л.Г., Гайдук И.О., Кремер Е.А., Можжухина А.В. Эффективный метод локализации ошибок при проектировании специализированных БИС. Изв. вузов. Электроника. - 2019. - Т. 24. - № 5.

74. Денисов А.Н., Фомин Ю.П., Коняхин В.В., Федоров Р.А. Библиотека функциональных ячеек для проектирования полузаказных микросхем серий 5503 и 5507. М.: Техносфера, 2012. 304 с. ISBN: 978-5-94836-332-5.

75.Puterman M.L. Markov decision processes // Handbooks in operations research and management science. - 1990. - Т. 2. - С. 331-434. DOI: https://doi.org/10.1016/S0927-0507(05)80172-0.

76.Papadimitriou C. H., Tsitsiklis J. N. The complexity of Markov decision processes //Mathematics of operations research. - 1987. - Т. 12, №. 3. -С. 441-450. DOI: https://doi.org/10.1287/moor.12.3.441.

77.Лапань M. Глубокое обучение с подкреплением. AlphaGo и другие технологии. СПб.: Питер, 2020. 496 с. ISBN: 978-5-4461-1079-7.

78.Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter C. Ma et al. GDP: Generalized device placement for dataflow graphs // arXiv preprint arXiv:1910.01578. - 2019. DOI: https://doi.org/10.48550/arXiv.1910.01578.

79.Heess N., TB D., Sriram, S., Lemmon, J. et al. Emergence of locomotion behaviours in rich environments // arXiv preprint arXiv:1707.02286. -2017. DOI: https://doi.org/10.48550/arXiv.1707.02286.

80.Hausknecht M., Stone P. Deep reinforcement learning in parameterized action space // 4th International Conference on Learning Representations, ICLR. - 2016. DOI: https://doi.org/10.48550/arXiv.1511.04143.

81.Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P. High-dimensional continuous control using generalized advantage estimation // 4th International Conference on Learning Representations, ICLR. - 2016. DOI: https://doi.org/10.48550/arXiv.1506.02438.

82.Lillicrap, T. P., Hunt, J. J., Pritzel, A. et al. Continuous control with deep reinforcement learning // 4th International Conference on Learning Representations, ICLR. - 2016. DOI: https://doi.org/10.48550/arXiv.1509.02971.

83.Riedmiller, M. Neural Fitted Q Iteration - First Experiences with a Data Efficient Neural Reinforcement Learning Method // Machine Learning: ECML 2005. ECML 2005. Lecture Notes in Computer Science, vol 3720. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564096_32.

84.Williams, R.J. Simple statistical gradient-following algorithms for connectionist reinforcement learning // Mach Learn. - 1992. - № 8. - C. 229-256. DOI: https://doi.org/10.1007/BF00992696.

85.Shani, L., Efroni, Y., & Mannor, S. Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs // Proceedings of the AAAI Conference on Artificial Intelligence. -2020. - № 34(04). - C. 5668-5675. DOI: https://doi.org/10.1609/aaai.v34i04.6021.

86.Mnih V. et al. Asynchronous Methods for Deep Reinforcement Learning // Proceedings of the 33rd International Conference on International Conference on Machine Learning, JMLR.org. - 2016. - № 48. - C. 19281937. DOI: https://doi.org/10.48550/arXiv.1602.01783.

87.Barto A.G., Sutton R.S., Anderson C.W. Looking Back on the Actor-Critic Architecture // IEEE Transactions on Systems, Man, and

Cybernetics: Systems. - 2021. - Т. 51, № 1. - С. 40-50. DOI: 10.1109/TSMC.2020.3041775.

88.Хабр [Электронный ресурс]: Интуитивный RL (Reinforcement Learning): введение в Advantage-Actor-Critic (A2C). URL: https://habr.com/ru/articles/442522/ (дата обращения: 10.02.2025).

89.Dankwa S., Zheng, W. Twin-Delayed DDPG: A Deep Reinforcement Learning Technique to Model a Continuous Movement of an Intelligent Robot Agent // ICVISP 2019: 3rd International Conference on Vision, Image and Signal Processing, 2019. - C. 1-5. DOI: 10.1145/3387168.3387199.

90.Sewak M. Deep Q Network (DQN), Double DQN, and Dueling DQN: A Step Towards General Artificial Intelligence // Deep Reinforcement Learning. Springer, 2019. - C. 95-108.

91.Ye Jian, Guo Huanyu, Zhao Di et al. TD3 Algorithm Based Reinforcement Learning Control for Multiple-Input Multiple-Output DC-DC Converters. IEEE Transactions on Power Electronics, 2024. - C. 1-13. DOI: 10.1109/TPEL.2024.3416911.

92.Xu, Y., Hu, D., Liang, L. et al. Target Entropy Annealing for Discrete Soft Actor-Critic // arXiv preprint arXiv:2112.02852. - 2021. DOI: https://doi.org/10.48550/arXiv.2112.02852.

93.Banerjee C., Chen Z., Noman N. Improved Soft Actor-Critic: Mixing Prioritized Off-Policy Samples With On-Policy Experiences // IEEE Transactions on Neural Networks and Learning Systems. - 2022. - C. 19. DOI: 10.1109/TNNLS.2022.3174051.

94.Wijmans E. et al. DD-PPO: Learning Near-Perfect PointGoal Navigators from 2.5 Billion Frames // International Conference on Learning Representations, Conference Blind Submission. - 2020. C. 1-17. URL: https://openreview.net/forum?id=H1gX8C4YPr (дата обращения: 02.11.2022).

95.Birck M., Ballester P., Andersson V., Araujo R. Multi-Task reinforcement learning: An hybrid A3C domain approach // ENIAC - Encontro Nacional de Inteligencia Artificial e Computacional, 2017. URL: https://www.researchgate.net/publication/320237340_Multi-Task_reinforcement_learning_An_hybrid_A3 C_domain_approach (дата обращения: 10.02.2025).

96.Engstrom L. et al. Implementation matters in deep policy gradients: A case study on PPO and TRPO // arXiv preprint arXiv:2005.12729. - 2020. DOI: https://doi.org/10.48550/arXiv.2005.12729.

97.Schulman J., Wolski F., Dhariwal P., Radford A., Klimov O. Proximal Policy Optimization Algorithms. - arXiv: Learning, 2017. - 12 p. http://export.arxiv.org/pdf/1707.06347.

98.Haarnoja, T., Zhou, A., Abbeel, P., Levine, S. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor // Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research. - 2018. - C. 18611870. URL: https://proceedings.mlr.press/v80/haarnoja18b.html (дата обращения: 02.11.2022).

99.Чачанидзе Е.Р. Сравнительный анализ алгоритмов proximal policy optimization и soft-actor-critic // E-Scio. - 2020. - №5 (44). - C. 226235. URL: https://cyberleninka.ru/article/n7sravnitelnyy-analiz-algoritmov-proximal-policy-optimization-i-soft-actor-critic (дата обращения: 02.11.2022).

100. Schulman J., Wolski F., Dhariwal P., Radford A., Klimov O. Proximal policy optimization algorithms // arXiv preprint arXiv:1707.06347. -2017. DOI: https://doi.org/10.48550/arXiv.1707.06347.

101. wandb.ai The AI developer platform to build AI agents, applications, and models with confidence [Электронный ресурс]: Huang C. SAC vs PPO runtime. URL: https://wandb.ai/cleanrl/cleanrl.benchmark/reports (дата обращения: 10.02.2025).

102. Гайдук И.О., Можжухина А.В. Графовые нейронные сети и методы обучения с подкреплением в задаче размещения элементов БИС // Системы компьютерной математики и их приложения: межвузовский сборник научных трудов. - Смоленск: Изд-во СмолГУ, 2024. - Вып. 25. - С. 89-95.

103. Можжухина А.В. Исследование и разработка архитектуры нейронной сети для алгоритмов reinforcement learning на этапе размещения элементов БИС на кристалле БМК // Материалы международной научно-практической конференции «Актуальные проблемы информатизации в цифровой экономике и научных исследованиях». - М.: МИЭТ, 2021. - 142 с.

104. Гласснер Э. Глубокое обучение без математики. M.: ДМК Пресс, 2020. 610 с. ISBN: 978-5-97060-701-5.

105. Траск Э.В. Грокаем глубокое обучение. СПб.: Питер, 2019. 352 с. ISBN: 978-5-4461-1334-7.

106. Николенко С., Кадурин A., Архангельская E. Глубокое обучение. Погружение в мир нейронных сетей. СПб.: Питер, 2018. 480 с. ISBN: 978-5-496-02536-2.

107. Можжухина А.В. Исследование и разработка адаптированного алгоритма глубокого обучения с подкреплением для моделирования организационно-технологических систем // Материалы XXX Всероссийской межвузовской научно-техническая конференции студентов и аспирантов «Микроэлектроника и информатика - 2023». - М.: МИЭТ, 2023. - С. 89-95.

108. Mozhzhukhina A.V. LSI element placement method based on deep reinforcement learning. // International Journal of Professional Science. -2022. - № 2. - С. 30-35. DOI 10.54092/25421085_2022_2_31.

109. Kattenborn T. et al. Review on Convolutional Neural Networks (CNN) in vegetation remote sensing //ISPRS Journal of Photogrammetry and

Remote Sensing. - 2021. - Т. 173. - С. 24-49. DOI: https://doi.Org/10.1016/j.isprsjprs.2020.12.010.

110. Sherstinsky A. Fundamentals of recurrent neural network (RNN) and long short-term memory (LSTM) network // Physica D: Nonlinear Phenomena. - 2020. - Т. 404. - С. 132-306. DOI: https://doi.org/10.1016/j.physd.2019.132306.

111. Jin W. et al. Graph structure learning for robust graph neural networks // Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. - 2020. - С. 66-74. DOI: https://doi.org/10.1145/3394486.3403049.

112. Scarselli F., Gori M., Tsoi A.C., Hagenbuchner M.G., Monfardini The Graph Neural Network Model // IEEE Transactions on Neural Networks. - 2009. - Т. 20, №. 1. - С. 61-80. DOI: 10.1109/TNN.2008.2005605.

113. Zhang Y. et al. On the learnability of fully-connected neural networks // Artificial Intelligence and Statistics. - PMLR, 2017. - С. 83-91.

114. Asiri Wijesinghe, Qing Wang A New Perspective on «How Graph Neural Networks Go Beyond Weisfeiler-Lehman?» // The Tenth International Conference on Learning Representations. - 2022. URL: https://openreview.net/forum?id=uxgg9o7bI\_3 (дата обращения: 02.11.2022).

115. Wu Z., Pan S., Chen F., Long G., Zhang C., Yu P. S. A Comprehensive Survey on Graph Neural Networks // IEEE Transactions on Neural Networks and Learning Systems. - 2021. - Т. 32, № 1. - C. 4-24. DOI: 10.1109/TNNLS.2020.2978386.

116. Morris C., Ritzert M., Fey M. et al. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks // Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI

Press. - 2019. - Статья № 565. - С. 4602-4609. DOI: https://doi.org/10.1609/aaai.v33i01.33014602.

117. Mozhzhukhina A. Improving the characteristics of organizational and technological systems at the modeling stage through the use of machine learning // International Conference on Advances in Environment Research, March 25th, 2023, Spain, Madrid. SPO "Professional science", Lulu Inc., 2023, 112 p. - С. 106-110.

118. Schaul, T., Quan, J., Antonoglou, I., Silver, D. Prioritized experience replay // 4th International Conference on Learning Representations, ICLR. - 2016. DOI: https://doi.org/10.48550/arXiv.1511.05952.

119. Можжухина А.В. Исследование и разработка архитектуры нейронной сети для алгоритмов обучения с подкреплением для поиска оптимальной стратегии поведения на этапе размещения элементов БИС на кристалле БМК // Инжиниринг предприятий и управление знаниями (ИП&УЗ-2021). Сборник научных трудов XXIII Международной научной конференции. - М.: ФГБОУ ВО «РЭУ им. Г. В. Плеханова», 2021. - 342 с.

120. Можжухина А.В. Особенности разработки методики автоматизации размещения ИМЭ с использованием графовой структуры / А.В. Можжухина, Л.Г. Гагарина // Международный научно-исследовательский журнал. - 2023. - №1 (127). - URL: https: //research-j ournal .org/archive/1-127-2023-january/10.23670/IRJ.2023.127.1 (дата обращения: 24.01.2023). - DOI: 10.23670/IRJ.2023.127.1.

121. ГОСТ 19.701-90 Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

122. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. М.: Финансы и статистика, 2009. 482 с.

123. Гаврилов С.В., Гайдук И.О., Можжухина А.В. Использование алгоритмов кластеризации для запуска интеллектуальных алгоритмов размещения элементов БИС на ПК // Аспирант и соискатель. - 2025. - № 4. - С. 11-23.

124. Schlag S. High-Quality Hypergraph Partitioning. Dissertation. -Karlsruher Institut für Technologie (KIT), 2020. - 283 c. DOI: 10.5445/IR/1000105953.

125. Luxburg U. A Tutorial on Spectral Clustering // Statistics and Computing, 2004. - C. 395-416. DOI: 10.1007/s11222-007-9033-z.

126. Zhang J., Fei J., Song X., Feng J. An Improved Louvain Algorithm for Community Detection // Mathematical Problems in Engineering, 2021. -C. 1-14. DOI: 10.1155/2021/1485592.

127. Ugli S.I.R., Park DS., Kim, D., Yang, Y., Peng, S., Siet, S. Movie Recommendation System Using Community Detection Based on the Girvan-Newman Algorithm. Advances in Computer Science and Ubiquitous Computing, Springer, 2022. Lecture Notes in Electrical Engineering, vol 1028. - C. 1-13. DOI: 10.1109/TPEL.2024.3416911.

128. Cordasco G., Gargano L. Label propagation algorithm: A semi-synchronous approach // International Journal of Social Network Mining, 2012. - C. 3-26. DOI: 10.1504/IJSNM.2012.045103.

129. Hairol A., Siti H., Abas Z., et al. Identifying Communities with Modularity Metric Using Louvain and Leiden Algorithms // Pertanika Journal of Science and Technology, 2024. - vol. 32, issue 3. DOI: 10.47836/pjst.32.3.16.

130. Tsitsulin A., Palowitch J., Perozzi B., Müller E. Graph Clustering with Graph Neural Networks. - arXiv: Learning, 2020. - 21 p. DOI: 10.48550/arXiv.2006.16904.

131. Idwan S., Etaiwi W. omputing breadth first search in large graph using hMetis partitioning // European Journal of Scientific Research, 2009. -vol.29. - C. 145-216. DOI: 10.1109/TPEL.2024.3416911.

132. github.com [Электронный ресурс]: KaHyPar (Karlsruhe Hypergraph Partitioning) repository. URL: https://github.com/kahypar/kahypar (дата обращения: 10.02.2025).

133. Karypis G., Kumar V. METIS—A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes and Computing Fill-Reducing Ordering of Sparse Matrices. Version 4.0. University of Minnesota, Department of Computer Science / Army HPC Research Center Minneapolis, 1997. - 44 c.

134. Andre R., Schlag S., Schulz C. Memetic multilevel hypergraph partitioning. -GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference, 2018. - C. 347-354.

135. Можжухина А.В. Исследование и разработка среды для тренировки агента глубокого обучения с подкреплением при проектировании организационно-технологических систем // Аспирант и соискатель. - 2023. - № 2. - С. 24-29.

136. Документация для Gym [Электронный ресурс]: Gym Documentation (A2C). URL: https://www.gymlibrary.dev (дата обращения: 10.02.2025).

137. Liang X. et al. PTR-PPO: Proximal Policy Optimization with Prioritized Trajectory Replay //arXiv preprint arXiv:2112.03798. - 2021. DOI: https://doi.org/10.48550/arXiv.2112.03798.

138. Platt E.L. Network Science with Python and NetworkX Quick Start Guide: Explore and Visualize Network Data Effectively. - Packt Publishing Ltd, 2019. 190 с. ISBN: 978-1-78995-531-6.

139. Imambi S., Prakash K.B., Kanagachidambaresan G.R. PyTorch // Programming with TensorFlow. - Springer, Cham, 2021. - С. 87-104. DOI: https://doi.org/10.1007/978-3-030-57077-4_10.

140. Paszke A. et al. Pytorch: An imperative style, high-performance deep learning library // Advances in neural information processing systems. -2019. - Т. 32. DOI: https://doi.org/10.48550/arXiv.1912.01703.

141. Можжухина А.В. Повышение эффективности размещения элементов БИС на основе алгоритмов машинного обучения // Исследования молодых ученых: материалы XXXIII Междунар. науч. конф. (г. Казань, февраль 2022 г.). - Казань: Молодой ученый, 2022. - С. 9-15.

142. Fedus W. et al. Revisiting fundamentals of experience replay // International Conference on Machine Learning. - PMLR, 2020. - С. 3061-3071. DOI: https://doi.org/10.48550/arXiv.2007.06700.

143. Гайдук И.О., Можжухина А.В. Размещение элементов БИС на БСК с использованием глубокого обучения с подкреплением // Информатизация и связь. - 2025. - № 1. - С. 129-133.

АКТЫ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

УТВЕРЖДАЮ

Директор НИК «Технологический центр»,

АКТ ВНЕДРЕНИЯ

результатов диссертации Можжухиной A.B. «Методика и алгоритмы размещения библиотечных элементов с применением машинного обучения для автоматизации проектирования микросхем на базовых структурированных кристаллах», представленной на соискание ученой степени кандидата технических наук по специальности 2.3.7 Компьютерное моделирование и автоматизация проектирования (технические науки).

Настоящим актом подтверждается, что результаты диссертации Можжухиной A.B. использовались в НПК «Технологический центр» в составе исследовательских мероприятий при выполнении ОКР «Разработка и освоение в производстве комплекта доверенных микросхем и микромодулей специального назначения, а также средств обеспечения доверенности процесса их проектирования и изготовления», шифр «Доверие» (идентификационный код закупки № 201770559633977030100101600017219000), дата подписания 28.12.2020. Разработанные методика и алгоритмы были программно реализованы и использованы при разработке средств автоматизированного проектирования БИС на основе базовых структурированных кристаллов. В исследования было получено свидетельство об официальной регистрации в Роспатент прог раммы для ЭВМ №2024691898 от 24.12.2024 «Программный модуль глобального размещения элементов БИС с использованием машинного обучения» (авторы: Гаврилов C.B.. Алешина В.И.. Фролов С.Н., Гайдук И.О., Немченко Д.И., Можжухина A.B.).

Главный конструктор ИМС

НПК «Технологический центр», к.т.н.

И.о. заместителя директора по науке НПК «Технологический центр», к.т.н.

УТВЕРЖДАЮ

i ]роректор МИ 'Л по учебной работе кандидат технических наук, доцент

А.Г. Балашов

А.Г. БаяапЮВ

« » _2025 г.

2025 г.

ЛК1

внедрения результатов диссертационной работы Можжухииой Л.В. на тему «Методика и алгоритмы размещения библиотечных элементов с применением машинного обучения для автоматизации проектирования микросхем на базовых структурированных кристаллах», представленной на соискание ученой степени кандидата технических наук го специальности 2.3,7. - Компьютерное моделирование и автоматизация проектирования (технические науки),

Результаты кандидатской диссертации Можжухивой A.B., посвященной разработке методики и алгоритмов поиска аппроксимирован ной стратегии размещения библиотечных элементов с применением машинного обучения ятя автоматизации проектирования БИС на БСК, а именно:

* методика поиска аппроксимированной оптимальной страте гни размещения библиотечных элементов на БСК е использованием обучения с подкреплением;

* алгоритм конвертирования характеристик проекта БИС и граничных критериев, переводящий Информацию о микросхеме и БСК в модель окружающей среды и графовую структуру;

• алгоритм оценки полученного размещения на основе граничных критериев;

• модифицированный алгоритм кластеризации ]"рафа БИС из плоских и иерархических списков соединений для параллельного размещения элементов.

Иепользуются в учебном процессе Института системной и программной инженерии и информационных технологий (СПИНТех) Национального исследовательского университета «.МЮТ» в лекционных и лабораторных занятиях по дисциплинам: «Большие данные». «Основы обучения с подкреплением», «Основы глубокого обучения е г откреплением».

Директор СПИНТех.

доктор технических наук, профессор

Ученый секретарь СПИНТех, кандидат технических наук, доцент

BJÖ Слюсарь

СВИДЕТЕЛЬСТВА ОБ ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ

РОССИЙСКАЯ ФЕДЕРАЦИЯ

RU

2024691898

ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ

(12) ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства):

Дата регистрации: 24.12.2024

Номер и дата поступления заявки: 2024689309 04.12.2024

Дата публикации и номер бюллетеня: 24.12.2024 Бюл. № 1

Авторы:

Гавр плов Сергей Владимирович (КС1), Алешина Валентина Ивановна (КС), Гайдук Игорь Олегович (КС), Можжухпна Арнна Валерьевна (КС), Немченко Дмитрий Игоревич (КС), Фролов Сергей Николаевич (КС)

Правоо бладате ль: федеральное государственное бюджетное научное учрежд е н пе «Научно -п р оп зв од ств е нн ый комплекс «Технологический пентр» (КС)

Название программы для ЭВМ:

Программный модуль глобального размещения элементов БИС с использованием машпнного обучения

Реферат:

Программа предназначена для повышения качества размещения элементов БИС в процессе топологического проектирования на основе методики и алгоритме® поиска аппроксимированной оптимальной стратегии размещения с применением машинного обучения. Тип ЭВМ: IBM PC; ОС: Windows, Linux, Manjaro.

Язык программирования: Python

Объем программы для ЭВМ: 249 КБ

российская федерация

ни 2025612030

V.

V1

v

ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ

(12) ГООДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства)::

Авторы:

Га в рил о в Сергей Влининросич (ИЦ), Алешина Валентина Ивановна (КГ). Фролов Сергей Николаевич (ВЦ), Карташев Алексей Юрьевич (БЕ), Астахов Алекс андр Владимирович (ЕЛТ), Немченко Дмитрии Игоревич (ВЦ), Никифоров Мстислав Алексеевич (БЕ). Мохсткина Арина Валерьевна (ЯЦ), Гайдук Игорь Олегович (НЕ)

2025612080

Дата регистрации: 27.01.2025

Номер и дата поступления заявки

2024Ш007 27.12.2024

Дата пуоликации и номер бюллетеня:

Д7ЖД025 Бюл. № 2

Правообладатель: федеральное государственное о кисетное научное учр ежд енне «Науч н о-производстве н н ый комплекс «Технологический пентр» (КЕ)

Название программы для ЭВМ:

Система автоматизированного проектирования полузаказных микросхем «Ковчег 4.1»

Программа предназначена для автоматизированного проектирования цифровых БИС на основе базовых матричных кристаллов (БМК) серии 5529. Программа обеспечивает маршрут разработки микросхемы от поведенческого описания схемы на языке УегЛоа до формирования файла с топологией микросхемы в формате ОБЗ. В состав программы вжодят следующие подсистемы: 1. Настройка маршрута на характеристики конкретного типа БМК.

1. Текстовый ввод иди импорт поведение сыгго описания схемы. 3. Поведенческое моделирование схемы. 4. Логический синтез из поведенческого описания в базис ячеек библиотеки 5529. 5. Структурное моделирование схемы, заданной б формате Уеп1о§ или в графическом формате в базисе ячеек библиотеки 5529. 6. Автоматическое создание и редактирование списка пепей синхронизации. 7. Автоматическое и ручное размещение ячеек схемы на поле БМК. £. Трассировка цепей с созданием файла с топологией в формате СЕЭ. 9. Верификация топологии с .экстракцией данных, необходимых для подсистемы расчета задержек. 10. Расчет задержек б топологии. 11. Аттестация проекта путем многократного моделирования с имиталией разброса технологических параметров. 12. Подготовка данных для испытания готовой микросхемы на измерительном оборудовании. Тип ЭВМ: ШМ РС-совмесг ПК; ОС:

Язык программирования: С=. С— Объем программы для ЭВМ: 61.93 МБ

Реферат:

ФРАГМЕНТЫ ПРОГРАММНОГО КОДА РАЗРАБОТАННОГО МОДУЛЯ

1. Среда def get_make_env_fn(**kargs):

def make_env_fn(Size_BIS=2240, BMC_start=960, BMC_end=3200, Num_el=1, Num_el_perif=1, Num_el_feat=9, El_feat_x=np.zeros((1, 9)), Num_region=16, Density_koef=0.7): mdir = tempfile.mkdtemp() env = None

env = BISPlacer(Size_BIS, BMC_start, BMC_end, Num_el, Num_el_perif, Num_el_feat, El_feat_x, Num_region, Density_koef) #gym.make(env_name) return env return make_env_fn, kargs class BISPlacer(Env):

def_init_(self,

Size_BIS: int = 2240, # Размер БИС

BMC_start: int = 960,

BMC_end: int = 3200,

Num_el: int = 1, # Кол-во эл-тов.

Num_el_perif: int = 1, # Кол-во периферии.

Num_el_feat: int = 9,

El_feat_x: np.array = np.zeros((1, 9)), # (Num_el, Num_el_feat), массив эмбеддингов элементов.

Num_region: int = 16, # Кол-во областей Density_koef: float = 0.7 ):

self.Size_BIS = Size_BIS self.BMC_start = BMC_start self.BMC_end = BMC_end self.Num_el = Num_el self.Num_el_feat = Num_el_feat self.Num_el_perif = Num_el_perif self.Num_region = Num_region self.Density_koef = Density_koef # Начальное распределение элементов self.El feat x = El feat x

self.current_step = 0 self.collected_reward = 0 # Начальное состояние. self.state = self. El_feat_x

self.Density_map_vect = np.arange(0, self.BMC_end - self.BMC_start + 1, self.Size_region_diskrets)

self.Density_map = np.full((self.Num_region, self.Num_region), self.Density_koef * self.Size_region_diskrets * self.Size_region_diskrets) self.Num_el_in_region = self._get_all_maps() self.observation_space = Dict({

"Density_map": Box(low=0, high=np.inf, shape=(self.Num_region, self.Num_region), dtype=np.int32),

"state": Box(low=0, high=np.inf, shape=(self.Num_el, self.Num_el_feat), dtype=np.int32) self.action_space = spaces.Tuple([

spaces.Discrete(2), # terminal action or not spaces.Discrete(self.Num_el), # Номер выставляемого элемента spaces.Discrete(self.Num_region), spaces.Discrete(self.Num_region)

])

def step(self, action, after_tracing = None): info = {} # для отладки и логов rw = 0

if action[0] == 0: # расставляем

self._take_action(action) else: # action[0] == 1/ # считаем метрики rw = self._get_reward(after_tracing) self.collected_reward += rw self.current_step += 1 self.render(action, rw)

return self.Density_map, self.state, self.collected_reward, action[0], info

2. PPO class PPO():

def optimize_model(self):

actions, returns, gaes, logpas, values, ep_idxs, ep_t, states_ep_path, density_ep_path = self.episode_buffer.get_stacks()

gaes = (gaes - gaes.mean()) / (gaes.std() + EPS) n_samples = len(actions) res = []

sf = []

for num in range(len(states_ep_path)):

sf.append(open(states_ep_path[num], 'r')) df = []

for num in range(len(density_ep_path)):

df.append(open(density_ep_path[num], 'r')) for _ in range(self.policy_optimization_epochs): # N раз

batch_size = int(self.policy_sample_ratio * n_samples) # размер выборки batch_idxs = np.random.choice(n_samples, batch_size, replace=False) # рандомная выборка без повторов

batch_idxs_split = np.array_split(batch_idxs, 4) # на K куска (на корень из batch_size (размера выборки))

# на 700к элементов будет выборка 560к по ~748 пакетов for split_num in range(4):

idxs = batch_idxs_split[split_num] idxs.sort()

actions_batch = actions[idxs] gaes_batch = gaes[idxs] logpas_batch = logpas[idxs] idx_step = 0 shift = 0

states_batch_file = [] placed_batch_file = [] density_batch_file = []

ep_num = [i for i, x in enumerate(ep_idxs) if x] for i, num in enumerate(ep_num): if idx_step >= idxs.size: break

while (idxs[idx_step] - shift) < ep_t[i]: n = idxs[idx_step] - shift sf[num].seek(0) a = list(islice(sf[num], n, n+1)) states_batch_file.append(*a)

states_batch_file[idx_step] = str(states_batch_file[idx_step][:-2]).split(';') states_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in state s_batch_file[idx_step] ]

df[num].seek(0)

a = list(islice(df[num], n, n+1))

density_batch_file.append(*a)

density_batch_file[idx_step] = str(density_batch_file[idx_step][:-2]).split(';') density_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in density_batch_file[idx_step]]

idx_step = idx_step + 1 if idx_step >= len(idxs): break shift = shift + ep_t[i] states_batch_file = np.array(states_batch_file) placed_batch_file = np.array(placed_batch_file) density_batch_file = np.array(density_batch_file)

logpas_pred, entropies_pred = self.policy_model.get_predictions(states_batch_file, actions_batch, edge_index, BMC, density_batch_file) ratios = (logpas_pred - logpas_batch).exp() pi_obj = gaes_batch * ratios

pi_obj_clipped = gaes_batch * ratios.clamp(1.0 - self.policy_clip_range,

1.0 + self.policy_clip_range) # policy_clip_range

задается в начале

policy_loss = -torch.min(pi_obj, pi_obj_clipped).mean()# losses have negative sign for maximizing via backprop

entropy_loss = -entropies_pred.mean() * self.entropy_loss_weight # высчитываем энтропию (среднее по массиву) и взвешиваем

self.policy_optimizer.zero_grad() # Sets the gradients of all optimized torch.Tensor s

to zero.

# потому что PyTorch накапливает градиенты при последующих обратных проходах. Такое накопительное поведение удобно при обучении RNN, но не везде и всегда это нужно.

(policy_loss + entropy_loss).backward()

# clip_grad_norm_ is used to mitigate the problem of exploding gradients torch.nn.utils.clip_grad_norm_(self.policy_model.parameters(), # Clips gradient norm

of an iterable of parameters.

self.policy_model_max_grad_norm) # policy_model_max_grad_norm задается в

начале

self.policy_optimizer.step() # updates the parameters with torch.no_grad(): # disable gradient calculation.

batch_idxs = np.random.choice(n_samples, n_samples, replace=False) # рандомная выборка без повторов

batch_idxs.sort()

batch_idxs_split = np.array_split(batch_idxs, 4) logpas_pred_split = [] for split_num in range(4):

idxs = batch_idxs_split[split_num]

idxs.sort()

idx_step = 0

shift = 0

states_batch_file = [] placed_batch_file = [] density_batch_file = []

ep_num = [i for i, x in enumerate(ep_idxs) if x] for i, num in enumerate(ep_num): if idx_step >= idxs.size: break

while (idxs[idx_step] - shift) < ep_t[i]: n = idxs[idx_step] - shift sf[num].seek(0) a = list(islice(sf[num], n, n+1)) states_batch_file.append(*a)

states_batch_file[idx_step] = str(states_batch_file[idx_step][:-2]).split(';')

states_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in state s_batch_file[idx_step]]

df[num].seek(0)

a = list(islice(df[num], n, n+1))

density_batch_file.append(*a)

density_batch_file[idx_step] = str(density_batch_file[idx_step][:-2]).split(';') density_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in density_batch_file[idx_step]]

idx_step = idx_step + 1 if idx_step >= len(idxs): break shift = shift + ep_t[i] states_batch_file = np.array(states_batch_file) placed_batch_file = np.array(placed_batch_file) density_batch_file = np.array(density_batch_file) actions_batch = actions[idxs]

logpas_temp, _ = self.policy_model.get_predictions(states_batch_file, actions_batch, edge_index, BMC, density_batch_file)

logpas_pred_split.append(logpas_temp.cpu().numpy()) logpas_pred_split = np.hstack([logpas_pred_split[0], logpas_pred_split[1], logpas_pred_split[2], logpas_pred_split[3]]) logpas_batch = logpas[batch_idxs]

kl = (logpas_batch.cpu().numpy() - logpas_pred_split).mean() if kl.item() > self.policy_stopping_kl: break

for _ in range(self.value_optimization_epochs): # N раз batch_size = int(self.value_sample_ratio * n_samples)

batch_idxs = np.random.choice(n_samples, batch_size, replace=False) # рандомная выборка без повторов

batch_idxs_split = np.array_split(batch_idxs, 4) for split_num in range(4):

idxs = batch_idxs_split[split_num] idxs.sort()

returns_batch = returns[idxs] # sum(rewards(oT t до T)*discounts(oT 0 до T+1-t)) => [np.sum(ep_discounts[:T+1-t] * ep_rewards[t:]) for t in range(T)]) values_batch = values[idxs] idx_step = 0 shift = 0

states_batch_file = [] actions_batch = actions[idxs] currents_batch = actions_batch[:, 0] ep_num = [i for i, x in enumerate(ep_idxs) if x] for i, num in enumerate(ep_num): if idx_step >= idxs.size: break

while (idxs[idx_step] - shift) < ep_t[i]: n = idxs[idx_step] - shift sf[num].seek(0) a = list(islice(sf[num], n, n+1)) states_batch_file.append(*a)

states_batch_file[idx_step] = str(states_batch_file[idx_step][:-2]).split(';') states_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in state s_batch_file[idx_step] ]

idx_step = idx_step + 1 if idx_step >= len(idxs): break shift = shift + ep_t[i] states_batch_file = np.array(states_batch_file)

values_pred = self.value_model(states_batch_file, edge_index, BMC, currents_batch) values_pred_clipped = values_batch + (values_pred - values_batch).clamp(-self.value_clip_range,

self.value_clip_range) # value_clip_range задается в начале v_loss = (returns_batch - values_pred).pow(2) v_loss_clipped = (returns_batch - values_pred_clipped).pow(2) value_loss = torch.max(v_loss, v_loss_clipped).mul(0.5).mean() self.value_optimizer.zero_grad() value_loss.backward()

torch.nn.utils.clip_grad_norm_(self.value_model.parameters(), # Clips gradient norm of an iterable of parameters.

self.value_model_max_grad_norm) # value_model_max_grad_norm задается тоже в начале: float('inf) self.value_optimizer.step() with torch.no_grad():

batch_idxs = np.random.choice(n_samples, n_samples, replace=False) # рандомная выборка без повторов

batch_idxs.sort()

batch_idxs_split = np.array_split(batch_idxs, 4) values_pred_split = [] values_pred_split_temp = [] for split_num in range(4):

idxs = batch_idxs_split[split_num]

idxs.sort()

idx_step = 0

shift = 0

states_batch_file = [] actions_batch = actions[idxs] currents_batch = actions_batch[:, 0] ep_num = [i for i, x in enumerate(ep_idxs) if x] for i, num in enumerate(ep_num): if idx_step >= idxs.size: break

while (idxs[idx_step] - shift) < ep_t[i]: n = idxs[idx_step] - shift sf[num].seek(0) a = list(islice(sf[num], n, n+1)) states_batch_file.append(*a)

states_batch_file[idx_step] = str(states_batch_file[idx_step][:-2]).split(';') states_batch_file[idx_step] = [list(map(np.int32, i.split(','))) for i in state s_batch_file[idx_step] ]

idx_step = idx_step + 1 if idx_step >= len(idxs):

break shift = shift + ep_t[i] states_batch_file = np.array(states_batch_file)

values_temp = self.value_model(states_batch_file, edge_index, BMC, currents_batch)

values_pred_split.append(values_temp.cpu().numpy()) values_pred_split = np.array(values_pred_split)

values_pred_split = np.hstack([values_pred_split[0], values_pred_split[1], values_pred_split[2], values_pred_split[3]]) values_batch = values[batch_idxs] mse = (values_batch.cpu().numpy() - values_pred_split) mse = np.power(mse, 2) mse = np.multiply(mse, 0.5) mse = mse.mean()

if mse.item() > self.value_stopping_mse: break

3. Входная информация о схеме def read():

global koef_down global dop_koef global tf

#читаем необходимые файлы проекта path = RESULTS_DIR + '/name_low_result.txt' sizes_perif = pd.read_csv(path,

sep=';', names =["Id", "w", "h", "perif", "placed"]) path = RESULTS_DIR + '/name_result.txt' sizes_etc = pd.read_csv(path,

sep=';', names =["Id", "w", "h", "perif", "placed"]) sizes_all = pd.concat([sizes_perif, sizes_etc]) path = RESULTS_DIR + '/OneOne.txt' graph_name = pd.read_csv(path, sep=';') del graph_name['Unnamed: 2'] path = RESULTS_DIR + '/Cells.txt'

embeddings_microns = pd.read_csv(path,

sep=';', names =["Name", "Id", "x", "y", "bis", "un"]) del embeddings_microns['un']

#читаем эмбеддинги элементов и эмбеддинг БМК BMC = embeddings_microns.iloc[[1,2]]

BMC_wh = (np.float(BMC.iloc[[0]]['y']) - np.float(BMC.iloc[[0]]['x']))*dop_koef BMC_start = (np.float(BMC.iloc[[0]]['x']))*dop_koef BMC_end = (np. float(BMC .iloc[[0]]['y']))*dop_koef

i_tracks = embeddings_microns.index[embeddings_microns['Name'] == 'TRACKS'].tolist()[0] i_comp = embeddings_microns.index[embeddings_microns['Name'] == 'C0MP0NENTS'].tolist()[0] tracks_read = embeddings_microns.iloc[(i_tracks+2):i_comp]

tracks_read.rename(columns = {'Name':'coord', 'Id':'from', 'x':'num', 'y':'step', 'bis':'layer'}, inplace = True)

koef = embeddings_microns.iloc[[0,i_comp]] del koef['x'] del koef['y'] del koef['bis']

koef_down = int(koef['Id'][0])

embeddings_el = embeddings_microns.iloc[(i_comp+1):len(embeddings_microns)]

del embeddings_el['bis']

embeddings_el = embeddings_el.reset_index()

del embeddings_el['index']

tf = embeddings_el.merge(sizes_all, how = 'left', left_on='Id', right_on='Id') elParam = tf.copy() del elParam['Name'] del elParam['Id']

elParam = elParam.reset_index() elParam['x'] = elParam['x'].astype(float) elParam['y'] = elParam['y'].astype(float) elParam['w'] = elParam['w'].astype(float) elParam['h'] = elParam['h'].astype(float) elParam['x'] = (elParam['x']*dop_koef)/koef_down elParam['y'] = (elParam['y']*dop_koef)/koef_down

elParam['w'] = elParam['w']*dop_koef elParam['h'] = elParam['h']*dop_koef

elParamloc[(elParam['perif] == 1) & (elParam['x'] == 0), 'y'] = elParam.apply(lambda x: (x['y'] + x['w']/2 - BMC_start)/16, axis=1)

elParam.loc[(elParam['perif] == 1) & (elParam['x'] == 0), 'x'] = -1

elParam.loc[(elParam['perif] == 1) & (elParam['x'] > BMC_end), 'y'] = elParam.apply(lambda y: (y['y'] + y['w']/2 - BMC_start)/16, axis=1)

elParam.loc[(elParam['perif] == 1) & (elParam['x'] > BMC_end), 'x'] = (BMC_wh/8) + 1 elParam.loc[(elParam['perif] == 1) & (elParam['y'] == 0), 'x'] = elParam.apply(lambda x: (x['x'] + x['w']/2 - BMC_start)/8, axis=1)

elParamloc[(elParam['perif] == 1) & (elParam['y'] == 0), 'y'] = -1

elParamloc[(elParam['perif] == 1) & (elParam['y'] > BMC_end), 'x'] = elParam.apply(lambda x: (x['x'] + x['w']/2 - BMC_start)/8, axis=1)

elParam.loc[(elParam['perif] == 1) & (elParam['y'] > BMC_end), 'y'] = (BMC_wh/16) + 1 elParam.loc[(elParam['perif] == 0) & (elParam['placed'] == 1), 'x'] = elParam.apply(lambda x: (x['x'] - BMC_start)/8, axis=1)

elParam.loc[(elParam['perif] == 0) & (elParam['placed'] == 1), 'y'] = elParam.apply(lambda x: (x['y'] - BMC_start)/16, axis=1)

elParam.loc[(elParam['perif] == 0) & (elParam['placed'] == 0), 'x'] = -1 elParam.loc[(elParam['perif] == 0) & (elParam['placed'] == 0), 'y'] = -1 elParam.loc[(elParam['perif] == 0) & (elParam['placed'] == 1), 'placed'] = 0 elParam['w'] = elParam['w']/8 elParam['h'] = elParam['h']/16

elParam.rename(columns = {'index':'i', 'x':'yach_x', 'y':'yach_y'}, inplace = True)

elParam['i'] = elParam['i'].astype(int)

elParam['yach_x'] = elParam['yach_x'].astype(int)

elParam['yach_y'] = elParam['yach_y'].astype(int)

elParam['w'] = elParam['w'].astype(int)

elParam['h'] = elParam['h'].astype(int)

elParam['placed'] = elParam['placed'].astype(bool)

elParam['perif] = elParam['perif].astype(bool)

elParamT = elParam.T.iloc[[0,1,2,3,4,5,6]] # возможно потом еще 6 - perif embed_x = torch.tensor([elParamT[0].tolist()])

for i in range (1, len(elParam)):

y = torch.tensor([elParamT[i].tolist()]) embed_x = torch.cat((embed_x[:], y)) del elParam del elParamT

num_perif = int(torch. sum((embed_x [:,5]==1)))

num_el = embed_x.shape[0] #with perif -> all element

num_el_to_pl ace = int(torch.sum(((embed_x [:,5]==0)&(embed_x [:,6]==0))))

#читаем граф связности элементов

name_id = tf['Name']

name_id = name_id.reset_index()

gr = graph_name.merge(name_id, how = 'left', left_on='from', right_on='Name') del gr['Name']

gr.columns = ["from", "to", "from_int"]

gr = gr.merge(name_id, how = 'left', left_on='to', right_on='Name') del gr['Name']

gr.columns = ["from", "to", "from_int", "to_int"]

a = gr['from_int'].tolist() # Дело в том, что в одном векторе должны быть перечислены вершины, являющиеся началом i-тых ребер,

b = gr['to_int'] .tolist() # а во втором векторе вершины,являющиеся концом i-тых ребер

edge_index = torch.tensor([a,b])

#читаем Circuit для HPWL

path = RESULTS_DIR + '/0neMany.txt'

circuit_name = pd.read_csv(path, sep=r';')

del circuit_name['Unnamed: 2']

#читаем data_scheme для reward

data_reg = pd.read_csv(RESULTS_DIR + '/data_reward.csv', sep=',', names =["name", "el_perif", "el_all", "BMK_perif_all", "density_all", "OneMany", "OneOne", "BMK_mikron", "el_mikron", "HPWL_mikron", "congestion_max26", "congestion_ABU", "type_BMK"]) data_reg = data_reg.drop(labels = [0],axis = 0) data_reg['name'] = data_reg['name'].astype(str) data_reg['el_perif] = data_reg['el_perif].astype(int) data_reg['el_all'] = data_reg['el_all'].astype(int) data_reg['BMK_perif_all'] = data_reg['BMK_perif_all'].astype(int)

data_reg['density_all'] = data_reg['density_all'].astype(float) data_reg['OneMany'] = data_reg['OneMany'].astype(int) data_reg['OneOne'] = data_reg['OneOne'].astype(int) data_reg['BMK_mikron'] = data_reg['BMK_mikron'].astype(float) data_reg['el_mikron'] = data_reg['el_mikron'].astype(float) data_reg['HPWL_mikron'] = data_reg['HPWL_mikron'].astype(float) data_reg['congestion_max26'] = data_reg['congestion_max26'].astype(float) data_reg['congestion_ABU'] = data_reg['congestion_ABU'].astype(float) data_reg['type_BMK'] = data_reg['type_BMK'].astype(int) a = data_reg.index[data_reg['name'] == PROJ_NAME].tolist() X = [data_reg['el_perif][a], data_reg['el_all'][a], data_reg['BMK_perif_all'][a], data_reg['density_all'] [a],

data_reg['OneMany'] [a], data_reg['OneOne'] [a], data_reg['BMK_mikron'] [a], data_reg['el_mikron'] [a], data_reg['HPWL_mikron'] [a], data_reg['congestion_ABU'] [a]] X = np.asarray(X).T

return edge_index, embed_x, BMC_wh, num_perif, num_el, num_el_to_place, BMC_start, BMC_end, circuit_name, X, koef_down, tf, tracks_read, gr