The Specifics of Developing a Methodology for Automating the Placement of Microelectronics Products Using a Graph Structure
The Specifics of Developing a Methodology for Automating the Placement of Microelectronics Products Using a Graph Structure
Abstract
Designing microelectronics products (MEPs) is a complex and time-consuming process. Over time, designers are striving to make them more and more compact, but also faster and more energy-efficient. Thus, the costs associated with production, including time, are increasing. This necessitates automation at every level of design. As a result, it is necessary to improve the individual stages of automated systems, keeping methods and algorithms updated. One of the phases requiring improvements is the product placement phase. This article discusses the formulation of the problem with a rationale for the use of a graph neural network in the training of a deep learning agent with reinforcement. A variant of solving the MEPs placement problem by applying the latest machine learning methods using the developed technique based on deep learning with reinforcement is also presented.
1. Введение
Все больше направлений науки и производства стремятся внедрить достижения сферы искусственного интеллекта в свои процессы. Не стала исключением и сфера электроники, где множество процессов проектирования связаны с автоматизацией , . Методы искусственного интеллекта помогают ускорить анализ данных и принятие решений, повысить точность получаемых решений и пр. Его применение в различных сферах обусловлено необходимостью обработки больших массивов информации и поиска сложных зависимостей в сложноформализуемых задачах. В частности, в настоящее время много исследований проводится по внедрению искусственного интеллекта в процесс проектирования микросхем , , .
Так как техпроцессы производства микросхем уменьшаются, а количество компонентов возрастает, то усложняется и дорожает процесс разработки , . В текущих реалиях стандартные алгоритмы даже при использовании распараллеливания оказываются слишком долгими и неэффективными и кроме того, усложняются устройством самих ИМЭ.
В сфере отечественного производства ИМЭ требуется улучшение средств автоматизации с использованием современных методов и средств. Одной из задач, при решении которой специалисты сталкиваются с рядом проблем при применении классических методов и алгоритмов, является размещение ИМЭ. В процессе размещения необходимо соблюдать определенный набор правил и ограничений, что существенно замедляет производство. В связи с ростом числа правил и входящих в состав изделий и связей между ними, а также сложностью оценки эффективности получаемых размещений, возрастает время проектирования и объем информации на этом шаге. В связи с тем, что размещение напрямую связано с проверкой характеристик перед производством, увеличение скорости будет способствовать уменьшению времени на означенные проверки.
2. Формализованное представление задачи размещения ИМЭ
Для решения задачи необходимо выполнить формализацию. В качестве начального приближения используются следующие множества :
1. E = {e1, e2, …, en …, eN} – множество ИМЭ для размещения;
2. P = {p1, p2, …, pm, …, pM} – фиксированный набор позиций, в которые должны быть размещены изделия из множества E.
В формальном представлении задачи:
где T – время размещения ИМЭ; n - количество элементов; – стратегия размещения; F - функция времени.
Общий процесс сводится к конечному марковскому процессу приятия решений . Среда в этом процессе эпизодическая, детерминированная, стационарная и дискретная с доступом алгоритма размещения (агента) к полной информации среды. Текущие действия агента влияют и на текущую награду Rt+1, и на последующие принимаемые решения. Для решения задачи в этом случаем следует прибегнуть к обучению с подкреплением с целью обучения параметров аппроксимирующей оптимальную стратегию размещения функции :
где – веса аппроксимирующей функции, т.е. глубокой нейронной сети ,
– политика агента, G – граф, представляющий размещение элементов множества E в ячейки множества P, Rp,G – награда, 𝑞𝑝,𝐺 – функция ценности. Использование нейронной сети позволит выявить различные зависимости и схожести между состояниями среды, что даст как минимум не худший вариант решения из всего возможного спектра вариантов размещения.
В связи с тем, что процесс размещения элементов является сложным процессом, влияющим на многие компоненты, связанные между собой, необходимо особым образом представлять входные данные. Для представления элементов ИМЭ и их связей, а также для наиболее корректного и эффективного рассмотрения их связей между собой, был выбран ориентированный взвешенный граф с векторами характеристик вершин . В соответствии с этим в качестве отдельных слоев на входе в архитектуре нейронной сеть необходимо использовать слои графовой нейронной сети – GNN, которая поможет перевести граф микросхемы в вектора связанных характеристик ребер и вершин.
3. Методика размещения ИМЭ на основе обученного агента RL и GNN
На основе требований отечественного технологического процесса и проведенного анализа существующих стандартных методов разработана методика размещения ИМЭ. Ниже приведены основные этапы.
Этап 1: начинается с перебора изделий и записи в список соединений по направлениям от выходов к входам, используя данные ИМЭ. После записи всех соединений для каждого ИМЭ, являющегося вершиной ориентированного графа, создаются вектора характеристик. Также перебирается список ребер, и каждому ребру присваивается соответствующий вес. Таким образом создается графовая структура и параметры окружающей среды.
Этап 2: размещение ИМЭ из созданной очереди. Создание очереди учитывает физические размеры изделий, размещая от большего к меньшему. Если были размещены не все ИМЭ, то размещение начинается заново с генерации очереди. После этого размещение передается другому алгоритму для проведения соединений.
Этап 3: состоит в оценке конечного размещения после выполнения соединений. По результатам выполнения соединения ИМЭ проверяется, хватило ли свободного места между изделиями, рассчитываются задержки и плотность размещения. На основе этих показателей выполняется сравнение с размещениями, сохраненными в базе. Если показатели размещения слишком низкие, может быть осуществлен возврат на этап 2.
Этап 4: размещение добавляется в общую базу для ведения статистики и внесения корректировок. Если обнаружены какие-то отклонения, то по запросу из базы извлекаются данные размещений, снова проходит размещение в режиме обучения (этапы 2 и 3), и на основе этого выполняются корректировки гиперпараметров агента и нейросети.
4. Направления последующего исследования
На основе проведенного анализа было выявлено, что на данный момент технологии обучения с подкреплением не используются в задаче о размещения ИМЭ. В основном используемые решения связаны с алгоритмами, производными от алгоритмов полного перебора возможной расстановки ИМЭ, что занимает достаточно много времени и ресурсов компьютера. Кроме этого, независимо от количества запусков, отсутствует возможность их обучения тупиковым вариантам решений. Использование обучения с подкреплением при решении задач связанных с накоплением, усреднением и использованием прошлого опыта позволяет повысить эффективность и снизить временную ресурсоемкость процесса решения.
Таким образом, основной целью будущих исследований является повышение скорости и качества размещения ИМЭ на основе разработанной методики поиска аппроксимированной оптимальной стратегии размещения с применением методов машинного обучения, в частности, глубокого обучения с подкреплением. В рамках достижения поставленных целей необходимо решить следующие задачи.
1. Разработать реализующие методику алгоритмы формирования размещения ИМЭ для снижения ресурсоемкости этапа.
2. Разработать специальную систему хранения и обработки данных ИМЭ для корректной работы с машинным обучением на основе графовой структуры.
3. Разработать методы и алгоритм для оценивания конечного размещения.
4. Разработать базу данных для сбора, хранения, сортировки и группировки, а также быстрого получения информации о размещениях ИМЭ за все время работы алгоритмов.
5. Выполнить программную реализацию для верификации результатов.
5. Заключение
В настоящее время в микроэлектронике России возросла потребность в импортозамещении, а также улучшении средств автоматизации. В связи с невозможностью использования зарубежных программных средств, а также из-за отсутствия конкурентоспособных отечественных средств автоматизации проектирования сопоставимых по мощности и функционалу, необходимо не только разрабатывать надежные и проверенные отечественные средства, но и поддерживать входящие в них методы и алгоритмы современными и быстродействующими. Данная методика размещения призвана сократить время размещения ИМЭ в процессе разработки за счет использования современных технологий на базе искусственного интеллекта.
Основываясь на результатах научных исследований , связанных с внедрением искусственного интеллекта в смежных областях, а также на анализе различных методов и средств, использование глубокого обучения с подкреплением приведет к значительным улучшениям в области автоматизации размещения ИМЭ.