Оптимизация топологии СБИС в иерархических моделях

• Автор: Сырцов, Илья Анатольевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 170 с. : ил.

1.1. ДЕКОМПОЗИЦИЯ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ

1.2. РАЗМЕЩЕНИЕ И ПЛАНИРОВКА КРИСТАЛЛА СБИС

1.3. МАКРОТРАССИРОВКА ЦЕПЕЙ СБИС

1.4. ДЕТАЛЬНАЯ ТРАССИРОВКА ЦЕПЕЙ СБИС

1.5. СЖАТИЕ ТОПОЛОГИИ СБИС

вывода

ГЛАВА 2. МЕТОДОЛОГИЯ ИЕРАЫЕСрЭГЛ СИНТЕЗА

ТОПОЛОГИИ СБИС1

2.1. ГЛОБАЛЬНЫЕ ПРОБЛЕМЫ ТОПОЛОГИЧЕСКОГО СИНТЕЗА

2.2. МЕТОДОЛОГИЯ ИСПОЛЬЗОВАНИЯ ОБЩЕЙ ИЕРАРХИЧЕСКОЙ МОДЕЛИ

2.3. ДЕКОМПОЗИЦИЯ И ОПЕРАЦИИ МАКРОСИНТЕЗА КРИСТАЛЛА

2.4. ОПЕРАЦИИ ДЕТАЛЬНОГО СИНТЕЗА КРИСТАЛЛА
ВЫВОДЫ
ГЛАВА 3. МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ
ИЕРАРХИЧЕСКОГО ПРОЕКТИРОВАНИЯ
3.1. МЕТОД ИТЕРАЦИОННОЙ РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ
3.2. АЛГОРИТМ МАКРОТРАССИРОВКИ НА ОСНОВЕ ВЕКТОРНОЙ МОДЕЛИ
3.3. ВЕКТОРНЫЙ МЕТОД ДЕТАЛЬНОЙ ТРАССИРОВКИ
3.4. СИЛОВОЙ АЛГОРИТМ СЖАТИЯ
ВЫВОДЫ 0
ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ
АЛГОРИТМОВ ОПТИМИЗАЦИИ
4.1. ОРГАНИЗАЦИЯ БАЗЫ ДАННЫХ В ИЕРАРХИЧЕСКОЙ САПР
4.2. РЕАЛИЗАЦИЯ АЛГОРИТМА РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ
4.3. АДАПТАЦИЯ АЛГОРИТМА ВЕКТОРНОЙ МАКРОТРАССИРОВКИ К САПР С БИНАРНЫМ ДЕРЕВОМ ИЕРАРХИИ
4.4. ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ ДЕТАЛЬНОГО СИНТЕЗА В ИЕРАРХИЧЕСКИХ САПР
ВЫВОДЫ
ГЛАВА 5. ПРОЕКТИРОВАНИЕ ТОПОЛОГИИ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР
5.1. СТРУКТУРНАЯ СХЕМА СВЯЗЕЙ МЕЖДУ ПРОЦЕДУРАМИ
В СИСТЕМЕ ПРОЕКТИРОВАНИЯ АИСТ
5.2. НАСТРОЙКА ПАРАМЕТРОВ МАРШРУТА ПРОЕКТИРОВАНИЯ
5.3 ПРОЕКТИРОВАНИЕ ПЕЧАТНЫХ ПЛАТ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР
ВЫВОДЫ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Таким образом, проблема размещения блоков может быть сведена к задаче целочисленного программирования. Такой подход называется глобальным размещением. Однако, на практике, вследствие очень большой размерности, он используется крайне редко 8. Зачастую для выполнения конструктивного размещения используют алгоритмы, основанные на моделировании определенных физических процессов, например, распределение мощности в электрической сети 9 или силовое притяжение . Основной недостаток подобных алгоритмов высокая вычислительная сложность, вследствие чего их применение на практике ограничено. Класс алгоритмов, основанных на идее рекурсивного деления схемы на подсхемы, является наиболее распространенным в настоящее время для решения задач размещения и планировки . Основная идея данного подхода состоит в том, что каждый раз доступная область топологии делится системой горизонтальных или вертикальных сечений на множество секций. Затем какаялибо часть декомпозированной схемы назначается в определенную область. Данный процесс рекурсивно продолжается до тех пор, пока в схеме остается хотя бы один неразмещенный вентиль. При разбиении подсхемы на группы необходимо минимизировать размер сечений. Достаточно качественных результатов размещения можно добиться, если в процессе декомпозиции схемы использовать алгоритм групповых перестановок. Алгоритм Брейера является одним из наиболее ярких представителей данного метода. Основной его идеей является снижение количества цепей, пересекающих линию сечения. Брейером были сформулированы следующие принципы.