- Артикул:00-01057248
- Автор: Дж.Д. Ульман
- ISBN: 5-256-0025-3-8
- Обложка: Твердая обложка
- Издательство: Радио и связь (все книги издательства)
- Город: Москва
- Страниц: 480
- Формат: 60 х 88 1/16
- Год: 1990
- Вес: 732 г
Развернуть ▼
В книге американского ученого на основе последних достижений в области теории алгоритмов и методов проектирования СБИС анализируется связь структуры разрабатываемых СБИС и реализуемых в них алгоритмов. Проводится теоретический анализ сложности решения различных вычислительных задаче СБИС. Описываются как методы разработки алгоритмов, удобных для реализации в виде СБИС (например, систолических алгоритмов), так и параллельные структуры ЭВМ, эффективно реализуемые с помощью СБИС. Значительное внимание уделяется вопросам создания САПР СБИС, рассматриваются структуры систем автоматизации проектирования. Для инженерно-технических работников, специализирующихся в области проектирования СБИС.
Содержание
Предисловие
Глава 1. Модели СБИС
1.1. Интегральные микросхемы и принципы Мида - Конвей
Слои и формирование транзистора
Параметр размера
Правила проектирования Мида - Конвей
Контакты
Нагрузочные транзисторы
Вход и выход
1.2. Реализация логических функций с помощью СБИС
Обозначение элементов схем
Логические схемы с нагрузочными и ключевыми транзисторами
Проводники питания и заземления
Синхронизация
1.3. Электрические свойства микросхем
Правило для передающего транзистора
Восстановители
Нелинейные параметры транзисторов
Вычисления временных характеристик
Повышение скорости распространения сигнала
Логика с предзарядом
1.4. Абстрактные модели СБИС
Роль моделей при разработке алгоритмов
Координатная модель СБИС
Предположение о выпуклости
Хронометрирование
Количество слоев
Упражнения
Замечания по литературе
Глава 2. Нижние пространственно-временные границы
2.1. Введение в анализ нижних границ
Задачи
Расписания для входных и выходных сигналов и детерминизм
Три основных подхода к определению нижних пространственно-временных границ
Нижние границы на основе анализа размеров памяти
Нижние границы на основе анализа ввода-вывода
Введение в анализ нижних границ типа ’’площадь на квадрат времени”
2.2. Информация и пересекающие последовательности
Информация
Пересекающие последовательности
Влияние формы микросхемы
Схемы с контактными площадками по краям
2.3. Вероятностные схемы и алгоритмы
Однонаправленная информация
Сравнение вероятностных и детерминированных вычислений
2.4. Схемы с повторением входных воздействий
Информация при разбиениях с перекрытием
Влияние информации на пространство и время
Упражнения
Замечания по литературе
Глава 3. Топологические алгоритмы
3.1. Н-деревья
Схемы двоичного дерева
Н-деревья
3.2. Нижние пространственные границы для схем деревьев
Деревья с листьями по краям схемы
Нижняя граница длины проводника
Верхняя граница длины проводников для полных двоичных деревьев
3.3. Топологический алгоритм типа ’’разделяй и властвуй”
Разделители
Строгие разделители
Создание каналов
Топологический алгоритм
3.4. Топологическая схема распознавателей регулярных выражений
Графы регулярных выражений
Построение графа методом Макнотона - Ямады
Теорема о разделителях для графов регулярных выражений
Некоторые практические соображения
3.5. Топологическая схема для плоских графов
Концентрическое представление плоских графов
Теорема о разделителе для плоских графов
Число пересечений и площадь схемы
Сеть древовидных графов
Разделители для сети деревьев
Площадь, необходимая для сети деревьев
Число пересечений для сетей деревьев
Упражнения
Замечания по литературе
Глава 4. Разработка алгоритмов для СБИС
4.1. Процессоры и сети процессоров
Процессор
Требования к времени работы и размерам процессоров
4.2. Язык программирования для процессоров
Синхронизация
4.3. Древовидная многопроцессорная структура
Операции на дереве процессоров
Задача определения областей связности
4.4. Организация сети процессоров
Сортировка методом слияния нечетных-четных
Сортировка слиянием и слияние нечетных-четных в квадратной сети
Реализация сортировки методом слияния нечетных-четных для произвольного значения л
4.5. Организация сети деревьев
Сортировка
Алгоритм определения областей связности
Детерминированный по времени алгоритм с АТ2 = л3+ е для нахождения областей связности
Время работы алгоритма 4.4
Упражнения
Замечания по литературе
Глава 5. Систолические алгоритмы
5.1. Введение: систолическая свертка
Временной анализ систолической свертки
5.2. Правила преобразования систолических алгоритмов
Временные диаграммы
Правила преобразования
5.3. Умножение матриц и транзитное замыкание
Умножение матриц
Систолическое транзитивное замыкание
5.4. Другие алгоритмы на матрицах и графах
Кратчайшие пути
Области связности
Транспонирование
Сильно связные области
Покрывающие деревья
Нахождение мостов
Упражнения
Замечания по литературе
Глава 6. Вычислительные системы со сложными связями между элементами
6.1. Тасовщик с обменом
Карты памяти
Цепочки
Площадь схем тасовщиков с обменом
6.2. Бабочки
Структура из кубически связанных колец
6.3. Алгоритмы для сетей в виде бабочки
Нормальные алгоритмы для бабочки
Гиперкуб
Быстрое преобразование Фурье
Сортировка
6.4. Идеально параллельные ЭВМ и их моделирование
Сети коммутации
Сети с пакетной коммутацией
Обзор раздела
Перестановочная маршрутизация
Частичная маршрутизация и малое время ожидания выбора маршрутов
Распределение данных
Маршрутизация из многих точек в одну
Упражнения
Замечания по литературе
Глава 7. Обзор систем проектирования СБИС
7.1. Языки проектирования
Уровни абстракции
Организация системы проектирования
7.2. Язык задания геометрии CIF
Оператор Box
Оператор Layer
Заранее определенные элементы
7.3. CHISEL - препроцессор генерации языка CIF
Точки
Прямоугольники
Слои
Элементы и библиотеки элементов
Проводники
Транзисторы
Контактные выводы
7.4. Язык уровня переключений esim
7.5. Язык логического проектирования lgen
7.6. Язык отрезков LAVA
Точки
Транзисторы
Проводники
Условия
Элементы
Вызов элемента
Подключение элементов
Повторение
7.7. ПЛМ и их задание
Задание ПЛМ
7.8. Язык конечных автоматов SLIM
Реализация конечных автоматов с помощью ПЛМ
Микропрограммная реализация ПЛМ
Определение состояний
Дополнительные свойства языка SLIM
Конвейеризация
7.9. Язык регулярных выражений
Объявления
Регулярные выражения
Позиции и последователи
Перевод регулярных выражений в ПЛМ
Упражнения
Замечания по литературе
Глава 8. Алгоритмы компиляции и оптимизации
8.1. Оптимизация заданий ПЛМ
Манипуляции с заданиями
Расширение термов
Свертывание ПЛМ
Время работы алгоритма 8.3
Свертывание уровня ИЛИ
Разбиение ПЛМ
8.2. Компиляция языков отрезков
Задание неравенств
Решение систем неравенств
Циклические графы ограничений
8.3. Компиляция логики
Матрицы Вайнбергера
Оптимизация логики
Упорядочивание столбцов
Назначение дорожек
Проводники, меняющие дорожку
Альтернативные структуры реализации логики
SLAP
8.4. Компиляция регулярных выражений
Построение НКА по регулярным выражениям
Интерпретация НКА методами” до” и ’’после”
Совместимые символы и конфликтные состояния
Кодирование состояний
Разбиение регулярных выражений
8.5. На пути к кремниевой компиляции
Разделение управления и данных
Исключение переменных управления
Другие способы оптимизации
Выявление и использование параллелизма
Упражнения
Замечания по литературе
Глава 9. Алгоритмы автоматизации проектирования СБИС
9.1. Обнаружение пересечений прямоугольников
Одномерная динамическая задача
Группы прямоугольников
Реализация групп
Поиск в дереве групп
9.2. Алгоритмы выделения схемы
Нахождение узлов и транзисторов
Выполнение слияния множеств
Анализ времени работы алгоритма экстракции схемы
9.3. Проверка соблюдения правил проектирования
Проверки правил проектирования на высоком уровне
Растровый подход к проверке соблюдения правил проектирования
Подход Бейкера - Термана
Условные правила
Правила, основанные на проверке углов
Проверка правил проектирования с помощью операций над многоугольниками
Иерархическая проверка соблюдения правил проектирования
9.4. Алгоритм моделирования переключательных схем
Понятия теории решеток
Решетка сигналов
Функции транзисторов
Вычисление передаточных функций
Дистрибутивные функции
Улучшенный алгоритм моделирования
Некоторые методы ускорения работы алгоритмов
9.5. Система размещения, соединения и трассировки
Иерархическое размещение
Проводники питания и заземления
Создание канала
Глобальная трассировка
Упорядочивание пересечений между каналами
Канальная трассировка
9.6. Оптимальная трассировка
Плотность канала
Потоковая трассировка
Модель потоковой трассировки
Свободная разводка левого блока
Прямолинейная потоковая трассировка
Алгоритм вычисления разделения с линейным временем работы
Упражнения
Замечания по литературе
Приложение
П.1. О-большое и Омега-большая
П.2. Метод поиска по глубине
П.З. Регулярные выражения и недетерминированные автоматы
Недетерминированные автоматы
П.4. Краткое изложение быстрого параллельного алгоритма сортировки
Выбор расщепителя
Полный алгоритм
Список литературы
Список работ, переведенных на русский язык
Рекомендуем
Артикул 00-01032798
