автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка математического и программного обеспечения систем топологического проектирования СБИС с использованием диаграмм Вороного

□0306427' 1'

На правах рукописи / ^

X'

V

о

Малннаускас Костас Костович

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

ВОРОНОГО

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2007 г

1 9 ИЮЛ 2007

Работа выполнена на кафедре Высшей математики № 1 Московского государственного института электронной техники (технического

университета)

Научный руководитель: доктор физико-математических наук,

доцент

Кожухов Игорь Борисович

Официальные оппоненты: доктор фшико-математических наук,

профессор

Селищев Сергей Васильевич

кандидат физико-математических наук, научный сотрудник Панкратьев Антон Евгеньевич

Ведущая органта^ия: ООО Фирм? «АНКАД», г Москва

Защита диссертации состоится » 2007 г в

часов на заседании диссертационного совет;/ Д 212 134 02 при Московском государстьенном институте электронной техники (техническом университете) па адресу 124498, г Москва, Зеленоград, МИЭТ

С диссертацией можно ознакомиться в бибшютеке МИЭТ

Автореферат разослан « » ¿угР-*^ 2007 г

Соискатель

* 1>

К К Малинаускас

Ученый секретарь диссертационного совета кандидат технических наук, профессор

АфФ^ 1

НВ Воробьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ С усложнением процессов производства интегральных схем, переходом на нанометровые технологии и увеличением степени интеграции растет внимание к средствам автоматизации топологического проектирования (Ш) СБИС. Системы ТП решают задачи синтеза топологии ИС и включают программные средства для размещения элементов схемы, глобальной и детальной трассировки соединений, анализа и оптимизации топологии по различным критериям Вклад в развитие систем ТП внесли рад отечественных и зарубежных авторов Г Г Казеннов, В М Щемелинин, В А Селютин, Б В Баталов, Г Э Широ, А М. Марченко, В Е Вулихман, А В Жмурин, Н Шервани, М Ласло, А Б Канг, Е Пападопуло и др Математический базис, используемый в отрасли, можно найти в трудах М Шеймоса, Ф Препараты, А Фокса, К Л Кларксона, ПВ Шора, Р Кляйна, Ф Ауренхаммера, С Фотьюна и др

В данной работе рассматриваются вопросы построения специализированных графовых моделей в системах ТТТ, востребованных при описании отношешш и связей между элементами топологии Здесь приходится сталкиваться со следующими проблемами Адекватность моделей предметной области - один из главных факторов, определяющий качество систем и процент выхода годных микросхем Уменьшение избыточности и размеров данных важно для оптимизации использования памяти и ускорения обработки данных Эффективность алгоритмов построения моделей — требование, обусловленное постоянно растущей степенью интеграции (более 108 транзисторов) Эффективность динамического обновления моделей особенно важна с возрастанием числа обратных связей в маршрутах проектирования, распространением итерационных методов оптимизации и интерактивного редактирования топологии В интерактивной системе человек ожидает быстрой реакции на свои действия, в итерационном методе многократные локальные корректировки топологии должны быть быстро отражены в используемых моделях

Для комплексного решения перечисленных проблем в настоящей работе предлагается использование моделей, основанных на диаграммах Вороного Классической диаграммой Вороного (ДВ) для точечных объектов называется разбиение плоскости на ячейки, каждая из которых есть локус точек, расположенных ближе к одному из объектов в метрике Евклида, чем к остальным Известны модификации данного определения для сложных объектов (отрезков, фигур и др), в

различных метриках и т д ДВ является плоским графом, ребра которого суть участки средних линий между объектами Идея использования ДВ в математическом и программном обеспечении систем ТП не является новой Как удобный инструмент решения ряда геометрических задач ДВ уже нашла применение в САПР, помогая строить адекватные графовые модели с относительно малыми затратами времени и памяти Так, известны примеры использования в системах оценки выхода годных и начального размещения

Использование ДВ может также повысить качество и уменьшить избыточность графовых моделей в системах глобальной трассировки, проверки, исправления, сжатия и преобразования топологии СБИС Актуальным представляется расширение области применения ДВ в математическом и программном обеспечении систем ТП, где востребованы эффективные средства представления информации о взаимном расположении элементов топологии СБИС в виде плоских графов Существуют эффективные динамические алгоритмы построения ДВ, перестраивающие ее локально быстрее, чем с нуля Несмотря на это, до сих пор динамические диаграммы не использовались в САПР Поэтому актуальным становится использование преимуществ динамического построения ДВ в интерактивных системах ТП, а также в итерационных методах локальной оптимизации топологии Однако известные динамические алгоритмы применимы только к конкретным определениям ДВ, те не являются универсальными Поэтому актуальна разработка универсального динамического алгоритма построения диаграмм Вороного разного рода, используемых в САПР Исхода из этого, решено обратиться к концепции абстрактной диаграммы Вороного (АДВ), обобщающей широкий класс ДВ

Цель диссертационной работы заключается в разработке эффективных динамических моделей, алгоритмов и программных средств на основе абстрактной диаграммы Вороного для использования в системах ТП СБИС Для достижения поставленной цели автором поставлены и решены следующие задачи

• разработка метода построения графа ограничений на основе ДВ в системах проверки, исправления и сжатия топологии СБИС,

• разработка метода построения планировочного графа на основе ДВ в системе глобальной трассировки и оценки суммарной длины соединений СБИС,

• разработка метода декомпозиции манхэтгенского многоугольника на основе ДВ в системе преобразования топологии фотошаблона в символьное представление

• разработка динамического алгоритма построения АДВ, теоретическое обоснование его корректности и эффективности,

• реализация метода декомпозиции многоугольника и его внедрение в программный комплекс оптимизации топологии СБИС, эксплуатируемый в компании Интел

Методы исследования базируются на фундаментальных положениях теории алгоритмов и вычислительной сложности, аналитической и вычислительной геометрии, общей топологии, правилах построения программного обеспечения, а также на принципах проектирования топологии интегральных схем

Научная новизна состоит в разработке моделей, методов и алгоритмов, вносящих вклад в развитие математической теории вычислений и обработки геометрических данных и позволяющих повысить качество и эффективность систем ТП В ходе выполнения диссертационной работы получен ряд научных результатов, на данный момент не имеющих аналогов

1 Доказана теорема об эффективном удалении объекта и разработан динамический алгоритм вычисления АДВ — универсальный инструмент, повышающий эффективность различных методов ТП

2 Доказано, что граф ограничений, используемый в задачах проверки, исправления и сжатия топологии является двойственным к ДВ специального вида Этот факт лег в основу динамического метода построения графа ограничений

3 Показана целесообразность использования ДВ в метрике Ь„ для построения планировочного графа в задачах глобальной трассировки и оценки суммарной длины соединений

4 Доказаны специальные свойства ядра Вороного в метрике Ь„, позволившие построить динамический метод декомпозиции многоугольника в задаче преобразования топологии фотошаблона в символьное представление

Практическая значимость работы заключается в расширении интеллектуальных возможностей вычислительных систем ТП СБИС за счет использования АДВ и динамического алгоритма ее построения Комплексно решаются проблемы быстродействия, качества и избыточности используемых графовых моделей в системах проверки, исправления и сжатия топологии, глобальной трассировки и оценки

суммарной длины соединений СБИС, преобразования топологии Для построения трех независимых графовых моделей впервые предложены динамические методы на основе АДВ Динамический алгоритм вычисления АДВ дает выигрыш во времени локального обновления графовых моделей относительно полного перестроения О(и) по сравнению с 0(п log и) времени, где п — размер входных данных Оценочное ускорение - от 5-10 раз до 20-40 раз при размерах входных данных от 100 до 1000 000 объектов Алгоритм востребован в интерактивных системах редактирования и итерационных методах оптимизации топологии Его программная реализация в виде модуля удобна для включения в библиотеку геометрического программного обеспечения и независимого повторного использования при построении моделей на основе ДВ разного рода Это позволяет унифицировать программный код и сократить его объём

