eng
Содержание
Об авторах 11
Введение 12
Глава 1. Задача синтеза интегральных схем и основные сведения
о КМОП-технологии 14
1.1.
Основные сведения о КМОП-технологии 14
1.2.
Стандартные ячейки 18
1.3.
Проектирование специализированных ИС (ASIC) 20
1.4.
Маршрут проектирования цифровых интегральных схем 22
1.5.
Литература к главе 1 27
1.6.
Рекомендованная литература к главе 1 27
Глава 2. Основы теории графов. Алгоритмический подход 29
2.1.
Определение графа. Типы графов 29
2.2.
Смежность, инцидентность, степени 30
2.2.1.
Перечисление элементов 30
2.2.2.
Изображение 30
2.2.3.
Матрица инциденций 30
2.2.4.
Матрица смежности (весов) 31
2.2.5.
Списки смежности (ребер) 32
2.2.6.
Списки инцидентности ЗАПИСЬ[v] 33
2.2.7.
Код Харари 33
2.3.
Некоторые специальные графы 34
2.4.
Расстояния и метрические характеристики 35
2.5.
Изоморфизм 35
2.6.
Методы обхода графа 37
2.6.1.
Поиск в ширину 38
2.6.2.
Поиск в глубину 39
2.6.3.
Топологическая сортировка 40
2.6.4.
Стягивающие деревья 42
2.7.
Циклы в графе 42
2.7.1.
Эйлеровы графы 42
2.7.2.
Гамильтоновы циклы 45
6
Содержание
2.8.
Поиск кратчайших путей в графе 48
2.8.1.
Алгоритм нахождения кратчайшего пути 49
2.8.2.
Волновой алгоритм 50
2.8.3.
Алгоритм Дейкстры 51
2.8.4.
Алгоритм Беллмана и Форда 53
2.9.
Оптимальные каркасы 54
2.9.1.
Алгоритм Прима 55
2.10.
Планарные графы 56
2.11.
Гиперграфы 58
Представление гиперграфов 58
2.12.
Литература к главе 2 59
2.13.
Рекомендованная литература к главе 2 60
Глава 3. Применение методов вычислительной геометрии
для представления и обработки геометрической информации 61
3.1.
Вычислительная геометрия и смежные направления 61
3.2.
Направления развития вычислительной геометрии 62
3.3.
Примеры задач. Топологическое проектирование СБИС 63
3.3.1.
Попарные пересечения геометрических объектов 64
3.3.2.
Базовые вычислительные приемы 66
3.3.2.1.
Сравнение расстояний 66
3.3.2.2.
Повороты 66
3.3.2.3.
Пересечение отрезков 67
3.3.2.4.
Метод сканирующей линии 69
3.3.2.5.
Алгоритм проверки пересечений отрезков
(Ф. Препарата, М. Шеймос) 70
3.4.
Специфика геометрических методов 71
3.5.
Структуры данных вычислительной геометрии 72
3.5.1.
Двоичное дерево 73
3.5.2.
Многомерное двоичное дерево (k-d дерево) 74
3.5.2.1.
Основная концепция 74
3.5.2.2.
Неформальное описание 74
3.5.3.
Дерево отрезков 75
3.5.4.
Реберные списки 76
3.5.4.1.
Простой реберный список 76
3.5.4.2.
Реберный список с двойными связями (РСДС) 77
Содержание 7
3.6.
Сортировка геометрических данных на плоскости 78
3.6.1.
4D бинарное дерево 78
3.6.2.
Одномерные квадранты 79
3.6.3.
Иерархические квадранты (H-tree) 79
3.6.4.
R-деревья 80
3.7.
Литература к главе 3 82
3.8.
Рекомендованная литература к главе 3 82
Глава 4. Введение в модели и методы искусственного интеллекта
в САПР СБИС 83
4.1.
Области применения ИИ. Методы представления задач 84
4.1.1.
Области применения ИИ 85
4.1.2.
Краткий исторический обзор развития работ в области ИИ 85
4.1.3.
Основные направления искусственного интеллекта 87
4.1.4.
Методы представления задач 89
4.1.5.
Формулировка задачи в замкнутой форме 89
4.2.
Классические методы решения задач 91
4.2.1.
Список хорошо решаемых задач 92
4.2.2.
Список задач класса NP 92
4.3.
Абстрактные модели алгоритмов. Машина Тьюринга.
Классификация задач по сложности 94
4.3.1.
Теорема Кука: задача разрешимости логического
выражения является NP-сложной 94
4.3.2.
Отношения сводимости задач класса NP 96
4.4.
Методы решения задач класса NP 97
4.4.1.
Алгоритм перебора 97
4.4.2.
Жадный алгоритм 98
4.4.3.
Алгоритм Краскаля построения минимального
связывающего дерева 100
4.4.4.
Градиентные методы. Алгоритм A* 101
4.4.5.
Моделирование (имитация) отжига (Simulated Annealing) 103
4.4.6.
Динамическое программирование 107
4.4.6.1.
Задача технологического мэппинга 108
4.4.7.
Абстрактный эволюционный алгоритм 113
4.5.
Литература к главе 4 114
4.6.
Рекомендованная литература 115
8
Содержание
Глава 5. Разбиение (декомпозиция) интегральной схемы 116
5.1.
Задача разбиения интегральной схемы 116
5.1.1.
Примеры формулировок задачи разбиения 117
5.1.2.
Классификация алгоритмов 120
5.2.
Алгоритм Кодреса (метод максимальной конъюнкции –
минимальной дизъюнкции) 121
5.3.
Алгоритм декомпозиции фрагмента СБИС по критерию
равномерной линейной плотности внешних выводов 124
5.4.
Правило Рента 129
5.5.
Алгоритм Кернигана – Лина (KL) 131
5.6.
Алгоритм Федуччи – Маттеуса 133
5.7.
Алгоритм многоуровневого разбиения гиперграфа (hMeTiS) 135
5.8.
Литература к главе 5 139
5.9.
Рекомендованная литература к главе 5 140
Глава 6. Размещение модулей интегральной схемы 141
6.1.
Формулировка проблемы 142
6.2.
Классификация алгоритмов размещения 147
6.3.
Дискретные методы размещения 147
6.3.1.
Обратное размещение 148
6.3.2.
Метод ветвей и границ 149
6.4.
Непрерывные методы размещения 156
6.4.1.
Формулировка задачи 156
6.4.2.
Методы планировки кристалла 156
6.4.2.1.
Гильотинные алгоритмы ПУ-2 156
6.4.2.2.
Негильотинные алгоритмы ПУ-5 157
6.4.2.3.
Негильотинные алгоритмы ПУ-13 158
6.5.
Аналитические методы размещения 159
6.5.1.
Силовой алгоритм Уеды 160
6.5.2.
Силовой алгоритм размещения Kraftwerk 163
6.5.3.
Метод многоуровневого иерархического размещения
mPL5 165
6.5.4.
Capo 168
6.5.5.
Dragon 169
6.6.
Сравнение известных алгоритмов размещения
на промышленных примерах 173
Содержание 9
6.7.
Литература к главе 6 174
6.8.
Рекомендованная литература к главе 6 175
Глава 7. Трассировка соединений в интегральной схеме 176
7.1.
Представление областей трассировки 177
7.1.1.
Граф пересечений каналов 178
7.1.2.
Сетчатый граф трассировки (Grid Graph Model) 179
7.1.3.
Граф связности каналов (Channel Connectivity Graph) 179
7.1.4.
Граф связности пересечений каналов (Switchbox
Connectivity Graph) 180
7.2.
Метрики трассировки 181
7.2.1.
Переполнение или перегруженность (Congestion) 181
7.2.2.
Число поворотов (Bend Count) 182
7.2.3.
Длина соединений (Wirelength) 183
7.2.4.
Синхронизация (Timing) 184
7.2.5.
Емкость связи (Coupling) 184
7.3.
Маршрут глобальной трассировки 185
7.3.1.
Минимальные деревья Штейнера и методы их построения 186
7.3.1.1.
Итерационный алгоритм (I1S) 188
7.3.1.2.
Точный алгоритм построения дерева Штейнера (Flute) 189
7.3.2.
Алгоритм построения леса деревьев 195
7.3.2.1.
Алгоритм Флойда — Уоршелла 195
7.3.2.2.
Инкрементальный алгоритм обновления
кратчайших путей в графе 198
7.3.2.3.
Декрементальный алгоритм обновления
кратчайших путей 200
7.4.
Детальная трассировка 202
7.4.1.
Волновой алгоритм трассировки 202
7.4.2.
Модификации алгоритма трассировки лабиринта 203
7.4.3.
Трассировка многоконтактных цепей 207
7.5.
Канальная трассировка 210
7.5.1.
Плотность канала и граф горизонтальных
ограничений (HCG) 211
7.5.2.
Граф вертикальных ограничений VCG 211
7.5.3.
Алгоритм левого края (Left Edge) 212
7.5.4.
L-трассировка (Dogleg) 213
10
Содержание
7.5.5.
Условие существования решения задачи канальной
трассировки в двух слоях 216
7.5.6.
Трассировка коммутатора (Switchbox) 216
7.5.7.
Трассировка через ячейки 218
7.6.
Современные методы трассировки 219
7.6.1.
Многоуровневая трассировка 220
7.6.2.
Линейное программирование для решения задачи
трассировки 223
7.6.2.1.
Кратчайшие пути 224
7.6.2.2.
Максимальный поток 225
7.6.2.3.
Поиск потока с минимальными затратами 226
7.6.2.4.
Многопродуктовый поток 227
7.6.3.
Современная формулировка проблемы глобальной
трассировки 228
7.6.4.
Релаксация Лагранжа 230
7.7.
Литература к главе 7 232
7.8.
Рекомендованная литература к главе 7 235
Настоящее пособие подготовлено коллективом сотрудников
ООО «НМ-Тех» во главе с доктором технических наук, главным научным
сотрудником Образовательного центра компании Александром Михай-
ловичем Марченко, внесшим основной вклад в написание данной книги.
А. М. Марченко прошел путь от студента Московского института
электронной техники, который окончил в 1976 году, до получения уче-
ной степени доктора технических наук в 1995 году по направлениям раз-
работки и исследования методов и алгоритмов проектирования, а также
синтеза топологии интегральных схем. Свои знания и опыт, связанные
с разработкой и поддержкой различных систем автоматизированного
проектирования (САПР), он с успехом применял как в преподаватель-
ской деятельности на профессорских должностях в МИЭТ, МФТИ, МГУ,
так и в трудовой деятельности в различные годы, работая, координируя
или возглавляя российские подразделения международных компаний,
таких как Motorola, Intel, Nangate, Mentor Graphics/Siemens. Кроме того,
А. М. Марченко является автором более 110 научных работ, включая 3
учебных пособия и 8 изобретений.
В 2023 году А. М. Марченко присоединился к российской компании
«НМ-ТЕХ», где его основной деятельностью является подготовка и разви-
тие студентов и молодых специалистов по направлениям автоматизации
проектирования и разработки САПР.
Соавторами данной книги являются как ученики А. М. Марченко,
руководство которыми он осуществлял с их студенческой скамьи и кото-
рые впоследствии стали экспертами по разработке САПР, так и его дей-
ствующие коллеги, имеющие многолетний опыт в области автоматиза-
ции проектирования. Следует отметить, что все авторы данного пособия
также имеют значительный опыт работы и в отечественных компаниях,
и в российских подразделениях международных компаний по указанным
направлениям.
Поддержка государства и развитие направления разработки отечест-
венных САПР мотивировали авторов начать выпуск серии книг, посвя-
щенных методам, алгоритмам и математическим моделям, которые мо-
гут быть использованы при разработке различных инструментов САПР
микроэлектроники.
Ââåäåíèå
На всех этапах проектирования интегральных схем используются раз-
личные системы автоматизированного проектирования (САПР). Переход
на глубокие субмикронные и нанометровые технологии подстегнул раз-
витие программных инструментов САПР, и, как результат, в настоящее
время ни одна интегральная схема (ИС) не может быть разработана без
использования тех или иных средств САПР. В мировом масштабе раз-
работчики интегральных схем широко используют инструменты САПР
так называемой «большой тройки» — компаний — разработчиков САПР,
которые практически полностью покрывают все этапы проектирования
как цифровых, так и смешанных или аналоговых ИС. Отечественные
средства САПР практически отсутствуют и используются очень ограни-
ченно, лишь на отдельных этапах проектирования. Для формирования
полноценных отечественных маршрутов проектирования направление
разработки САПР в России требует существенного развития. При этом
для разработки САПР требуются не только навыки и опыт программиро-
вания, но и углубленное погружение в специализированные алгоритмы,
математические модели и т. п., а также понимание процесса проектирова-
ния ИС. В данном пособии авторы начинают рассмотрение базовых алго-
ритмов, математических моделей и методов синтеза, которые могут быть
использованы при разработке различных инструментов САПР СБИС.
Пособие включает следующие основные разделы.
В первой главе приведены основные сведения о КМОП-технологии,
показаны базовые маршруты проектирования интегральных схем и взаи-
модействие средств проектирования и систем автоматизированного про-
ектирования (САПР).
Во второй главе рассмотрены основы теории графов, их методы и ал-
горитмы, основные свойства.
В третьей главе показаны применение и классификация методов вы-
числительной геометрии при обработке геометрической информации,
рассмотрены структуры данных.
В четвертой главе затронуты вопросы возможности применения и за-
дачи искусственного интеллекта в САПР СБИС.
Пятая глава посвящена задаче разбиения или компоновки интеграль-
ной схемы и классификации алгоритмов разбиения.
Введение 13
В шестой главе рассмотрены задачи и алгоритмы размещения эле-
ментов интегральной схемы, проанализированы основные подходы
к размещению.
В седьмой главе проводится классификация алгоритмов трассировки,
затрагиваются вопросы трассировки соединений в интегральной схеме.
Таким образом, основной целью данного пособия является первичное
ознакомление с базовыми алгоритмами, математическими моделями,
методами синтеза, которые применяются разработчиками при создании
инструментов САПР.
Пособие ориентировано на специалистов, студентов и аспирантов,
специализирующихся в области разработки систем автоматизированного
проектирования (САПР) микроэлектроники.
Технология на основе комплементарной структуры металл — оксид (ди-
электрик) — полупроводник (КМОП) к 2000 году стала доминирующим
подходом в проектировании и изготовлении цифровых, и не только, ин-
тегральных схем [1.5.1]. Основной принцип применения КМОП-техно-
логии в цифровых схемах основан на использовании комплементарных
пар МОП-транзисторов P-типа и N-типа для реализации функций ком-
бинационных и последовательностных элементов. Несмотря на тот факт,
что КМОП-технология широко используется при создании аналоговых
и схем смешанного сигнала (например, операционные усилители, цифро-
аналоговые и аналого-цифровые преобразователи и т. д.), в данной работе
мы сконцентрировались на применениях для проектирования цифровых
СБИС.
Общая структура МОП-транзистора N-типа и его условное обозначе-
ние показаны на рис. 1.1. МОП-транзистор N-типа является 4-выводным
полупроводниковым прибором (четырехполюсником). Прибор формиру-
ется областями с различным типом проводимости — подложкой P-типа,
истоком и стоком с проводимостью N-типа, а также управляющим поли-
кремниевым затвором, отделенным от подложки тонким слоем диэлек-
трика (обычно оксида кремния SiO2). Необходимо отметить, что в ряде
случаев затвор может быть металлическим.
Принцип работы N-МОП-транзистора с индуцированным каналом
в ключевом режиме показан на рис. 1.2 и включает следующие состояния:
ООО «НМ-Тех» во главе с доктором технических наук, главным научным
сотрудником Образовательного центра компании Александром Михай-
ловичем Марченко, внесшим основной вклад в написание данной книги.
А. М. Марченко прошел путь от студента Московского института
электронной техники, который окончил в 1976 году, до получения уче-
ной степени доктора технических наук в 1995 году по направлениям раз-
работки и исследования методов и алгоритмов проектирования, а также
синтеза топологии интегральных схем. Свои знания и опыт, связанные
с разработкой и поддержкой различных систем автоматизированного
проектирования (САПР), он с успехом применял как в преподаватель-
ской деятельности на профессорских должностях в МИЭТ, МФТИ, МГУ,
так и в трудовой деятельности в различные годы, работая, координируя
или возглавляя российские подразделения международных компаний,
таких как Motorola, Intel, Nangate, Mentor Graphics/Siemens. Кроме того,
А. М. Марченко является автором более 110 научных работ, включая 3
учебных пособия и 8 изобретений.
В 2023 году А. М. Марченко присоединился к российской компании
«НМ-ТЕХ», где его основной деятельностью является подготовка и разви-
тие студентов и молодых специалистов по направлениям автоматизации
проектирования и разработки САПР.
Соавторами данной книги являются как ученики А. М. Марченко,
руководство которыми он осуществлял с их студенческой скамьи и кото-
рые впоследствии стали экспертами по разработке САПР, так и его дей-
ствующие коллеги, имеющие многолетний опыт в области автоматиза-
ции проектирования. Следует отметить, что все авторы данного пособия
также имеют значительный опыт работы и в отечественных компаниях,
и в российских подразделениях международных компаний по указанным
направлениям.
Поддержка государства и развитие направления разработки отечест-
венных САПР мотивировали авторов начать выпуск серии книг, посвя-
щенных методам, алгоритмам и математическим моделям, которые мо-
гут быть использованы при разработке различных инструментов САПР
микроэлектроники.
Ââåäåíèå
На всех этапах проектирования интегральных схем используются раз-
личные системы автоматизированного проектирования (САПР). Переход
на глубокие субмикронные и нанометровые технологии подстегнул раз-
витие программных инструментов САПР, и, как результат, в настоящее
время ни одна интегральная схема (ИС) не может быть разработана без
использования тех или иных средств САПР. В мировом масштабе раз-
работчики интегральных схем широко используют инструменты САПР
так называемой «большой тройки» — компаний — разработчиков САПР,
которые практически полностью покрывают все этапы проектирования
как цифровых, так и смешанных или аналоговых ИС. Отечественные
средства САПР практически отсутствуют и используются очень ограни-
ченно, лишь на отдельных этапах проектирования. Для формирования
полноценных отечественных маршрутов проектирования направление
разработки САПР в России требует существенного развития. При этом
для разработки САПР требуются не только навыки и опыт программиро-
вания, но и углубленное погружение в специализированные алгоритмы,
математические модели и т. п., а также понимание процесса проектирова-
ния ИС. В данном пособии авторы начинают рассмотрение базовых алго-
ритмов, математических моделей и методов синтеза, которые могут быть
использованы при разработке различных инструментов САПР СБИС.
Пособие включает следующие основные разделы.
В первой главе приведены основные сведения о КМОП-технологии,
показаны базовые маршруты проектирования интегральных схем и взаи-
модействие средств проектирования и систем автоматизированного про-
ектирования (САПР).
Во второй главе рассмотрены основы теории графов, их методы и ал-
горитмы, основные свойства.
В третьей главе показаны применение и классификация методов вы-
числительной геометрии при обработке геометрической информации,
рассмотрены структуры данных.
В четвертой главе затронуты вопросы возможности применения и за-
дачи искусственного интеллекта в САПР СБИС.
Пятая глава посвящена задаче разбиения или компоновки интеграль-
ной схемы и классификации алгоритмов разбиения.
Введение 13
В шестой главе рассмотрены задачи и алгоритмы размещения эле-
ментов интегральной схемы, проанализированы основные подходы
к размещению.
В седьмой главе проводится классификация алгоритмов трассировки,
затрагиваются вопросы трассировки соединений в интегральной схеме.
Таким образом, основной целью данного пособия является первичное
ознакомление с базовыми алгоритмами, математическими моделями,
методами синтеза, которые применяются разработчиками при создании
инструментов САПР.
Пособие ориентировано на специалистов, студентов и аспирантов,
специализирующихся в области разработки систем автоматизированного
проектирования (САПР) микроэлектроники.
Технология на основе комплементарной структуры металл — оксид (ди-
электрик) — полупроводник (КМОП) к 2000 году стала доминирующим
подходом в проектировании и изготовлении цифровых, и не только, ин-
тегральных схем [1.5.1]. Основной принцип применения КМОП-техно-
логии в цифровых схемах основан на использовании комплементарных
пар МОП-транзисторов P-типа и N-типа для реализации функций ком-
бинационных и последовательностных элементов. Несмотря на тот факт,
что КМОП-технология широко используется при создании аналоговых
и схем смешанного сигнала (например, операционные усилители, цифро-
аналоговые и аналого-цифровые преобразователи и т. д.), в данной работе
мы сконцентрировались на применениях для проектирования цифровых
СБИС.
Общая структура МОП-транзистора N-типа и его условное обозначе-
ние показаны на рис. 1.1. МОП-транзистор N-типа является 4-выводным
полупроводниковым прибором (четырехполюсником). Прибор формиру-
ется областями с различным типом проводимости — подложкой P-типа,
истоком и стоком с проводимостью N-типа, а также управляющим поли-
кремниевым затвором, отделенным от подложки тонким слоем диэлек-
трика (обычно оксида кремния SiO2). Необходимо отметить, что в ряде
случаев затвор может быть металлическим.
Принцип работы N-МОП-транзистора с индуцированным каналом
в ключевом режиме показан на рис. 1.2 и включает следующие состояния: