Введение
Глава 1. Обзор методов сжатия топологии 8
1.1. Постановка задачи сжатия 9
1.2. Классификация алгоритмов сжатия 13
1.3. Одномерное сжатие 14
1.4. Алгоритмы, использующие два графа ограничений 25
1.5. Двумерное сжатие 31
1.6. Иерархическое сжатие 33
1.7. Оптимизация топологии 34
Выводы 36
Глава 2. Представление топологии и построение графа ограничений ... 37
2.1. Контурное представление топологии 37
2.2. Представление технологических правил 41
2.3. Построение графа ограничений 41
2.4. Способы минимизации длины критического пути в графе ограничений 47
2.5. Выводы 53
Глава 3. Методы сжатия топологии стандартных ячеек 55
3.1. Алгоритм 1.5 мерного сжатия 56
3.2. Анализ графа ограничений 60
3.3. Критерий остановки и анализ дальнейшей сжимаемости топологии .. 71
3.4. Выход из локальных минимумов 73
3.5. Заключительная оптимизация топологии 76
3.6. Сложность алгоритма сжатия 82
3.7. Выводы 83
Глава 4. Снижение размерности задачи сжатия 85
4.1. Метод линейной декомпозиции 85
4.2. Способы применения линейной декомпозиции 88
4.3. Выводы 89
Глава 5. Исследование эффективности методов сжатия 91
5.1. Выбор характеристики размера топологии стандартной ячейки 91
5.2. Зависимость времени сжатия от размеров топологии 93
5.3. Сравнение качества сжатия топологии 96
5.4. Минимизация задачи сжатия 100
5.5. Выводы 103
Заключение 104
Список литературы: 107