Достоверность научных положений и выводов, полученных соискателем, подтверждается теоретическими выкладками и успешным промышленным внедрением

Личный вклад автора. Все основные результаты получены автором лично Постановка задачи выполнена совместно с научным руководителем Автор принимал активное участие в разработке архитектуры, реализации, документации и тестировании программного обеспечения, внедренного в ЗАО «Интел А/О»

Внедрение результатов работы. Метод преобразования фотошаблонного представления проводника в символьное внедрен в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О» При работе на символьной топологии уровня функциональных блоков (порядка 104 транзисторов) метод позволил однозначным образом осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в 10-15 раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1 5-2 8 раз Результаты диссертации внедрены в учебный процесс МФТИ на базовой кафедре Интела в курсе «Математические основы САПР»

На защиту выносятся:

1) метод построения графа ограничений на основе ДВ,

2) метод построения графа глобальной трассировки на основе ДВ,

3) метод декомпозиции фотошаблонного проводника на основе ДВ,

4) динамический алгоритм вычисления АДВ, лежащий в основе предложенных методов,

5) результаты промышленного внедрения

Апробация результатов работы проводилась на конференциях и семинарах Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2003, 2004, 2007 гг, 3 доклада), Международная научно-техническая конференция «Интеллектуальные САПР» (Дивноморское, 2003, 2005 гг, 2 доклада), Международный семинар «Дискретная математика и ее приложения» (Москва, МГУ, 2004 г, 1 доклад), Математические методы и приложения пятнадцатые математические чтения РГСУ (Руза, 2006 г, 1 доклад), семинар «Геометрия и дискретный анализ» (Москва, Мехмат МГУ, каф МаТИС, 2007 г, 1 доклад) Доклады на конференции «Микроэлектроника и информатика» в 2003 и 2007 годах отмечены дипломами 1-ой степени в секции «Математические модели и алгоритмы в информатике»

Публикации. Результаты диссертации отражены в трех статьях и семи тезисах докладов

Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 75 позиций Работа содержит 115 стр, 1 акт о внедрении в производство и 1 акт о внедрении в учебный процесс

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации, формулируются общие проблемы, цели и задачи исследования, научное и практическое значение полученных результатов

I "Г^лГ."".-' ~ „_ " \Т1 'с"« с 1; ;

"'тЧ'г^' 'г

г - г-ч-ч1-

Г - !>1 ■ г,

1 I1 , ,

■ ■ " * ■ !. ? « « ■■ ■ ^

Рисунок 1 - Пример топологии интегральной схемы

В первой главе приводится обзор тенденций развития современных математических и программных средств автоматизации топологического проектирования (111) и связанных проблем Системы ТП решают задачи синтеза топологии СБИС по функциональному и логическому описаниям для реализации на кристалле в виде транзисторов, стандартных ячеек и электрических соединений Топология схемы является сложным геометрическим объектом, состоящим из манхэттенских многоугольников (со сторонами, параллельными координатным осям), в полупроводниковых и металлических слоях (рисунок 1)

С усложнением технологических процессов и увеличением степени интеграции ИС растет внимание и повышаются требования к системам ТП Особенно это характерно для производства заказных СБИС, таких как микропроцессоры По мере того, как схемы становятся сложнее (до сотен миллионов транзисторов), а размеры элементов уменьшаются (десятки нанометров в настоящее время), приходится работать с топологиями больших размеров, одновременно учитывая разнообразные физические эффекты, возникающие на кристалле Несмотря на развитие вычислительных мощностей, математическое и программное обеспечение систем ТП вынуждено развиваться в сторону повышения качества моделей и эффективности алгоритмов Маршруты синтеза топологии характеризуются большим числом обратных связей, когда по результатам последующих этапов приходится уточнять решения, полученные на предыдущих Поэтому получили развитие итерационные методы ТП Например, по результатам глобальной трассировки уточняют начальное размещение блоков схемы Кроме того, требуется исправлять ошибки и проводить локальные корректировки на конечных стадиях проектирования Так, возможны перемещения элементов топологии, вставка буферов, изменение размеров транзисторов и тд При этом в интерактивном режиме требуется выполнить верификацию и оптимизацию схемы (сжатие, уменьшение задержек в цепях и т п ) В итерационных и интерактивных системах ТП востребованы динамические алгоритмы, позволяющие более эффективно работать при локальных изменениях топологии

Наряду со средствами для оптимального хранения и доступа к геометрическим данным (связные углы, одномерные и иерархические квадранты и др ), востребованы специализированные графовые модели, описывающие отношения и связи между элементами топологии СБИС Использование плоских графов имеет определенные преимущества Во-

первых, плоские графы являются разреженными (с линейной зависимостью числа вершин и ребер) и приводят к моделям линейного размера с малой избыточностью Во-вторых, возможен быстрый доступ к соседним элементам, что обеспечивает константную сложность локальных операций в моделях Среди проблем, возникающих при разработке графовых моделей, можно назвать адекватность моделей предметной области, уменьшение избыточности и размеров данных, эффективность алгоритмов построения и динамического обновления моделей Для комплексного решения проблем в данной работе предлагается использование моделей, основанных на диаграммах Вороного ДВ естественным образом сохраняет информацию о взаимном расположении соседних элементов топологии и расстояниях между ними Также она удобна для произведения локальных изменений Рассмотрим потенциальные области применения диаграмм ДВ в системах ТП.

Рисунок 2 Граф горизонтальных ограничений в одном слое

Системы проверки, исправления и сжатия топологии Топология фотошаблона представлена манхэттенскими многоугольниками, объединяющими элементы схемы в одном слое (участки транзисторов, проводящие соединения и др ) Проверка топологии состоит в создании отчета о нарушении технологических правил Одномерные технологические правила - это ограничения минимального и максимального расстояния, ширины, перекрытия и включения Исправление заключается в устранении нарушений путем наименьшей трансформации топология Одномерное сжатие состоит в минимизации совокупной площади кристалла путем перемещения элементов топологии вдоль одной из координат В системах проверки, исправления и сжатия часто используются методы, работающие на модели графа ограничений (рисунок 2) Вершины графа представляют подвижные элементы (стороны многоугольников), ребра - ограничения

на расстояния между ними. Построение графа является наиболее трудоемкой задачей. Используемые методы (сканирующей линии, теневые и др.) имеют сложность по времени 0(п log п), 0(nVn) и даже 0(п2). Неизвестен метод, более эффективно перестраивающий граф при локальном изменении топологии фотошаблона. В третьей главе предложен такой метод, основанный на ДВ.

а ;«—.и gaas g

! Mil; р^И»

ЁЫшш

Рисунок 3 - Слева: построение граф« трассировки с номощмо сетки.

Справа: Граф пересечении каналов

Система глобальной трассировки и оценки суммарной длины соединений. Суммарная длина соединений является одним из критериев качества размещения схемы. Для быстрых её оценок в ранних САПР применялся метод полу периметра прямоугольника, охватывающего терминалы. 8 настоящее время используются более точные методы, в частности, основанные на глобальной трассировке, В последней рассматривается плоскость кристалла С терминалами, подлежащими соединению. Препятствия представляются многоугольными областями. Требуется получить приближённые оценки прохождения трасс. Для этого свободные участки описываются в виде плана - фа фа трассировки. Традиционные подходы, основанные на регулярных сетках, приводят к большим размерам графа (рисунок 3 слева). Хотя такие сетки предоставляют более точную информацию для детальной трассировки, при оценке длины соединений эта информация избыточна. Граф пересечения каналов (рисунок 2 справа) имеет меньший размер, однако не учитывает переменную ширину канала, перестающего быть прямоугольником на границе с многоугольными препятствиями, что встречается в размещении блоков современных заказных СБИС. Б ]ггерационных методах размещения необходимо заново оценивать длину соединений при локальных перемещениях блоков. Следовательно, востребован метод, динамически перестраивающий граф трассировки. В четвертой главе приводится метод построения графа с помощью ДВ, решающий данные проблемы.

