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

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

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО

ОБЕСПЕЧЕНИЯ СИСТЕМ ТОПОЛОГИЧЕСКОГО

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

ВОРОНОГО

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

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

Москва – 2007 г.

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Селищев Сергей Васильевич кандидат физико-математических наук, научный сотрудник Панкратьев Антон Евгеньевич ООО Фирма «АНКАД», г. Москва

Ведущая организация:

Защита диссертации состоится «_» 2007 г. в часов на заседании диссертационного совета Д.212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, г. Москва, Зеленоград, МИЭТ.

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

Автореферат разослан «_» 2007 г.

Соискатель К.К. Малинаускас

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Препараты, А. Фокса, К.Л. Кларксона, П.В. Шора, Р. Кляйна, Ф.

Ауренхаммера, С. Фотьюна и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комплексно решаются проблемы быстродействия, качества и избыточности используемых графовых моделей в системах проверки, исправления и сжатия топологии, глобальной трассировки и оценки суммарной длины соединений СБИС, преобразования топологии. Для построения трёх независимых графовых моделей впервые предложены динамические методы на основе АДВ. Динамический алгоритм вычисления АДВ даёт выигрыш во времени локального обновления графовых моделей относительно полного перестроения: O(n) по сравнению с O(n log n) времени, где n – размер входных данных.

Оценочное ускорение – от 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-ой степени в секции «Математические модели и алгоритмы в информатике».

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

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

Работа содержит 115 стр., 1 акт о внедрении в производство и 1 акт о внедрении в учебный процесс.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Топология схемы является сложным геометрическим объектом, состоящим из манхэттенских многоугольников (со сторонами, параллельными координатным осям), в полупроводниковых и металлических слоях (рисунок 1).

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

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

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

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

Рассмотрим потенциальные области применения диаграмм ДВ в системах ТП.

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

Исправление заключается в устранении нарушений путём наименьшей трансформации топологии. Одномерное сжатие состоит в минимизации совокупной площади кристалла путём перемещения элементов топологии вдоль одной из координат. В системах проверки, исправления и сжатия часто используются методы, работающие на модели графа ограничений (рисунок 2). Вершины графа представляют подвижные элементы (стороны многоугольников), рёбра – ограничения на расстояния между ними. Построение графа является наиболее трудоёмкой задачей. Используемые методы (сканирующей линии, теневые и др.) имеют сложность по времени O(n log n), O(nn) и даже O(n2). Неизвестен метод, более эффективно перестраивающий граф при локальном изменении топологии фотошаблона. В третьей главе предложен такой метод, основанный на ДВ.

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

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

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

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

Следовательно, востребован метод, динамически перестраивающий граф трассировки. В четвёртой главе приводится метод построения графа с помощью ДВ, решающий данные проблемы.

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

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

Ввиду разнообразия способов задания ДВ решено обратиться к понятию абстрактной диаграммы Вороного (АДВ), введённому немецким математиком Р. Кляйном в 1988 году, – аксиоматическому определению, обобщающему широкий класс конкретных видов ДВ, применяемых в САПР. АДВ задаётся через систему биссектрис между абстрактными объектами – натуральными числами от 1 до n, удовлетворяющую определённым аксиомам. Для каждой пары объектов p и q задана кривая линия – биссектриса J(p,q), разделяющая области доминирования p над q – D(p,q) и q над p – D(q,p).

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

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

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

Рисунок 6 – Слева: процедура добавления объекта в АДВ.

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

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

Теорема 1. Пусть R – множество объектов, N R – множество соседей s R, s, I – множество невидимых объектов в R. Тогда Удалить из АДВ рёбра ячейки VR(s) Построить АДВ* для соседей s и невидимых объектов (алгоритмом Пересечь АДВ* с VR(s) и оставить только часть АДВ* внутри VR(s) Склеить основную АДВ и АДВ* Рисунок 7 – Слева: процедура удаления объекта из АДВ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диаграмма Вороного специального вида является частным случаем АДВ. Рассмотрим ДВ для вертикальных отрезков. Система биссектрис задаётся на основе специальной функции расстояния от точки u с координатами (xu,yu) до объекта-отрезка p с координатами концов (xp,yp1) и (xp,yp2):

Затем определение уточняется, чтобы биссектрисы удовлетворяли аксиомам АДВ. В окончательном варианте биссектриса состоит из одного вертикального отрезка и двух лучей, как изображено на рисунке y B = max{ y1B, y 2 B }, yT = min{ y1T, y 2T }. Направления горизонтальных Рисунок 9 - Специальное определение биссектрисы вертикальных отрезков ДВ специального вида (рисунок 10) вычисляется представленным выше динамическим алгоритмом, для чего реализована базовая операция алгоритма применительно к данной ДВ и исследованы варианты построения биссектрис. Предложенный метод позволяет строить граф ограничений за ожидаемое время O(n log n) с использованием O(n) памяти, что сравнимо с лучшими известными методами. При этом граф c n вершинами имеет асимптотически оптимальный размер – O(n). В отличие от стандартных методов построения графа ограничений, предложенный метод обрабатывает локальные изменения топологии фотошаблона быстрее, чем построение графа с нуля – за время O(n) в худшем случае. Благодаря этому он имеет преимущества в системах интерактивной проверки правильности топологии, итерационных методах полуторамерного сжатия и исправления (когда в результате локальных изменений топологии в ортогональном направлении необходимо перестраивать граф ограничений для повторного сжатия/исправления в основном направлении).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

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

5. Malinauskas K.K., Marchenko A.M, Zinchenko A.V. Voronoi Diagrams in L metrics and Application in Mask to Symbolic Layout Conversion. // In Proc. of International Science Conference “Intelligent Systems (IEEE AIS-05)” and “Intelligent CAD’s (CADVol. 3. – P. 69–74.

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

7. Малинаускас К.К. Обзор алгоритмов поиска кратчайших путей в задачах сжатия топологии ИС. // Известия вузов. Электроника, 8. Малинаускас К.К. Динамическое построение абстрактных диаграмм Вороного. // Фундаментальная и прикладная математика, 2007, том 13, № 2. – C. 133–146.

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

Малинаускас К.К. Специальная диаграмма Вороного для 10.

построения графа ограничений в задачах топологического проектирования СБИС. // Известия вузов. Электроника, 2007, Подписано в печать:

Заказ № Тираж экз. Уч.-изд.л. Формат 60х84 1/ Отпечатано в типографии МИЭТ (ТУ).

103498, Москва, МИЭТ (ТУ).