Разработка математического и программного обеспечения систем топологического проектирования СБИС с использованием диаграмм Вороного

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

Содержание
Введение
Глава 1. Проблемы математического и программного обеспечения топологического проектирования СБИС
1.1. Тенденции развития математических и программных средств автоматизации топологического проектирования

1.2. Проблемы построения специализированных графовых моделей

1.3. Использование диаграмм Вороного в графовых моделях существующие и потенциальные области применения
1.4. Выводы

Глава 2. Динамический алгоритм построения абстрактной диаграммы Вороного

2.1. Определения диаграммы Вороного

2.2. Методы построения диаграмм Вороного

2.3. Абстрактная диа1рамма Вороного

2.4. Основная идея динамического алгоритма
2.5. Инкрементальный алгоритм Кляйна
2.6. Удаление объекта из ЛДВ и динамический алгоритм
2.7. Анализ динамического алгоритма
2.8. Выводы
Глава 3. Использование динамического алгоритма в системах проверки, исправления и сжатия топологии СБИС
3.1. Постановка задачи
3.2. Метод построения графа ограничений на основе диаграммы Вороного
3.3. Анализ эффективности метода
3.4. Анализ избыточности графа ограничений
3.5. Выводы
Глава 4. Использование динамического алгоритма в системе глобальной трассировки и оценки суммарной длины соединений СБИС
4.1. Постановка задач и
4.2. Метод построения графа трассировки на основе диаграммы Вороного
4.3. Анализ эффективности метода
4.4. Анализ избыточности модели на основе диаграммы Вороного по сравнению с сеточными моделями
4.5. Анализ точности модели на основе диаграммы Вороного по сравнению с графом пересечения каналов и другими моделями
4.6. Выводы
Глава 5. Использование динамического алгоритма в системе преобразования топологии фотошаблона в символьную модель
5.1. Постановка задачи
5.2. Метод декомпозиции манхэттенского многоугольника на основе диаграммы Вороного
5.3. Анализ эффективное метода
5.4. Адекватность декомпозиции на основе диаграммы Вороного требованиям символьной модели топологии
5.5. Выводы
Заключение
Список литературы


Цель диссертационной работы заключается в разработке эффективных динамических моделей, алгоритмов и программных средств на основе абстрактной диаграммы Вороного для использования в системах ТП СБИС. ДВ в системе преобразования топологии фотошаблона в символьное представление. СБИС, эксплуатируемый в компании Интел. Методы исследования базируются на фундаментальных положениях теории алгоритмов и вычислительной сложности, аналитической и вычислительной геометрии, общей топологии, правилах построения программного обеспечения, а также на принципах проектирования топологии интегральных схем. ТП. В ходе выполнения диссертационной работы получен ряд научных результатов, на данный момент не имеющих аналогов. АДВ - универсальный инструмент, повышающий эффективность различных методов ТП. ДВ специального вида. Этот факт лёг в основу динамического метода построения графа ограничений. Практическая значимость работы заключается в расширении интеллектуальных возможностей вычислительных систем ТП СБИС за счёт использования АДВ и динамического алгоритма её построения. Комплексно решаются проблемы быстродействия, качества и избыточности используемых графовых моделей в системах проверки, исправления и сжатия топологии, глобальной трассировки и оценки суммарной длины соединений СБИС, преобразования топологии. Для построения трёх независимых графовых моделей впервые предложены динамические методы на основе АДВ. Динамический алгоритм вычисления АДВ даёт выигрыш во времени локального обновления графовых моделей относительно полного перестроения: 0(п) по сравнению с 0(nogri) времени, где п - размер входных данных. Оценочное ускорение - от 5- раз до - раз при размерах входных данных от 0 до 1 0 0 объектов. Алгоритм востребован в интерактивных системах редактирования и итерационных методах оптимизации топологии. ДВ разного рода. Это позволяет унифицировать программный код и сократить его объём. Достоверность научных положений и выводов, полученных соискателем, подтверждается теоретическими выкладками и успешным промышленным внедрением. Личный вклад автора. Все основные результаты получены автором лично. Постановка задачи выполнена совместно с научным руководителем. Автор принимал активное участие в разработке архитектуры, реализации, документации и тестировании программного обеспечения, внедрённого в ЗАО «Интел А/О». Внедрение результатов работы. Метод преобразования фотошаблонного представления проводника в символьное внедрён в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О». При работе на символьной топологии уровня функциональных блоков (порядка 4 транзисторов) метод позволил однозначным образом осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в - раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1. Результаты диссертации внедрены в учебный процесс МФТИ на базовой кафедре Интела в курсе «Математические основы САПР». Апробация результатов работы проводилась на конференциях и семинарах: Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, , , гг. Международная научно-техническая конференция «Интеллектуальные САПР» (Дивноморское, , гг. Международный семинар «Дискретная математика и её приложения» (Москва, МГУ, г. Математические методы и приложения: пятнадцатые математические чтения РГСУ (Руза, г. Геометрия и дискрегный анализ» (Москва, Мехмат МГУ, каф. МаТИС, г. Доклады на конференции «Микроэлектроника и информатика» в и годах отмечены дипломами 1-ой степени в секции «Математические модели и алгоритмы в информатике». Публикации. Результаты диссертации отражены в трёх статьях [8][Ю][] и семи тезисах докладов [4][5][6][7][9][ ][]. Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из позиций. Работа содержит 5 стр.