□

Рисунок 4 - Преобразование фото шаблонного проводника и символьный

методом нарезки

Система преобразования топологии фотошаблона в символьную модель. Шаблонная модель состоит из наборов манхэттснских фигур в (фото)шаблонных слоях. Она удобна для использования на конечных стадиях проектирования (проверка, исправление, сжатие топологии). В символьной модели группам прямоугольников ставятся в соответствие символы, характеризующиеся координатами, размерами и функциональностью (транзистор, проводник и т.д.). Символьная модель удобна на начальных стадиях проектирования, для хранения и редактирования топологии, а также когда конкретные технологические параметры неизвестны или могут меняться. Востребованы эффективные методы преобразования моделей. Преобразование символьной топологии в шаблонную тривиально, к обратному существуют различные подходы. В данной работе рассматривается преобразование фотошаблонного проводника (многоугольника) в символьное представление (линии с назначенной шириной и соединённые в виде графа). Сегодня распространён метод нарезки многоугольника на прямоугольники, далее сужаемые до линий (рисунок 4). Очевидно, сама нарезка неоднозначна и возникает вопрос выбора вариантов. Затем, как видно из рисунка, восстановление направлений требует дополнительного анализа с целью получить связный граф, В изображённом примере потребовалось удлинение вертикального ребра и разделение горизонтальных на две части. Предлагаемый в пятой главе метод декомпозиции многоугольника на основе ДВ упрощает восстановление направлений и связности и построение искомого графа, а также является динамическим, ускоряя интерактивное преобразование топологии фотошаблона в символьную модель,

Вторал глава начинается рассмотрением различных определений ДВ, используемых в САПР (для сложных объектов, в разных метриках, взвешенные ДВ), и методов их вычисления. Проанализированы основные классы алгоритмов построения ДВ: «разделяй и властвуй», методы заметания плоскости, поднятие в трёхмерное пространство и

инкрементальные алгоритмы Развитием последних являются динамические алгоритмы, работающие с меняющимися во времени входными данными

Ввиду разнообразия способов задания ДВ решено обратиться к понятию абстрактной диаграммы Вороного (АДВ), введенному немецким математиком Р Кляйном в 1988 году, - аксиоматическому определению, обобщающему широкий класс конкретных видов ДВ, применяемых в САПР АДВ задается через систему биссектрис между абстрактными объектами — натуральными числами от 1 до и, удовлетворяющую определенным аксиомам Для каждой пары объектов р и д задана кривая линия - биссектриса Др,д)ь разделяющая области доминирования р над д — 0{р,д) и д над р — 0(д,р)

Здесь int - внутренность, а bd - граница множества VR(p,s) называется ячейкой Вороного объекта р, или р-ячейкой относительно множества объектов S, EVR(p,S) называется расширенной ячейкой Вороного объекта р относительно S V(S) называется абстрактной диаграммой Вороного множества объектов S Для удобства диаграмма ограничивается фиктивным объектом да с ячейкой, находящейся за достаточно большим контуром Г, и рассматривается конечная часть АДВ внутри Г (рисунок 5) Объекты, ячейки которых являются пустыми множествами, называются невидимыми АДВ хранит только топологическую информацию и представляется графом Координаты вершин и ребер определяются конкретной системой биссектрис

EVRtp.S) = р| R(p,q), VR(p,S) = mtTLVR(p,S),

V(S) = (JbdEVRC/vV)

Рисунок 5 - Ограшгеенная абстрактная диаграмма Вороного

Анализ существующих методов построения ДВ указывает на отсутствие динамического алгоритма построения АДВ, применимого к широкому классу конкретных диаграмм и эффективно оперирующего с удалением и вставкой объектов

Основной теоретический результат диссертационной работы — разработанный динамический алгоритм вычисления АДВ -универсальный инструмент для построения динамических графовых моделей в системах ТП на основе ДВ, не зависимый от вида объектов и отношения близости Любые локальные изменения во множестве исходных данных реализуются с помощью двух операций вставка и удаление абстрактного объекта Начальное построение реализуется путем последовательных вставок.

л / "" -----

\ взаимодействующие1

1 / рёбра| 1

1 '

I

граница

новой

ячейки

Рисунок 6 — Слева- процедура добавления объекта в АДВ Справа взаимодействующие с новой ячейкой ребра АДВ

Процедура вставки объекта и начальное построение реализуются известным алгоритмом Р Кляйна в три этапа (рисунок 6) Самым сложным по времени является первый этап Для оптимизации поиска используется специальный граф истории, запоминающий информацию о предыдущих вставках Оценка сложности процедуры вставки -О (log п) времени в среднем (при случайном выборе нового объекта), начального построения АДВ - 0{п log п), где п - количество добавленных объектов После начального построения граф истории не используется (для упрощения процедуры удаления) Поэтому сложность последующих вставок - 0{п) в худшем случае (поиск взаимодействующих ребер полным перебором)

Процедура удаления объекта из АДВ Доказанная теорема говорит о том, что при удалении объекта изменения в АДВ определяются только множеством его соседних и невидимых объектов, и является основным

теоретическим результатом, позволяющим построить эффективный динамический алгоритм

Теорема 1. Пусть Л - множество объектов, N<^71 - множество соседей в е Я, 5 Ф оо, / - множество невидимых объектов в Л Тогда У(Л \{.9})п VR.Cs, Л) = У(ЛГ и /) п VR.Cs, Л^ и I и {5})

о .¡ссча 1 I 7Г

Рисунок 7 - Слева: процедура удаления объекта из АДВ Справа сцепление оставшейся части АДВ после удаления ячейки и АДВ* (для соседних и невидимых объектов)

Случай удаления невидимого объекта из АДВ тривиален В остальных случаях процедура состоит из четырех основных этапов, проиллюстрированных на рисунке 7 Теоретическая оценка сложности процедуры удаления - 0(m log п) в среднем (при случайности выбора удаляемого объекта), где т - число невидимых объектов на текущей АДВ Если невидимые объекты не разрешены (что обычно бывает на практике), то средняя оценка сложности - O(log п)

Базовая операция динамического алгоритма построения АДВ - это единственная операция в процедурах вставки и удаления, которую необходимо реализовать в практическом приложении в соответствии с конкретным выбранным определением системы биссектрис Абстрактный алгоритм оперирует с топологическими вычислениями, геометрические (пересечение кривых и тд) должны выполняться в базовой операции Она устанавливает топологический вид пересечения

ребра АДВ, определяемого четырьмя смежными объектами, с ячейкой пятого (нового) объекта. Возможны следующие виды (рисунок 8):

1) пересечение пустое;

2) пересечение непустое и связное:

2а) ребро целиком;

26) отрезок ребра, инцидентный первому концу; 2в) отрезок ребра, инцидентный второму концу; 2г) отрезок ребра, не инцидентный ни одному из концов;

3) две связные компоненты, инцидентные концам ребра,

К базовой операции предъявляется требование: время выполнения должно быть 0(1), т.е. константным.

возможные ситуации пересечения ребра с ячейкой невозможная

ситуация

Рисунок 8 - Виды пересечения ребра Вороного с ячейкой нового объекта

Итак, представлен динамический алгоритм построения АДВ, позволяющий обрабатывать удаления и вставки объектов эффективнее, чем построение с нуля: 0{п) вместо 0(п log я), Оценка практического ускорения: от 5-10 раз до 2040 раз при размерах входных данных от 100 до i ООО ООО объектов. Алгоритм затрачивает оптимальный размер памяти 0(п). Любые локальные изменения во множестве входных данных реализуются с помощью удаления объекта с последующей вставкой. Так на практике можно реализовать перемещение и деформацию объектов. Алгоритм оперирует исключительно с топологическими вычислениями. Для конкретного определения ДВ необходимо реализовать одну базовую операцию.

Динамический алгоритм используется в трех предлагаемых далее независимых методах построения динамических графовых моделей, используемых в системах ТП СБИС.

Третья глава посвящена разработке метода построения графа ограничений с -использованием диаграмм Вороного в системах проверки правильности, исправления и сжатия топологии интегральных схем, ДВ специального вида применяется для построения фа фа горизонтальных (вертикальных) ограничений, моде лиру ющих одномерные технологические правила размещения элементов топологии фото шаблона. ДВ строится для вертикальных (горизонтальных)

отрезков - сторон многоугольников таким образом, чтобы она отражала отношение горизонтальной (вертикальной) видимости между объектами-отрезками Тогда ребра графа ограничений напрямую соответствуют ребрам ДВ

Диаграмма Вороного специального вида является частным случаем АДВ Рассмотрим ДВ для вертикальных отрезков Система биссектрис задается на основе специальной функции расстояния от точки и с координатами (хиуи) до объекта-отрезка р с координатами концов (хрур]) И (хряуРз)

I хи-хр I, уи е [ур„ур2],

Затем определение уточняется, чтобы биссектрисы удовлетворяли аксиомам АДВ В окончательном варианте биссектриса состоит из одного вертикального отрезка и двух лучей, как изображено на рисунке 9 Координаты вертикального отрезка ха =(х1+х2)Л, ув = тах{у1В,у2В}, уТ = тт{у1Т,у2Т} Направления горизонтальных

d(u,p) =

лучей хв = i , хт

-«\У1в>Угв

-оо,у1Т <у2Т + оо, у1Т > у1Т

у2т У it---

У2В У ¡в

Ут

Ув

Хт Xi Хо Х2 Хв

Рисунок 9 - Специальное определение биссектрисы вертикальных отрезков

ДВ специального вида (рисунок 10) вычисляется представленным выше динамическим алгоритмом, для чего реализована базовая операция алгоритма применительно к данной ДВ и исследованы варианты построения биссектрис Предложенный метод позволяет строить граф ограничений за ожидаемое время 0(п log п) с использованием 0(п) памяти, что сравнимо с лучшими известными методами При этом граф с п вершинами имеет асимптотически оптимальный размер - 0{п) В отличие от стандартных методов построения графа ограничений, предложенный метод обрабатывает локальные изменения топологии фотошаблона быстрее, чем построение

графа с куля - за время 0(п) в худшем случае. Благодаря этому он имеет преимущества в системах интерактивной проверки правильности топологии, итерационных методах полуторамерного сжатия и исправления (когда в результате локальных изменений топологии в ортогональном направлении необходимо перестраивать граф ограничений для повторного сжатия/исправления в основном направлении).

Рисунок 10 - ДВ для вертикальных отрезков и рёбра графа ограничений;

сверху: ограничения ширины и расстояния в одном слое, снизу: ограничения расстояния, перекрытия и включения в дну* слоях

Четвертая глава посвящена разработке метода построения планировочного графа на основе диаграммы Вороного в системе глобальной трассировки и оценки суммарной длины соединений. ДВ в метрике Ь„ вычисляется для горизонтальных и вертикальных отрезков -сторон фигур-препятствий. ДВ для сторон содержит в себе ДВ для самих фигур и дополнительные рёбра, которые используются для вывода терминалов (рисунок 11 слева). После удаления лишних вершин и ребер получаем плоский граф — план трассировки (рисунок 11 справа), который можно ещё редуцировать, если нас не интересуют конкретное прохождение трасс, а только их длины. С каждым ребром графа связаны длина, определяемая в метрике Манхзтгена и пропускная способность, определяемая как удвоенное наименьшее из расстоянии от концов ребра до разделяемых им препятствий.

Рисунок 11 - Слева: ДВ для сторон фигур с выведенными терхншалами.

Справа- план трассировки на основе ДВ

Используемая ДВ является частным случаем АДВ С применением предложенного выше динамического алгоритма построения АДВ средняя сложность построения графа трассировки - 0(п log ri) -является приемлемой и не превышает сложности самих алгоритмов трассировки Преимущество подхода в том, что граф на основе ДВ более адекватно представляет свободные участки схемы, чем граф пересечения каналов С другой стороны, граф на основе ДВ имеет меньший размер по сравнению с сеточными графами, что ускоряет трассировку В отличие от подхода, опубликованного на конференции ISPD'06 (Feng Z et al) и применяющего ДВ, предлагаемый здесь подход учитывает пропускные способности свободных участков топологии, что значительно повышает трассируемость всех цепей схемы Наконец, метод является динамическим и позволяет локально перестраивать граф быстрее - за время 0(п)

В пятой главе предлагается метод декомпозиции маихэттенского многоугольника на основе диаграммы Вороного в системе преобразования топологии фотошаблона в символьную модель, заключающийся в следующем Вычисляется ДВ в метрике для горизонтальных и вертикальных отрезков - сторон многоугольника, которая удовлетворяет аксиомам АДВ Затем из нее вычленяется ядро Вороного - множество вершин, горизонтальных и вертикальных участков ДВ во внутренней области многоугольника, как показано на рисунке 12 Доказанная теорема говорит о том, что манхэттенский многоугольник совпадает с покрытием прямоугольниками, описанными около отрезков его ядра Вороного Очевиден простой и естественный метод декомпозиции многоугольника на прямоугольники, направление и связность которых восстанавливаются из ДВ и адекватны топологии многоугольника (рисунок 13)

Рисунок 12 - Диаграмма Вороного для внутренности многоугольника и ядро Вороного (толстые линии)

Рисунок 13 - Декомпозиция манхэттенского многоугольника на связанные прямоугольники, построенные из ядра Вороного

В отличие от традиционных методов нарезки многоугольника на прямоугольники, предлагаемая декомпозиция однозначная и естественным образом соответствует требованиям символьной модели топологии. При этом отпадает необходимость дополнительного анализа направлений и связности: направление соответствует соотношению длины и ширины прямоугольника, а связность определяет ДВ, Применение предложенного выше динамического алгоритма построения АДВ позволяет более эффективно обрабатывать локальную деформацию многоугольника, затрачивая максимум 0(п) времени на локальное обновление декомпозиции вместо 0(п log п) времени на полное перестроение.

В заключении приведены основные теоретические и практические результаты, полученные в ходе выполнения диссертационной работы.

1. Анализ графовых моделей в математическом и программном обеспечении систем топологического проектирования (ТП) СБИС показал целесообразность использования диаграмм Вороного (ДВ) для комплексного решения проблем качества, избыточности, эффективности построения и динамического обновления моделей,

2. На основе ДВ разработаны динамические методы построения графовых моделей в трёх независимых системах ТП, позволившие ускорить локальное обновление моделей; О(п) времени вместо 0(n log п) для полного перестроения. Методы востребованы в итерационных й интерактивных системах анализа и оптимизации топологии.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

• Метод построения графа ограничений в системах проверки, исправления и сжатия топологии ИС, состоящей из произвольных манхэттенских фигур

• Метод построения планировочного графа в системе глобальной трассировки и оценки суммарной длины соединений приводит к меньшей избыточности, чем сеточные графы, и большей точности, чем граф пересечения каналов, что существенно для трассировки заказных СБИС

• Метод декомпозиции манхэтгенского многоугольника в системе преобразования топологии фотошаблона в символьную модель, в отличие от метода нарезки, упрощает восстановление направлений и связности элементов

3 Разработан динамический алгоритм вычисления абстрактной ДВ — универсальный инструмент, лежащий в основе методов построения графовых моделей ТП

