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

• Заплетина Мария Андреевна
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Заплетина Мария Андреевна

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

ВВЕДЕНИЕ

Глава 1 Анализ существующих методов и алгоритмов этапа трассировки межсоединений СБИС на основе реконфигурируемых ИС

1.1 Классические методы и алгоритмы решения задачи трассировки

1.2 Современные направления развития методов решения задачи трассировки

1.3 Неклассические методы решения задачи трассировки

1.4 Методы предварительной оценки трассируемости проектной схемы

1.5 Анализ динамики выхода публикаций по проблеме диссертации

1.6 Выводы

Глава 2 Разработка архитектурно-зависимых теоретико-графовых моделей коммутационных ресурсов реконфигурируемых ИС

2.1 Классическая графовая модель трассировочных ресурсов

2.2 Модель смешанного графа трассировочных ресурсов

2.3 Формализация задачи трассировки межсоединений в терминах модифицированной смешанной графовой модели

2.4 Разработка расширенной модели смешанного графа трассировочных ресурсов

2.5 Разработка смешанной плоско-иерархической модели коммутационных ресурсов

2.6 Выводы

Глава 3 Разработка архитектурно-зависимых методов ускоренной автоматической трассировки межсоединений реконфигурируемых ИС

3.1 Разработка алгоритма разрыва и перетрассировки для адаптированного алгоритма А*

3.2 Разработка методов ускоренной автоматической трассировки на основе модифицированного метода Pathfinder

3.3 Метод ускоренной автоматической трассировки на основе расширенной модели коммутационных ресурсов реконфигурируемых ИС

3.4 Применение иерархической трассировки реконфигурируемой ИС на основе смешанной плоско-иерархической графовой модели

3.5 Выводы

Глава 4 Программная реализация предложенных моделей и методов автоматической трассировки

4.1 Программные описания используемых моделей коммутационных ресурсов

4.2 Программно-алгоритмическая реализация методов автоматической трассировки межсоединений

4.3 Выводы

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ 1. Акт внедрения от ДЦ «Союз»

ПРИЛОЖЕНИЕ 2. Акт внедрения от АО «НИИМЭ»

ПРИЛОЖЕНИЕ 3. Акт внедрения от ИППМ РАН

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

БД - база данных

ГЛЭ - группа логических элементов

ИС - интегральная схема

ЛЭ - логический элемент

ЛЯ - логическая ячейка

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

СБИС - сверхбольшая интегральная схема

СнК - система на кристалле

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

LAB - logic array block (группа логических элементов)

LE - logic element (логический элемент)

LUT - look up table (функциональная таблица истинности)

Введение диссертации (часть автореферата) на тему «Автоматизация этапа трассировки межсоединений в физическом проектировании СБИС на основе реконфигурируемых интегральных схем»

ВВЕДЕНИЕ

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

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

Реконфигурируемые ИС представлены как продуктами зарубежных компаний, среди которых наибольшая часть рынка принадлежит Intel (собственные разработки и наследие поглощенной компании Altera - серии Agilex [2], Stratix [3], Arria [4], Max [5], Cyclone [6]), Xilinx (серии Spartan [7], Virtex [8], Kintex [9], Artix [10]), Microsemi (серии PolarFire [11, 12], IGLOO [13] и IGLOO2 [14], ProASIC3 [15], Fusion Mixed Signal [16]), Lattice Semiconductors (серии CertusPro-NX [17], Certus-NX [18], ECP5 [19], LatticeECP3 [20], LatticeECP2/M [21] и др.), Efinix (серии Trion [22], Titanium [23]), Cypress (серия реконфигурируемых СнК PSoC 6 Microcontrollers [24]), так и микросхемами российских производителей: ДЦ «Союз» (ПАИС 5400ТР035 [25], ПАЦИС 5400ТР094 [26]), АО «ВЗПП-С» (ПЛИС 5578ТС064, 5578ТС094, 5576ХС1Т, 5576ХС4Т и др.) [27, 28], АО «ПКК Миландр» (ПЛИС М3, разрабатываемая в рамках ОКР «Бриллиант» [29]), АО «НИИМЭ» и ПАО «Микрон» (ПЛИС, разрабатываемые в рамках ОКР «Алмаз-14» [30], ОКР «Алмаз-19-Т» [31], ОКР «Логика-И2» [32], ОКР «Схема-И11-Т»[33]).

Реконфигурируемые интегральные схемы обладают рядом конкурентных преимуществ по сравнению со схемами заказного и полузаказного (например,

базовые матричные кристаллы) проектирования. В первую очередь, их достоинствами являются короткий цикл проектирования готового устройства с пользовательской функциональностью, сокращенное время выхода на рынок, крайне малые для конечного пользователя единовременные затраты на проектирование (англ. Non-Recurring Engineering costs), включенные в цену кристалла реконфигурируемой ИС, а также возможность быстрого перепрограммирования без использования специализированного высокотехнологичного оборудования. Разработка реконфигурируемых ИС с новыми архитектурными решениями, с одной стороны, расширяет возможности разработчиков радиоэлектронной аппаратуры на основе реконфигурируемых ИС и, с другой стороны, требует создания новых эффективных методов и моделей маршрута физического проектирования, обеспечивающих поддержку всех структурных особенностей таких ИС, высокое качество и скорость имплементации проектных решений заказчика.

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

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

заключен значительный потенциал. Подтверждения этого тезиса найдены с помощью представленных в работе методов и моделей трассировки, реализованных в составе системы автоматизированного проектирования для имплементации пользовательских СБИС на основе нескольких целевых реконфигурируемых ИС российского производства ([26], [30 - 31] и др.).

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

В настоящее время проблемами автоматизации этапа трассировки реконфигурируемых ИС занимается большое число ученых и специалистов за рубежом: А. Аль-Хьяри, Дж. Андерсон, В. Бетз, Д. Веркруйче, М. Горт, С. Зонг, И. Л. Марков, Д.-Ж. Нам, У. Фарук и др. В России направление разработки методов и моделей для автоматизации проектирования на реконфигурируемых ИС развито слабее (Гаврилов С.В. с коллегами, Цыбин С.А., Строганов А.В., Пирогов А.А. и др.). Причина этого заключается в том, что в большинстве российские разработчики радиоэлектронной аппаратуры десятилетиями использовали зарубежные реконфигурируемые микросхемы, поставляемые с существующими проприетарными САПР. Однако постепенно появилось понимание пагубности такой практики для отечественной микроэлектроники и безопасности страны в целом. В связи с этим, высокий спрос на микросхемы этого класса в настоящее время привел к появлению российских производителей, ведущих собственные научно-исследовательские и опытно-конструкторские работы по созданию реконфигурируемых схем и систем автоматизированного проектирования для их поддержки. Основные российские группы специалистов и научные школы сосредоточены на предприятиях-производителях реконфигурируемых ИС (перечислены выше), в нескольких академических институтах и высших учебных заведениях (Институт проблем проектирования в микроэлектронике РАН, Институт системного программирования им. В. П. Иванникова РАН, Московский государственный университет,

Московский институт электронной техники, Южный федеральный университет, Санкт-Петербургский государственный университет).

Особенности (в значительной степени неоднородность) схемотехнической структуры современных гетерогенных реконфигурируемых ИС сверхбольшой степени интеграции, разреженность структуры коммутационных ресурсов и наличие сложных логических зависимостей между ними, а также чрезвычайно высокая размерность №-полной задачи трассировки [34 - 36] снижают эффективность существующих моделей и методов решения задачи трассировки и усложняют разработку новых. №-полнота означает, что существование эффективного универсального алгоритма для всей группы задач трассировки (как и доказательство его отсутствия) эквивалентно одному из центральных вопросов теории сложности о равенстве между классами Р и ИР. Применение стратегии «разделяй и властвуй», в частности, декомпозиция трассировочных ресурсов на схемотехнические уровни иерархии с последующим решением задачи трассировки на каждом из них [37] способно обеспечить положительный результат. Однако в большом числе современных промышленных архитектур реконфигурируемых ИС иерархический подход способен привести к избыточному усложнению теоретической модели описания реконфигурируемой ИС и низкой вычислительной эффективности реализации иерархической стратегии в целом. В этом случае лучший результат способны обеспечить эвристические методы, основывающиеся на новых, гибких моделях описания коммутационных ресурсов, позволяющих более полно и эффективно использовать особенности их архитектуры.

В настоящее время можно выделить четыре общих подхода к решению задач этапа трассировки межсоединений. Первый подход подразумевает введение алгоритмических улучшений в классические алгоритмы трассировки и поиска кратчайшего пути [38, 39]. В эту группу методов можно включить также параллельные версии классических алгоритмов, например, [40]. Подход позволяет

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

Для второго подхода характерна разработка методов и моделей на новых математических основах, таких, как задача выполнимости булевых формул [41], клеточные автоматы [42], алгоритмы, реализующие идею совместного выполнения размещения и трассировки [43] и др. Кроме того, к этой группе можно отнести ряд алгоритмов для предварительной «грубой» глобальной трассировки межсоединений, которая позволяет получить оценку разводимости рассматриваемого размещения [44].

