Вычислительные аспекты СБИС

Ульман Дж.5256002538

Table of contents :
Обложка……Page 1
Оглавление……Page 475
Предисловие……Page 5
1.1. Интегральные микросхемы и принципы Мида – Конвей……Page 7
Слои и формирование транзистора……Page 8
Правила проектирования Мида – Конвей……Page 10
Контакты……Page 11
Нагрузочные транзисторы……Page 13
1.2. Реализация логических функций с помощью СБИС……Page 16
Логические схемы с нагрузочными и ключевыми транзисторами……Page 18
Синхронизация……Page 21
Правило для передающего транзистора……Page 24
Восстановители……Page 25
Нелинейные параметры транзисторов……Page 26
Вычисления временных характеристик……Page 28
Повышение скорости распространения сигнала……Page 31
Логика с предзарядом……Page 33
1.4. Абстрактные модели СБИС……Page 35
Роль моделей при разработке алгоритмов……Page 36
Координатная модель СБИС……Page 37
Хронометрирование……Page 41
Количество слоев……Page 43
Упражнения……Page 45
Замечания по литературе……Page 47
Задачи……Page 48
Расписания для входных и выходных сигналов и детерминизм……Page 49
Три основных подхода к определению нижних пространственно-временных границ……Page 51
Нижние границы на основе анализа размеров памяти……Page 52
Введение в анализ нижних границ типа “площадь на квадрат времени”……Page 54
2.2. Информация и пересекающие последовательности……Page 56
Информация……Page 57
Пересекающие последовательности……Page 61
Схемы с контактными площадками по краям……Page 64
2.3. Вероятностные схемы и алгоритмы……Page 65
Однонаправленная информация……Page 67
Сравнение вероятностных и детерминированных вычислений……Page 69
2.4. Схемы с повторением входных воздействий……Page 73
Информация при разбиениях с перекрытием……Page 76
Влияние информации на пространство и время……Page 77
Упражнения……Page 80
Замечания по литературе……Page 83
Глава 3. Топологические алгоритмы……Page 84
3.1. H-деревья……Page 85
Схемы двоичного дерева……Page 86
3.2. Нижние пространственные границы для схем деревьев……Page 89
Деревья с листьями по краям схемы……Page 90
Нижняя граница длины проводника……Page 92
Верхняя граница длины проводников для полных двоичных деревьев……Page 93
3.3. Топологический алгоритм типа “разделяй и властвуй”……Page 95
Разделители……Page 96
Строгие разделители……Page 98
Создание каналов……Page 101
Топологический алгоритм……Page 103
Графы регулярных выражений……Page 105
Построение графа методом Макнотона – Ямады……Page 107
Теорема о разделителях для графов регулярных выражений……Page 109
Некоторые практические соображения……Page 113
Концентрическое представление плоских графов……Page 114
Теорема о разделителе для плоских графов……Page 117
Число пересечений и площадь схемы……Page 121
Сеть древовидных графов……Page 122
Разделители для сети деревьев……Page 123
Площадь, необходимая для сети деревьев……Page 124
Число пересечений для сетей деревьев……Page 128
Упражнения……Page 130
Замечания по литературе……Page 131
Глава 4. Разработка алгоритмов для СБИС……Page 132
4.1. Процессоры и сети процессоров……Page 133
Процессор……Page 134
Требования к времени работы и размерам процессоров……Page 138
4.2. Язык программирования для процессоров……Page 140
Синхронизация……Page 141
Операции на дереве процессоров……Page 145
Задача определения областей связности……Page 146
4.4. Организация сети процессоров……Page 150
Сортировка методом слияния нечетных-четных……Page 151
Сортировка слиянием и слияние нечетных-четных в квадратной сети……Page 153
Реализация сортировки методом слияния нечетных-четных для произвольного значения n……Page 156
4.5. Организация сети деревьев……Page 160
Сортировка……Page 161
Алгоритм определения областей связности……Page 162
Детерминированный по времени алгоритм с AT²=n³+e для нахождения областей связности……Page 166
Время работы алгоритма 4.4……Page 171
Упражнения……Page 174
Глава 5. Систолические алгоритмы……Page 175
5.1. Введение: систолическая свертка……Page 176
Временной анализ систолической свертки……Page 180
Временные диаграммы……Page 181
Правила преобразования……Page 183
Умножение матриц……Page 190
Систолическое транзитивное замыкание……Page 193
5.4. Другие алгоритмы на матрицах и графах……Page 198
Области связности……Page 199
Транспонирование……Page 200
Сильносвязные области……Page 201
Покрывающие деревья……Page 202
Нахождение мостов……Page 204
Упражнения……Page 206
Глава 6. Вычислительные системы со сложными связями между элементами……Page 208
6.1. Тасовщик с обменом……Page 209
Карты памяти……Page 210
Цепочки……Page 211
Площадь схем тасовщиков с обменом……Page 213
6.2. Бабочки……Page 215
Структура из кубически связанных колец……Page 217
Нормальные алгоритмы для бабочки……Page 218
Быстрое преобразование Фурье……Page 220
Сортировка……Page 223
6.4. Идеально параллельные ЭВМ и их моделирование……Page 226
Сети коммутации……Page 227
Обзор раздела……Page 228
Перестановочная маршрутизация……Page 229
Частичная маршрутизация и малое время ожидания выбора маршрутов……Page 230
Распределение данных……Page 233
Маршрутизация из многих точек в одну……Page 238
Упражнения……Page 241
Глава 7. Обзор систем проектирования СБИС……Page 242
7.1. Языки проектирования……Page 243
Уровни абстракции……Page 245
Организация системы проектирования……Page 247
Оператор Box……Page 251
Оператор Layer……Page 252
Заранее определенные элементы……Page 254
7.3. CHISEL – препроцессор генерации языка CIF……Page 256
Точки……Page 258
Элементы и библиотеки элементов……Page 259
Проводники……Page 260
Транзисторы……Page 261
Контактные выводы……Page 263
7.4. Язык уровня переключений esim……Page 266
7.5. Язык логического проектирования lgen……Page 268
7.6. Язык отрезков LAVA……Page 270
Точки……Page 271
Транзисторы……Page 272
Проводники……Page 273
Условия……Page 274
Вызов элемента……Page 277
Подключение элементов……Page 278
Повторение……Page 279
7.7. ПЛМ и их задание……Page 281
Задание ПЛМ……Page 285
7.8. Язык конечных автоматов SLIM……Page 287
Реализация конечных автоматов с помощью ПЛМ……Page 288
Микропрограммная реализация ПЛМ……Page 289
Определение состояний……Page 292
Дополнительные свойства языка SLIM……Page 293
Конвейеризация……Page 295
7.9. Язык регулярных выражений……Page 298
Регулярные выражения……Page 299
Позиции и последователи……Page 300
Перевод регулярных выражений в ПЛМ……Page 301
Упражнения……Page 304
Замечания по литературе……Page 305
Глава 8. Алгоритмы компиляции и оптимизации……Page 306
Манипуляции с заданиями……Page 307
Расширение термов……Page 311
Свертывание ПЛМ……Page 312
Время работы алгоритма 8.3……Page 316
Разбиение ПЛМ……Page 317
8.2. Компиляция языков отрезков……Page 318
Задание неравенств……Page 321
Решение систем неравенств……Page 324
Циклические графы ограничений……Page 331
8.3. Компиляция логики……Page 332
Матрицы Вайнбергера……Page 333
Оптимизация логики……Page 335
Упорядочивание столбцов……Page 338
Назначение дорожек……Page 341
Альтернативные структуры реализации логики……Page 345
SLAP……Page 347
8.4. Компиляция регулярных выражений……Page 348
Построение НКА по регулярным выражениям……Page 349
Интерпретация НКА методами “до” и “после”……Page 352
Совместимые символы и конфликтные состояния……Page 354
Кодирование состояний……Page 357
Разбиение регулярных выражений……Page 361
8.5. На пути к кремниевой компиляции……Page 362
Разделение управления и данных……Page 365
Исключение переменных управления……Page 366
Другие способы оптимизации……Page 368
Выявление и использование параллелизма……Page 369
Упражнения……Page 371
Замечания по литературе……Page 373
9.1. Обнаружение пересечений прямоугольников……Page 374
Одномерная динамическая задача……Page 376
Группы прямоугольников……Page 377
Реализация группы……Page 378
Поиск в дереве групп……Page 379
9.2. Алгоритмы выделения схемы……Page 385
Нахождение узлов и транзисторов……Page 387
Выполнение слияния множеств……Page 389
9.3. Проверка соблюдения правил проектирования……Page 390
Проверки правил проектирования на высоком уровне……Page 391
Подход Бейкера – Термана……Page 392
Условные правила……Page 394
Правила, основанные на проверке углов……Page 395
Проверка правил проектирования с помощью операций над многоугольниками……Page 396
Иерархическая проверка соблюдения правил проектирования……Page 398
9.4. Алгоритм моделирования переключательных схем……Page 401
Понятия теории решеток……Page 402
Решетка сигналов……Page 403
Функции транзисторов……Page 405
Вычисление передаточных функций……Page 408
Дистрибутивные функции……Page 410
Улучшенный алгоритм моделирования……Page 414
Некоторые методы ускорения работы алгоритмов……Page 416
9.5. Система размещения, соединения и трассировки……Page 417
Иерархическое размещение……Page 418
Проводники питания и заземления……Page 421
Создание канала……Page 422
Глобальная трассировка……Page 424
Упорядочивание пересечений между каналами……Page 425
Канальная трассировка……Page 428
Плотность канала……Page 431
Модель потоковой трассировки……Page 433
Свободная разводка левого блока……Page 434
Прямолинейная потоковая трассировка……Page 437
Алгоритм вычисления разделения с линейным временем работы……Page 439
Упражнения……Page 442
Замечания по литературе……Page 444
П.1. О-большое и Омега-большая……Page 446
П.2. Метод поиска по глубине……Page 447
П.З. Регулярные выражения и недетерминированные автоматы……Page 448
Недетерминированные автоматы……Page 450
П.4. Краткое изложение быстрого параллельного алгоритма сортировки……Page 452
Полный алгоритм……Page 455
Список литературы……Page 457
Список работ, переведенных на русский язык……Page 474