• Доказана теорема об эффективном удалении объекта из АДВ, вносящая вклад в теорию вычислений и обработки геометрических данных

• В отличие от известных, динамический алгоритм вычисления АДВ более эффективно перестраивает диаграмму при любых локальных изменениях входных данных 0(п) времени по сравнению с 0(n log п) для полного построения. На практике это дает оценочное ускорение от 5-10 раз до 20-40 раз при размерах входных данных от 100 до 1 000 000 объектов

• Затрачиваемая память имеет размер 0(п), как и сама ДВ, что нередко решает проблему избыточности данных

• В отличие от существующих динамических алгоритмов, универсальный алгоритм работает с широким классом ДВ

• Реализация алгоритма в виде отдельного программного модуля для включения в библиотеку геометрического программного обеспечения позволяет повторно применять его в системах ТП, использующих ДВ разного рода, уменьшив таким образом общий объем программного кода

4 Метод преобразования фотошаблонного представления проводника в символьное внедрен в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О» При работе на топологии уровня функциональных блоков (порядка 104 транзисторов) метод позволил однозначным образом

осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в 1015 раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1 5-2 8 раз

5 Результаты диссертации внедрены в учебный процесс в МФТИ на базовой кафедре Интела в курсе «Математические основы САПР»

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

1 Малинаускас К К Алгоритм построения диаграмм Вороного для решения задач топологического анализа II Микроэлектроника и информатика - 2003 10-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов Тезисы докладов -М МИЭТ, 2003 -С 163

2 Малинаускас К К, Марченко А М Применение диаграмм Вороного для оценки качества трассировки в задаче размещения модулей СБИС // Труды конференций «Интеллектуальные системы (IEEE AIS'03) и «Интеллектуальные САПР» (CAD-2003) М Изд-во Физ-мат лит, 2003 -Т2-С 70-74

3 Малинаускас К К Декрементный алгоритм построения диаграмм Вороного для решения задач топологического анализа // Микроэлектроника и информатика - 2004 11-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов Тезисы докладов -М МИЭТ, 2004 - С 187

4 Малинаускас К К Динамический алгоритм построения диаграмм Вороного для использования в задачах топологического анализа интегральных микросхем // Материалы VIII международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г) - М Изд-во механико-математического факультета МГУ, 2004 - С 283-284

5 Malinauskas К К, Marchenko А М, Zmchenko А V Voronoi Diagrams m Leo metacs and Application in Mask to Symbolic Layout Conversion // In Proc of International Science Conference "Intelligent Systems (IEEE AIS-05)" and "Intelligent CAD's (CAD-2005)", 2005 - Vol 3 -P 69-74

6 Малинаускас К.К, Кожухов И Б , Ревякин А М Алгоритмы поиска кратчайших путей в графе // Математические методы и приложения труды пятнадцатых математических чтений РГСУ (28-31 января 2006 года) - М Изд-во РГСУ, 2006 - С 147-167

7 Малинаускас К К Обзор алгоритмов поиска кратчайших путей в задачах сжатия топологии ИС // Известия вузов Электроника, 2006, №6 - С 36-55

8 Малинаускас К К Динамическое построение абстрактных диаграмм Вороного // Фундаментальная и прикладная математика, 2007, том 13, № 2 - С 133-146

9 Малинаускас К К Метод построения графа ограничений в задачах сжатия и корректировки топологии интегральных схем // Микроэлектроника и информатика — 2007 14-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов Тезисы докладов - М МИЭТ, 2007 - С 156

10 Малинаускас К К Специальная диаграмма Вороного для построения графа ограничений в задачах топологического проектирования СБИС // Известия вузов Электроника, 2007, №3 -С 36-42

Подписано в печать

Заказ Тираж /¿О экз Уч-издл ^ / Формат 60x84 1/16

Отпечатано в типографии МИЭТ (ТУ) 103498, Москва, МИЭТ (ТУ)

Введение

Глава 1. Проблемы математического и программного обеспечения топологического проектирования СБИС

1.1. Тенденции развития математических и программных средств автоматизации топологического проектирования

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

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

1.4. Выводы

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

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

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

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

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. Выводы

С усложнением процессов производства интегральных схем, переходом на нанометровые технологии и увеличением степени интеграции растёт внимание к средствам автоматизации топологического проектирования (ТП) СБИС. Системы ТП решают задачи синтеза топологии ИС и включают программные средства для размещения элементов схемы, глобальной и детальной трассировки соединений, анализа и оптимизации топологии по различным критериям. Вклад в развитие систем ТП внесли ряд отечественных и зарубежных авторов: Г.Г. Казённое, В.М. Щемелинин, В.А. Селютин, Б.В. Баталов, Г.Э. Широ, A.M. Марченко, В.Е. Вулихман, А.В. Жмурин, Н. Шервани, М. Ласло, А.Б. Канг, Е. Пападопуло и др. Математический базис, используемый в отрасли, можно найти в трудах М. Шеймоса, Ф. Препараты, А. Фокса, K.JI. Кларксона, П.В. Шора, Р. Кляйна, Ф. Ауренхаммера, С. Фотьюна и др.

В данной работе рассматриваются вопросы построения специализированных графовых моделей в системах ТП, востребованных при описании отношений и связей между элементами топологии. Здесь приходится сталкиваться со следующими проблемами. Адекватность моделей предметной области - один из главных факторов, определяющий качество систем и процент выхода годных микросхем. Уменьшение избыточности и размеров данных важно для оптимизации использования памяти и ускорения обработки данных. Эффективность алгоритмов построения моделей - требование, обусловленное q постоянно растущей степенью интеграции (более 10 транзисторов). Эффективность динамического обновления моделей особенно важна с возрастанием числа обратных связей в маршрутах проектирования, распространением итерационных методов оптимизации и интерактивного редактирования топологии. В интерактивной системе человек ожидает быстрой реакции на свои действия, в итерационном методе многократные локальные корректировки топологии должны быть быстро отражены в используемых моделях.

Для комплексного решения перечисленных проблем в настоящей работе предлагается использование моделей, основанных на диаграммах Вороного. Классической диаграммой Вороного (ДВ) для точечных объектов называется разбиение плоскости на ячейки, каждая из которых есть локус точек, расположенных ближе к одному из объектов в метрике Евклида, чем к остальным. Известны модификации данного определения: для сложных объектов (отрезков, фигур и др.), в различных метриках и т.д. ДВ является плоским графом, рёбра которого суть участки средних линий между объектами. Идея использования ДВ в математическом и программном обеспечении систем ТП не является новой. Как удобный инструмент решения ряда геометрических задач, ДВ уже нашла применение в САПР, помогая строить адекватные графовые модели с относительно малыми затратами времени и памяти [ 19] [31 ] [43 ] [76] [77]. Так, известны примеры использования в системах оценки выхода годных и начального размещения.

Использование ДВ может также повысить качество и уменьшить избыточность графовых моделей в системах глобальной трассировки, проверки, исправления, сжатия и преобразования топологии СБИС. Т.е., актуальным представляется расширение области применения ДВ в математическом и программном обеспечении систем ТП, где востребованы эффективные средства представления информации о взаимном расположении элементов топологии СБИС в виде плоских графов. Существуют эффективные динамические алгоритмы построения ДВ, перестраивающие её локально быстрее, чем с нуля. Несмотря на это, до сих пор динамические диаграммы не использовались в САПР. Поэтому актуальным становится использование преимуществ динамического построения ДВ в интерактивных системах ТП, а также в итерационных методах локальной оптимизации топологии. Однако известные динамические алгоритмы применимы только к конкретным определениям ДВ, т.е. не являются универсальными. Поэтому актуальна разработка универсального динамического алгоритма построения диаграмм Вороного разного рода, используемых в САПР. Исходя из этого, решено обратиться к концепции абстрактной диаграммы Вороного (АДВ), обобщающей широкий класс ДВ.

