Иерархическая экстракции цепей из топологии ИС

1.

Федеральное государственное автономное образовательное учреждение высшего образования
«Национальный исследовательский университет «Московский институт электронной техники»»
Институт “Институт интегральной электроники имени академика К.А. Валиева”
«Иерархическая экстракции цепей из
топологии ИС»
Студент: Шурупов Илья Викторович
Консультант: Сотников Михаил Анатольевич
Рук. от института: Калашников Вячеслав Сергеевич
Рук. по пед. практике: Булах Дмитрий Александрович
2024 год.
1

2.

Актуальность
• Подсистема миграции топологии:
- Получение схемы из топологии
- Построение ограничений для алгоритмов сжатия топологии
- Сохранение электрической связности схемы во время миграции
- Определение порядка миграции ячеек
• Потенциальное применение:
- Верификация топологии
- Расчет паразитных элементов
2

3.

Цель и задачи
Цель:
• Выбор подхода к реализации алгоритма иерархической экстракции цепей и
разработка вспомогательного интерфейса для визуального анализа топологии.
Задачи:
• Изучение базовых принципов алгоритма иерархической экстракции цепей
• Формирование требований к реализации алгоритма
• Описание входных и выходных данных
• Анализ возможных способов реализации
• Разработка дополнительных инструментов визуального анализа топологии
3

4.

Структурное представление топологии
Иерархическое представление топологии в БД
подсистемы миграции топологии
Плоское представление топологии
4

5.

Электрическая связность
Электрическая связность топологии
Эл. связность между ячейками
Эл. связность внутри одной ячейки
5

6.

Подходы к реализации алгоритма
Рассмотренные подходы:
• Полное сплющивание
• Плоская экстракция снизу-вверх
• Частичное сплющивание
Выбранный подход - Частичное сплющивание
6

7.

Полное сплющивание
Идея:
• Конвертация структур представления топологии (полное сплющивание топологии)
• Экстракция цепей из всех ячеек в целом, не рассматривая отдельно каждую ячейку
• Использование существующего алгоритма экстракции цепей плоской топологии
7

8.

Полное сплющивание
Плюсы:
• Нет необходимости анализировать каждую ячейку отдельно
• Простая реализация конвертации иерархического представления в плоское
• Относительно быстрое выполнение алгоритма
Минусы:
• Большое дублирование данных геометрии фигур
• Большое использование памяти во время работы алгоритма
• Сложная реализация обратной конвертации представления топологии
8

9.

Плоская экстракция снизу-вверх
Идея:
• Рассмотрение каждой ячейки отдельно
• Формирование окружения ячейки снизу вверх по иерархии топологии
• Использование существующего алгоритма экстракции цепей плоской топологии для каждой ячейки учитывая
сформированное окружение ячейки
9

10.

Плоская экстракция снизу-вверх
Плюсы:
• Можно запускать алгоритм плоской экстракции цепей отдельно на каждой ячейке
• Меньшее дублирование данных по сравнению с полным сплющивание
Минусы:
• Необходим предварительный анализ взаимодействия ячеек
• Все еще не самый оптимальный способ по использованию памяти
10

11.

Частичное сплющивание
Идея:
• Разбиение на два типа сбора данных – плоских и иерархических
• Использование существующего алгоритма экстракции цепей плоской топологии для каждой ячейки
• Рассмотрение всех ячеек сразу учитывая только их охватывающие прямоугольники (частичное сплющивание)
11

12.

Частичное сплющивание
Плюсы:
• Наименьшее использование памяти и времени за счет частичного сплющивания с кешированием
фигур и разделения на два типа анализа
• Самое быстрое выполнение алгоритма из рассмотренных подходов
Минусы:
• Сложная реализация анализа иерархического взаимодействий фигур
• Все ячейки могут принимать только определенные ориентации и единичный масштаб
12

13.

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

14.

Доп. инструменты виз. анализа топологии
Проводник имеет следующую функциональность:
• Исследование графовидной структуры базы данных в любом порядке
• Доступ к истории просмотра объектов и навигация по ней
• Рекурсивный поиск объектов по любым параметрам регулярными выражениями
• Синхронизация с графическим окном редактора
• Простой программный интерфейс для расширение поддерживаемых типов
14

15.

Выводы
• Изучены базовые принципы алгоритма иерархической экстракции цепей
• Сформированы требования к реализации алгоритма и его входные и выходные данные
• Проанализированы возможные способы реализации алгоритма
• Выбран наиболее подходящий для задачи способ реализации алгоритма
• Разработаны дополнительные инструменты визуального анализа топологии
15

16.

Итоги педагогической практики
Проведены 4 лабораторные работы по курсу «Теория Алгоритмов» для группы ЭН-24:
• Получен опыт объяснения материала лабораторной работы перед студентами
• Получен опыт подготовки материала для лабораторной работы
• Получен опыт приёма лабораторных работ у студентов
Руководитель: Булах Дмитрий Александрович
16

17.

Литература
1.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms 4th
Edition / MIT Press, 2022.
2.
Ласло М. Вычислительная геометрия и компьютерная графика на c++ / М. Ласло. Москва Бином, 1997.
3.
Naveed Sherwani. Algorithms for VLSI Physical Design Automation / Kluwer Academic Publishers, 1995.
4.
Yale N. Patt. Introduction to computing systems, from bits and gates to C/C++ and beyond / Mc Graw Hill 2001.
17