Третьему подходу следуют методы и алгоритмы, подразумевающие обязательную аппаратную реализацию в виде отдельного устройства либо разработанные для выполнения на специализированном вычислителе. Так, в работе [45] предложен аппаратный трассировщик на платформе Intel DE1-SoC с процессором ARM Cortex A9, а в [46, 47] программы трассировки созданы для запуска на графическом процессоре. Третий подход часто используется в исследовательских целях, поскольку способен обеспечить высокую скорость поиска трассировочного решения. Однако рядовой разработчик радиоэлектронной аппаратуры, как правило, не имеет доступа к специальным вычислителям, поэтому внедрение методов такого рода в системы автоматизации проектирования, предполагающие промышленное использование, носит ограниченный характер.

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

традиционных методов. Например, представленный в 2007 г. метод RUDY [48] был применен в [49] и ряде других работ. При всём исследовательском оптимизме, окружающем направление методов искусственного интеллекта и машинного обучения, по качеству результата в настоящее время новые методы автоматизации этапа трассировки на их основе часто лишь незначительно [50] превосходят традиционные.

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

Целью диссертационной работы является исследование и разработка моделей, методов и алгоритмов для автоматизации этапа трассировки межсоединений в маршруте физического проектирования цифровых схем на основе реконфигурируемых интегральных схем (программируемых логических интегральных схем и реконфигурируемых систем на кристалле) с учетом их архитектурных и схемотехнических особенностей. Для её достижения решены следующие задачи:

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

2. Разработка алгоритма двухуровневой иерархической трассировки межсоединений с учетом особенностей архитектуры коммутационной сети реконфигурируемых ИС с элементами островной архитектуры.

3. Разработка алгоритма разрыва и перетрассировки для алгоритма А* для поиска кратчайшего пути между вершинами на смешанном графе.

4. Разработка группы методов автоматической трассировки межсоединений с применением предложенных в диссертации графовых моделей в маршруте физического проектирования в базисе реконфигурируемых ИС, превосходящих аналоги по набору заданных критериев качества трассировки.

5. Программная реализация перечисленных выше моделей, методов и алгоритмов в составе существующей системы автоматизации проектирования для реконфигурируемых интегральных схем.

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

Задачи диссертационного исследования решались с использованием методов и моделей теории графов и теории алгоритмов. В рамках исследования разработаны методы, развивающие алгоритм A* для поиска пути на взвешенном графе и метод Pathfinder для трассировки проектируемых схем на ПЛИС, адаптированный к представлению коммутационных ресурсов в виде смешанного графа. Метод декомпозиции применен для алгоритмической и программной реализации двухуровневого метода решения задачи трассировки на примере реконфигурируемой ИС с элементами островной архитектуры.

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

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

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

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

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

1. Расширенная смешанная графовая модель представления коммутационных ресурсов реконфигурируемой ИС и метод её настройки с использованием карт перегруженности.

2. Плоско-иерархическая смешанная модель описания коммутационных ресурсов и алгоритмическая реализация иерархической двухуровневой трассировки для реконфигурируемых ИС с использованием предложенной модели.

3. Группа методов ускоренной трассировки межсоединений для маршрута физического проектирования пользовательских схем на основе реконфигурируемых ИС.

4. Программно-алгоритмические реализации представленных моделей и методов трассировки.

Практическая значимость работы заключается в следующем: 1. Графовые модели, предложенные в рамках диссертации, формируют компактное описание коммутационных ресурсов целевых реконфигурируемых ИС с учетом их схемотехнических и архитектурных особенностей. Методы трассировки на их основе позволили кратно (от 1,3 до 2,6 раза для плоской трассировки и от 2,5 до 5,6 раза для двухуровневой иерархической) уменьшить

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

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

3. Предложенные в диссертации модели, методы и алгоритмы положены в основу программных средств для трассировки межсоединений СБИС в рамках физического проектирования в базисе ряда отечественных реконфигурируемых ИС (микросхемы семейств 5400ТР, 5510ХС, 5510ТС, 1931БЛ) и внедрены в АО «Научно-исследовательский институт молекулярной электроники», АО «Дизайн Центр «СОЮЗ» и Институте проблем проектирования в микроэлектронике РАН (ИППМ РАН), что подтверждено актами о внедрении, приведенными в Приложениях 1, 2, 3.

Диссертационное исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований в рамках научного проекта №20-37-90046.

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

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

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