Цель диссертационной работы заключается в разработке эффективных динамических моделей, алгоритмов и программных средств на основе абстрактной диаграммы Вороного для использования в системах TTI СБИС. Для достижения поставленной цели автором поставлены и решены следующие задачи:

• разработка метода построения графа ограничений на основе ДВ в системах проверки, исправления и сжатия топологии СБИС;

• разработка метода построения планировочного графа на основе ДВ в системе глобальной трассировки и оценки суммарной длины соединений СБИС;

• разработка метода декомпозиции манхэттенского многоугольника на основе ДВ в системе преобразования топологии фотошаблона в символьное представление.

• разработка динамического алгоритма построения АДВ, теоретическое обоснование его корректности и эффективности;

• реализация метода декомпозиции многоугольника и его внедрение в программный комплекс оптимизации топологии СБИС, эксплуатируемый в компании Интел.

Методы исследования базируются на фундаментальных положениях теории алгоритмов и вычислительной сложности, аналитической и вычислительной геометрии, общей топологии, правилах построения программного обеспечения, а также на принципах проектирования топологии интегральных схем.

Научная новизна состоит в разработке моделей, методов и алгоритмов, вносящих вклад в развитие математической теории вычислений и обработки геометрических данных, и позволяющих повысить качество и эффективность систем ТП. В ходе выполнения диссертационной работы получен ряд научных результатов, на данный момент не имеющих аналогов.

1. Доказана теорема об эффективном удалении объекта и разработан динамический алгоритм вычисления АДВ - универсальный инструмент, повышающий эффективность различных методов ТП.

2. Доказано, что граф ограничений, используемый в задачах проверки, исправления и сжатия топологии является двойственным к ДВ специального вида. Этот факт лёг в основу динамического метода построения графа ограничений.

3. Показана целесообразность использования ДВ в метрике L,„ для построения планировочного графа в задачах глобальной трассировки и оценки суммарной длины соединений.

4. Доказаны специальные свойства ядра Вороного в метрике L®, позволившие построить динамический метод декомпозиции многоугольника в задаче преобразования топологии фотошаблона в символьное представление.

Практическая значимость работы заключается в расширении интеллектуальных возможностей вычислительных систем ТП СБИС за счёт использования АДВ и динамического алгоритма её построения. Комплексно решаются проблемы быстродействия, качества и избыточности используемых графовых моделей в системах проверки, исправления и сжатия топологии, глобальной трассировки и оценки суммарной длины соединений СБИС, преобразования топологии. Для построения трёх независимых графовых моделей впервые предложены динамические методы на основе АДВ. Динамический алгоритм вычисления АДВ даёт выигрыш во времени локального обновления графовых моделей относительно полного перестроения: 0(п) по сравнению с 0(п log п) времени, где п - размер входных данных. Оценочное ускорение - от 5-10 раз до 20-40 раз при размерах входных данных от 100 до 1 000 000 объектов. Алгоритм востребован в интерактивных системах редактирования и итерационных методах оптимизации топологии. Его программная реализация в виде модуля удобна для включения в библиотеку геометрического программного обеспечения и независимого повторного использования при построении моделей на основе ДВ разного рода. Это позволяет унифицировать программный код и сократить его объём.

Достоверность научных положений и выводов, полученных соискателем, подтверждается теоретическими выкладками и успешным промышленным внедрением.

Личный вклад автора. Все основные результаты получены автором лично. Постановка задачи выполнена совместно с научным руководителем. Автор принимал активное участие в разработке архитектуры, реализации, документации и тестировании программного обеспечения, внедрённого в ЗАО «Интел А/О».

Внедрение результатов работы. Метод преобразования фотошаблонного представления проводника в символьное внедрён в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О». При работе на символьной топологии уровня функциональных блоков (порядка 104 транзисторов) метод позволил однозначным образом осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в 10-15 раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1.5-2.8 раз. Результаты диссертации внедрены в учебный процесс МФТИ на базовой кафедре Интела в курсе «Математические основы САПР».

На защиту выносятся:

1) метод построения графа ограничений на основе ДВ;

2) метод построения графа глобальной трассировки на основе ДВ;

3) метод декомпозиции фотошаблонного проводника на основе ДВ;

4) динамический алгоритм вычисления АДВ, лежащий в основе предложенных методов;

5) результаты промышленного внедрения.

Апробация результатов работы проводилась на конференциях и семинарах: Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2003, 2004, 2007 гг., 3 доклада); Международная научно-техническая конференция «Интеллектуальные САПР» (Дивноморское, 2003, 2005 гг., 2 доклада); Международный семинар «Дискретная математика и её приложения» (Москва, МГУ, 2004 г., 1 доклад); Математические методы и приложения: пятнадцатые математические чтения РГСУ (Руза, 2006 г., 1 доклад); семинар «Геометрия и дискретный анализ» (Москва, Мехмат МГУ, каф. МаТИС, 2007 г., 1 доклад). Доклады на конференции «Микроэлектроника и информатика» в 2003 и 2007 годах отмечены дипломами 1-ой степени в секции «Математические модели и алгоритмы в информатике».

Публикации. Результаты диссертации отражены в трёх статьях [8][10][11] и семи тезисах докладов [4][5][6][7][9][12][69].

Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 75 позиций. Работа содержит 115 стр., 1 акт о внедрении в производство и 1 акт о внедрении в учебный процесс.

5.5. Выводы

Предложен метод декомпозиции манхэттенского многоугольника в задаче преобразования топологии фотошаблона в символьную модель на основе диаграммы Вороного для отрезков в метрике Lx.

• В отличие от существующих декомпозиций, предложенная декомпозиция является детерминированной.

• В отличие от существующих декомпозиций, декомпозиция на основе диаграммы Вороного естественным образом отображает топологию многоугольника, представляет собой интуитивно понятную символьную цепь и не требует дополнительного анализа связности и ориентации её элементов.

• В отличие от существующих методов декомпозиции, предложенный метод является динамическим: он позволяет перестраивать декомпозицию при локальных деформациях многоугольника более эффективно, чем построение с нуля.

• Обоснованы корректность и эффективность метода. Доказанная теорема о декомпозиции раскрывает свойства ядра Вороного и имеет ценность как отдельный математический результат.

Заключение

Настоящая диссертационная работа посвящена исследованию в области проектирования и анализа алгоритмов вычислительной геометрии и их приложению в математическом и программном обеспечении вычислительных систем топологического проектирования СБИС. Предметом исследования является вопрос построения разного рода диаграмм Вороного - инструментов для решения множества фундаментальных и прикладных задач геометрической природы или интерпретации. Перечислим основные выводы и результаты работы.

1. Анализ графовых моделей в математическом и программном обеспечении систем топологического проектирования (ТП) СБИС показал целесообразность использования диаграмм Вороного (ДВ) для комплексного решения проблем качества, избыточности, эффективности построения и динамического обновления моделей.

2. На основе ДВ разработаны динамические методы построения графовых моделей в трёх независимых системах ТП, позволившие ускорить локальное обновление моделей: О(п) времени вместо 0(nlogn) для полного перестроения. Методы востребованы в итерационных и интерактивных системах анализа и оптимизации топологии.

• Метод построения графа ограничений в системах проверки, исправления и сжатия топологии ИС, состоящей из произвольных манхэттенских фигур.

• Метод построения планировочного графа в системе глобальной трассировки и оценки суммарной длины соединений приводит к меньшей избыточности, чем сеточные графы, и большей точности, чем граф пересечения каналов, что существенно для трассировки заказных СБИС.

• Метод декомпозиции маихэттеиского многоугольника в системе преобразования топологии фотошаблона в символьную модель, в отличие от метода нарезки, упрощает восстановление направлений и связности элементов.

