Введение
Глава 1. Проблемы математического и программного обеспечения топологического проектирования СБИС 10
1.1. Тенденции развития математических и программных средств автоматизации топологического проектирования 10
1.2. Проблемы построения специализированных графовых моделей 11
1.3. Использование диаграмм Вороного в графовых моделях: существующие и потенциальные области применения 12
1.4. Выводы 19
Глава 2. Динамический алгоритм построения абстрактной диаграммы Вороного 20
2.1. Определения диаграммы Вороного 20
2.2. Методы построения диаграмм Вороного 29
2.3. Абстрактная диаграмма Вороного 3 5
2.4. Основная идея динамического алгоритма 39
2.5. Инкрементальный алгоритм Кляйна 39
2.6. Удаление объекта из АДВ и динамический алгоритм 48
2.7. Анализ динамического алгоритма 55
2.8. Выводы 60
Глава 3. Использование динамического алгоритма в системах проверки, исправления и сжатия топологии СБИС 62
3.1. Постановка задачи 62
3.2. Метод построения графа ограничений на основе диаграммы Вороного 65
3.3. Анализ эффективности метода 76
3.4. Анализ избыточности графа ограничений 77
3.5. Выводы 78
Глава 4. Использование динамического алгоритма в системе глобальной трассировки и оценки суммарной длины соединений СБИС 79
4.1. Постановка задачи 79
4.2. Метод построения графа трассировки на основе диаграммы Вороного 80
4.3. Анализ эффективности метода 85
4.4. Анализ избыточности модели на основе диаграммы Вороного по сравнению с сеточными моделями 86
4.5. Анализ точности модели на основе диаграммы Вороного по сравнению с графом пересечения каналов и другими моделями 86
4.6. Выводы 88
Глава 5. Использование динамического алгоритма в системе преобразования топологии фотошаблона в символьную модель 89
5.1. Постановка задачи 89
5.2. Метод декомпозиции манхэтгенского многоугольника на основе диаграммы Вороного 91
5.3. Анализ эффективности метода 102
5.4. Адекватность декомпозиции на основе диаграммы Вороного требованиям символьной модели топологии 103
5.5. Выводы 103
Заключение 105
Список литературы