1. VIII Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем», 2018, Россия, Москва, Зеленоград, доклад «Исследование механизма разрыва и перетрассировки на этапе топологического синтеза в базисе реконфигурируемых систем на кристалле».

2. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, 2019, Россия, Москва, Зеленоград, доклад «The Rip-up and Reroute Technique Research for Island-Style Reconfigurable System-on-Chip».

3. IX Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем», 2020, Россия, Москва, Зеленоград, доклады «Иерархический подход к трассировке реконфигурируемой системы на кристалле островного типа», «Применение SAT-подхода к трассировке блоков коммутации для реконфигурируемых систем на кристалле».

4. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, 2020, Россия, Москва, Зеленоград, доклады «The Global Interconnect Routing Approach for Reconfigurable System-on-a-chip», «The Iterative SAT Based Approach to Detailed Routing for Reconfigurable System-on-a-chip».

5. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, 2021, Россия, Москва, Зеленоград, доклады «Improving Pathfinder Algorithm Performance for FPGA Routing», «The Review of Cellular Automata Algorithms for Placement and Routing Problems».

6. X Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем», 2021, Россия, Москва, Зеленоград, «Методы ускорения работы модифицированного алгоритма трассировки Pathfinder для ПЛИС островного типа».

7. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, 2022, Россия, Санкт-Петербург, доклад «The Acceleration Techniques for the Modified Pathfinder Routing Algorithm on an Island-Style FPGA».

Публикации

Основные результаты диссертационной работы представлены в виде 16 научных трудов, среди которых 4 статьи опубликованы в ведущих рецензируемых журналах и сборниках из перечня Высшей аттестационной комиссии Минобрнауки РФ, и 12 - в журналах, входящих в базы цитирования Web of Science, Scopus, Russian Science Citation Index (RSCI).

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

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

В опубликованных в соавторстве работах личный вклад автора следующий: в [52 - 55] автором разработана модель описания коммутационных блоков, реализован двухуровневый иерархический метод трассировки на основе метода Pathfinder, выполнена основная часть экспериментальных исследований и обработка полученных данных; в [56 - 57] предложен и программно реализован алгоритм разрыва и перетрассировки для повышения трассируемости при использовании адаптированного алгоритма А* для поиска кратчайшего пути на смешанном графе; в [58 - 59] предложены и реализованы в программном коде изменения целевой функции модифицированного метода Pathfinder для смешанного графа трассировочных ресурсов, выполнена вся обработка и интерпретация полученных экспериментальных результатов трассировки; в [60] исследованы альтернативные алгоритмы для решения задач этапа трассировки; в [42, 91] автором выполнен поиск и обзор существующих методов поиска кратчайшего пути с применением моделей клеточных автоматов; в [61 - 63]

выполнена основная доля теоретических и все экспериментальные исследования по архитектурной настройке адаптированного метода Pathfinder.

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

Диссертационная работа состоит из списка сокращений, введения, четырех глав, заключения, списка использованных источников (163 наименования) и 3 приложений. Диссертация содержит 145 страниц, включая 12 таблиц, 27 рисунков.

Дальнейшее содержание диссертации кратко изложено далее.

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

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

интегрированной картой перегруженности и смешанная плоско иерархическая графовая модель.

Третья глава представлена несколькими параграфами.

Параграф 3.1 посвящен исследованию механизма разрыва и перетрассировки для алгоритма A* [65], адаптированного для работы со смешанным графом трассировочных ресурсов [51]. Механизм разрыва и перетрассировки применен к комбинаторной задаче перебора списка межсоединений проектируемой ИС для поиска оптимального порядка, обеспечивающего её разводимость.

Параграф 3.2 посвящен набору методов ускоренной автоматической трассировки межсоединений, основывающихся на методе Pathfinder, модифицированном для работы со смешанными графовыми моделями трассировочных ресурсов, представленными в Главе 2 диссертации. Разработанные спецификации целевой функции и специальные правила обхода графа трассировочных ресурсов позволили кратно уменьшить скорость нахождения трассировочного решения без ухудшения трассируемости. Работа методов проанализирована на примере четырех архитектур реконфигурируемых интегральных схем.

Параграф 3.3 посвящен методу ускоренной трассировки на основе направленного поиска и предтрассировочной оценки перегруженности коммутационных ресурсов с учетом данных расширенной графовой модели трассировочных ресурсов параграфа 2.4.

Параграф 3.4 включает в себя детали программно-алгоритмической реализации и результаты применения иерархической автоматической трассировки на основе смешанной плоско-иерархической модели коммутационных ресурсов из Главы 2.

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

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

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