Разработан динамический алгоритм вычисления абстрактной ДВ -универсальный инструмент, лежащий в основе методов построения графовых моделей ТП.

• Доказана теорема об эффективном удалении объекта из АДВ, вносящая вклад в теорию вычислений и обработки геометрических данных.

• В отличие от известных, динамический алгоритм вычисления АДВ более эффективно перестраивает диаграмму при любых локальных изменениях входных данных: 0(п) времени по сравнению с 0(n log п) для полного построения. На практике это даёт оценочное ускорение от 5-10 раз до 20-40 раз при размерах входных данных от 100 до 1 000 000 объектов.

• Затрачиваемая память имеет размер О(п), как и сама ДВ, что нередко решает проблему избыточности данных.

• В отличие от существующих динамических алгоритмов, универсальный алгоритм работает с широким классом ДВ.

• Реализация алгоритма в виде отдельного программного модуля для включения в библиотеку геометрического программного обеспечения позволяет повторно применять его в системах ТП, использующих ДВ разного рода, уменьшив таким образом общий объём программного кода.

Метод преобразования фотошаблонного представления проводника в символьное внедрён в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О». При работе на топологии уровня функциональных блоков (порядка 104 транзисторов) метод позволил однозначным образом осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в 10-15 раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1.52.8 раз.

5. Результаты диссертации внедрены в учебный процесс в МФТИ на базовой кафедре Интела в курсе «Математические основы САПР».

1. Казёнов Г.Г., Щемелинин В.М. Автоматизация проектирования БИС: В 6-ти кн. Кн. 4: Топологическое проектирования нерегулярных БИС. М.: Высшая школа.-1990.-110 с.

2. Келли Дж. Общая топология: Пер. с англ. 2-е изд. - М.: Наука, 1981. -432 с.

3. Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: «Издательство БИНОМ», 1997. - 304 е.

4. Малинаускас К.К, Кожухов И.Б., Ревякин A.M. Алгоритмы поиска кратчайших путей в графе. // Математические методы и приложения: труды пятнадцатых математических чтений РГСУ (28-31 января 2006 года). М.: Изд-во РГСУ, 2006. - С. 147-167.

5. Малинаускас К.К. Динамическое построение абстрактных диаграмм Вороного. // Фундаментальная и прикладная математика, 2007, том 13, № 2. -С.141-154.

6. Малинаускас К.К. Обзор алгоритмов поиска кратчайших путей в задачах сжатия топологии ИС. // Известия вузов. Электроника, 2006, № 6. С. 36-55.

7. Малинаускас К.К. Специальная диаграмма Вороного для построения графа ограничений в задачах топологического проектирования СБИС. // Известия вузов. Электроника, 2007, № 3. С. 24-31.

8. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.-478 с.

9. Селютин В.А. Автоматизированное проектирование топологии БИС. -М.: Радио и связь. 1983. - 112 с.

10. Сотников М.А. Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС: Дисс. канд. техн. наук. ЗАО «Моторола ЗАО», Москва, 2004. 119 с.

11. Томас Ф., Иванов А. САПР микроэлектроники. Этапы большого пути. // Электроника: наука, технология бизнес, № 3'2006. 2006. - С. 82-85.

12. Шепелев В.А., Стемпковский A.JI. Организация системной среды для построения открытых САПР СБИС. М.: МИЭТ. - 1999. - 116 с.

13. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве: пер. с англ. М.: Мир. - 1982. - 304 с.

14. Щемелинин В.М. Автоматизация топологического проектирования. М.: МИЭТ.-2001.- 132 с.

15. Aichholzer О., Aurenhammer F. Voronoi diagrams computational geometry's favorite // Special issue of Foundations of Information Processing of TELEMATIK. - 2002. - Vol. 1. - P. 7-11.

16. Aurenhammer F., Klein R. Voronoi diagrams. // In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry, Chapter V. Elsevier Science Publishing, 2000. P. 201-290.

17. Aurenhammer F. Voronoi diagrams a survey of a fundamental geometric data structure // ACM Computing Surveys. - 1991. - Vol. 23. - No. 3. - P. 345-405.

18. Blelloch G., Miller G.L., Talmor D. Developing a practical projection-based parallel Delaunay algorithm. // In Proc. 12th Annual ACM Symposium on Computational Geometry. 1996. - P. 186-195.

19. Boissonnat J.-D., Teillaud M. On the randomized construction of the Delaunay tree. // Theoretical Computer Science. 1993. - Vol. 112. - P. 339-354.

20. Bonapace C.R., Lo C.-Y. An 0(n log m) algorithm for VLSI design rule checking. // IEEE Transactions on Computer-Aided Design. 1992. - Vol. 11.- No. 6.-P. 753-758.

21. Brumberger H., Goodisman J. Voronoi cells: an interesting and potentially useful cell model for interpreting the small angle scattering of catalysts. // Journal of Applied Crystallography. 1983. - Vol. 16. - P. 83-88.

22. Carabelas M.I., Yvinec M. Dynamic additively weighted Voronoi diagrams in 2D. // Lecture Notes in Computer Science. 2002. - Vol. 2461. - P. 586-598.

23. Carpenter C.W., Horowitz M. Generating incremental VLSI compactionthspacing constraints. // In Proc. of 24 ACM/IEEE Design Automation Conference. -1987.-P. 291-297.

24. Cho Y.E. A subjective review of compaction // In Proc. of 22nd IEEE Design Automation Conference. 1985. - P. 396-404.

25. Choi S.-G., Kyung C.-M. A floorplanning algorithm using rectangular Voronoi diagram and force-directed block shaping. // In Proc. of IEEE International Conference on Computer-Aided Design, 1991. Santa Clara, CA, USA, 1991. P. 5659.

26. Clarkson K.L., Mehlhorn K., Seidel R. Four results on randomized incremental constructions. // Computational Geometry: Theory and Applications. 1993. - Vol. 3.-P. 185-212.

27. Clarkson K.L., Shor P.W. Applications of random sampling in computational geometry, II. // Discrete Computational Geometry. 1989. - Vol. 4. - P. 387-421.

28. Cong J., Fang J., Khoo K.-Y. DUNE a multi-layer gridless routing system with wire planning. // In Proc. of ISPD'2000. - 2000. - San Diego, CA. - P. 12-18.

29. Cong J., Sarrafzadeh M. Incremental physical design. // Proc. of the 2000 International Symposium on Physical Design. 2000. - San Diego, CA. - P. 84-92.

30. Dehne F., Klein R. "The big sweep": on the power of the wavefront approach to Voronoi diagrams. // Algorithmica. 1997. - Vol. 17. - P. 19-32.

31. Descartes R. Principia Philosophiae. Ludovicus Elzevirius. Amsterdam, 1644.

32. Devillers O., Meiser S. Teillaud M. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. // Computational Geometry: Theory and Applications. -1992. Vol. 2. - P. 55-80.

33. Diaz-Banes J.M., Gomez F., Ventura I. The anchored Voronoi diagram: static, dynamic versions and applications. // International Journal on Computational Geometry and Applications. 2006. - Vol. 16. - No. 4. - P. 315-332.

34. Dirichlet G.L. Uber die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. // Journal fur die reine und angewandte Mathematik. -1850.-T. 40.- S. 209-227.

35. Dwyer R.A. A faster divide-and-conquer algorithm for constructing Delaunay triangulations. // Algorithmica. 1987. - Vol. 2. - P. 137-151.

36. Fang J., Wong J.S.L., Zhang K., Tang P. A fast constraint graph based compactor for VLSI circuit layouts // In Proc. of International Conference on Circuits and Systems. 1991. - P. 628-631.

37. Feng Z. et al. An 0(n log n) algorithm for obstacle-avoiding routing tree construction in the X-geometry plane. // In Proc. of ISPD'06. San Jose, С A, USA, 2006.-P. 48-55.