Глава 1 Анализ существующих методов и алгоритмов этапа трассировки межсоединений СБИС на основе реконфигурируемых ИС

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

1.1 Классические методы и алгоритмы решения задачи трассировки

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

Список литературы диссертационного исследования кандидат наук Заплетина Мария Андреевна, 2023 год

Исх. Sí

На№ от

утверждаю

Генеральный Эректор ао «НИИМЭ» академик Р^ЧИ. профессор,

- 1 / Красников Г. Я.

18 марта 20 22 г.

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

резу лыатов диссертационной работы Заплстиной М.А. на соискание ученой степени кандидата технических наук

Тема диссертации: «Автоматизация этапа трассировки межсоединений в физическом проектировании СВИС на основе реконфнгурирусмых интегральных схем».

Настоящий акт составлен в том. что в АО «НИИМЭ» использованы и внедрены научные и практические результаты диссертационной работы Заллетиной М.А.. в том числе модели, методы и алгоритмы трассировки сверхбольших интегральных схем в базисе программируемых логических игггегразьных схем.

Предложенные в диссертационной работе модели, методы и алгоритмы использованы при выполнении ОКР «Разработка и освоение производства радиационно-стойкой отказоустойчивой ИЛИС емкостью не менее 250 тыс. логических вентилей со встроенными блоками Р1Х и умножителями» (шифр «Алмаз-14»). ОКР «Разработка и освоение серийного производства микросхемы типа система на кристалле, состоящей из ядер процессора и ПЛИС емкостью не менее 800 тыс. системных вентилей» (шифр «Логика-И2»), ОКР «Разработка и освоение серийного производства интегральной микросхемы потоковой обработки информации с применением программируемых логических элементов и трехкратным резервированием на кристалле» (шифр «Схема-Ш 1-Т»), а также при выполнении этапа прототнпнроваиия при разработке программируемых логических интегральных схем в рамках ОКР «Разработка и освоение серийного производства комплекта микросхем в составе ПЛИС емкостью не менее 24 000 вен гилей на основе статического ОЗУ. однократно программируемой памяти объемом не менее 8 Мбит и схемы управления питанием» (шифр «Алмаз-19-Т»), Разработанные модели, методы и алгоритмы программно реализованы и включены в состав комплекса средств автоматизированного проектирования для микросхем серии 5510ТС н микросхем серии 1931ВА.

Заместитель генерального директора по разработке и внедрению микросхем космического и специального назначения АО «НИИМЭ». кандидат технических на\ к

Тел.: [phone] e-mail: vennvä niime.ru

Россия. 124460. Москм. Зеленоград, ул. Академика Валиева. 6.1

Эннс Виктор Иванович

о «

О О

Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное учреждение науки

*

тЛш * ИНСТИТУТ ПРОБЛЕМ ПРОЕКТИРОВАНИЯ > В МИКРОЭЛЕКТРОНИКЕ

V . РОССИЙСКОЙ АКАДЕМИИ НАУК (ИППМ РАН)

124365, г. Москва. Зеленоград, Советская ул., дом 3, тел./факс: [phone], тел.: [phone]. www.ippm.ru,[e-mail], ИНН 7735043892, КПП 773501001, ОГРН 1037739118560

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

результатов диссертации Заплетиной М.А. «Автоматизация этапа трассировки

межсоединений в физическом проектировании СБИС на основе реконфигурируемых интегральных схем», представленной на соискание ученой степени кандидата технических наук

Настоящим актом подтверждается, что результаты диссертации Заплетиной М.А. использовались в научно-исследовательской работе Института проблем проектирования в микроэлектронике Российской академии наук в составных частях опытных конструкторских работ: «Разработка программного обеспечения для проектирования на ПЛИС» (шифр «Алмаз-14-И»), «Разработка программного обеспечения для проектирования на ПЛИС с интерфейсом для процессорного ядра» (шифр «Логика-И2-И»), «Разработка программного обеспечения для комплекта микросхем ПЛИС емкостью не менее 24 000 вентилей на основе статического ОЗУ» (шифр «Алмаз-19-Т-И»), а также в составной части научно-технического проекта Фонда перспективных исследований «Обоснование технического облика средств автоматизированного проектирования для программирования проблемно-ориентированной, гетерогенной ПЛИС» (шифр «ПЕМЗА-А2»),

Главный научный сотрудник,

^¿гг № //¿/л

УТВЕРЖДАЮ Заместитель директора ИППМ РАН

-_ С.Г. Бобков

«_#> -и^/Ус/ 2022 г.

д.т.н., профессор