38. Fortune S. Voronoi diagrams and Delaunay triangulations. // In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, vol. 1 of Lecture Notes Series on Computing, pp. 193-233. World Scientific, Singapore, 1st edition, 1992.

39. Fortune S J. A sweepline algorithm for Voronoi diagrams. // Algorithmica. -1987.-Vol. 2.-P. 153-174.

40. Gavrilova M.L., Rokne J. Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean (/-dimensional space. // Computer Aided Geometric Design. 2003. - Vol. 20, P. 231-242.

41. Gold C.M., Remmele P.R., Roos T. Fully dynamic and kinematic Voronoi diagrams in GIS. // Algorithmica. Special Issue on Cartography and GIS. - 1999. -20 p.

42. Gowda I.G., Kirkpatrick D.G., Lee D.T. A. Naamad. Dynamic Voronoi diagrams. // In IEEE Transactions on Information Theory. 1983. - Vol. 29. - No. 5. -P. 724-731.

43. Green P.J., Sibson R.R. Computing Dirichlet tessellations in the plane. // The Computer Journal. 1978.-Vol. 21.-P. 168-173.

44. Guibas L.J. Mitchell J.S.B., Roos T. Voronoi diagrams of moving points in thethplane. // In Proc. of 17 International Workshop Graph-Theoretic Concepts in Computer Science, Vol. 570 of Lecture Notes in Computer Science, 1992. P. 113— 125.

45. Guibas L.J., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. // ACM Transactions on Graphics. -1985. Vol. 4. - No. 2. - P. 74-123.

46. Held M. Voronoi Diagrams and Offset Curves of Curvilinear Polygons. // Computer-Aided design. 1998. - Vol. 30. - No. 4. - P. 287-300.

47. Heng F.-L., Chen Zh., Tellez G.E. A VLSI artwork legalization technique based on a new criterion of minimum layout perturbation // In Proc. of ISPD'97. -1997.-P. 116-121.

48. Huttenlocher D.P., Kedem K., Kleinberg J.M. On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane. // In Proc. of 8th Annual ACM Symposium on Computational Geometry.1992.-Vol. 6.-P. 110-119.

49. Jungkrajarng N. et al. IPRAIL — intellectual property reuse-based analog 1С layout automation. // Integration, the VLSI journal. 2003. - Vol. 36. - P. 237-262.

50. Kahng A.B., Robins G. On optimal interconnections for VLSI. Kluwer Academic Publishers, 1994. 304 p.

51. Katajainen J., Koppinen M. Constructing Delaunay triangulations by merging buckets in quadtree order. // Annales Societatis Mathematicae Polonae, Series IV, Fundamenta Informaticae. 1988. - Vol. 11. - No. 3. - P. 275-288.

52. Kim C.-M. et al. Interaction interfaces in proteins via the Voronoi diagram of atoms. // Computer-Aided Design. 2006. - Vol. 38. - P. 1192-1204.

53. Kirkpatrick D. Efficient Computation of Continuous Skeletons. // Proceedings of the 20th Annual Symposium on Foundations of Computer Science. 1979. - P. 18-27.-194 p.

54. Klein R. Abstract Voronoi diagrams and their applications (extended abstract). In H. Noltemeier, ed. // Proc. of the Workshop on Computational Geometry and its Applications, Wiirzburg, Lecture Notes in Computer Science 333, 1988. P. 148157.

55. Klein R. Concrete and abstract Voronoi diagrams. Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1989. - Vol. 400. - 167 p.

56. Klein R., Mehlhorn K., Meiser S. Randomized incremental construction of abstract Voronoi diagrams. // Computational Geometry: Theory and Applications.1993.-Vol. З.-No. 3.-pp. 157-184.

57. Klein R., Mehlhorn K., Meiser S. Randomized incremental construction of abstract Voronoi diagrams. // Computational Geometry: Theory and Applications. -1993.-Vol.3.-P. 157-184.

58. Kuh E.S., Ohtsuki T. Recent advances in VLSI layout. // Proc. of the IEEE. -1990. Vol. 78, № 2. - P. 237-263.

59. Lee D.T., Wong C.K. Voronoi diagrams in the L( (L») metrics with 2-dimensional storage applications. // SIAM Journal on Computing. 1980. - Vol. 9. -P. 200-211.

60. Lee D.T., Drysdale R.L. Generalization of Voronoi diagrams in the plane. // SIAM Journal on Computing. 1981. - Vol. 10. - P. 73-87.

61. Lee J.-F. A new framework of design rules for compaction of VLSI layouts. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. -1988.-Vo. 7. No. 11.-P. 1195-1204.

62. Li J.-Y., Li Y.-L. An efficient tile-based ECO router with routing graph reduction and enhanced global routing flow. // In Proc. of ISPD'05. 2005. - P. 713.

63. Mayya N. and Rajan V.T. An Efficient Shape-Representation Scheme Using Voronoi Skeletons. // Pattern Recognition Letters. 1995. - Vol. 16. - No. 2. - P. 147-160.

64. Mercier F. and Baujard O. Voronoi diagrams to model forest dynamics in French Guiana. // In Proceedings of GeoComputation'97 & Sirc'97. University of Otago, New Zeeland. - 1997. - P. 161-171.

65. Mulmuley K. Randomized algorithms in computational geometry. // In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, 2000, Elsevier Science Publishers B.V. North-Holland, Amsterdam. pp. 703-724.

66. O'Dunulaing С. and Yap C.K. A Retraction Method for Planning the Motion of a Disc. // Journal of Algorithms. 1985. - Vol. 6. - P. 104-111.

67. Ohya Т., Iri M., Murota K. A fast Voronoi diagram algorithm with quaternary tree bucketing. // Information Processing Letters. -1984. Vol. 18. - P. 227-231.

68. Okabe A., Boots В., Sugihara K. Spatial tessellations: concepts and applications of Voronoi diagrams. 2nd edition. - Wiley, Chichester, 2000. - 671 p.

69. Papadopoulou E. Critical Area Computation for Missing Material Defects in VLSI Circuits. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2001. - Vol. 20. - No. 5. - P. 583-597.

70. Papadopoulou E., Lee D.T. The L(X) Voronoi diagram of segments and VLSI applications. // International Journal of Computational Geometry and Applications. -2001.-Vol. 11. -P. 503-528.

71. Seidel R. Constrained Delaunay triangulations and Voronoi diagrams with obstacles. // In 1978-1988 10-Years IIG. Inst. Inform. Process., Techn. Univ. Graz, Austria.-1988.-P. 178-191.

72. Shamos M.I., Hoey D. Closest-Point Problems. // In Proc. of 16th Annual IEEE Symposium on FOCS. 1975. - P. 151-162.

73. Sherwani N. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers, Dordrecht, 1999. - 482 p.

74. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane. // Advances in Engineering Software. 1987. - Vol. 9. - No. 1, P. 34-55.

75. Suzuki G. A practical online design rule checking system. // In Proc. of 27th ACM/IEEE Design Automation Conference. 1990. - P. 246-252.

76. Voronoi G.M. Nouvelles applications des parametres continus a la theorie des formes quadratiques. // deuxieme Memoire: Recherches sur les parallelloedres primitifs. Journal fur die reine und angewandte Mathematik. 1908. - V. 134. - S. 198-287.

77. Утверждаю» Директор отделения архитектуры Интел1. Член-корреспондент РАН1. Акт внедрениярезультатов диссертационной работы Малинаускаса Костаса* Кбш^эиЗ

78. Разработка математического и программного обеспечения систем топологического проектирования СБИС с использованием диаграмм Вороного», представленной на соискание учёной степени кандидата наук.

79. J1/ь и'^л-у- д.т.н. В.Е. Вулихман' .-.■•/->-••■/ ■ к.т.н. А.В. Жмурин/ ■