Содержание к диссертации
Введение
Глава 1. Проблемы математического и программного обеспечения топологического проектирования СБИС 10
1.1. Тенденции развития математических и программных средств автоматизации топологического проектирования 10
1.2. Проблемы построения специализированных графовых моделей 11
1.3. Использование диаграмм Вороного в графовых моделях: существующие и потенциальные области применения 12
1.4. Выводы 19
Глава 2. Динамический алгоритм построения абстрактной диаграммы Вороного 20
2.1. Определения диаграммы Вороного 20
2.2. Методы построения диаграмм Вороного 29
2.3. Абстрактная диаграмма Вороного 3 5
2.4. Основная идея динамического алгоритма 39
2.5. Инкрементальный алгоритм Кляйна 39
2.6. Удаление объекта из АДВ и динамический алгоритм 48
2.7. Анализ динамического алгоритма 55
2.8. Выводы 60
Глава 3. Использование динамического алгоритма в системах проверки, исправления и сжатия топологии СБИС 62
3.1. Постановка задачи 62
3.2. Метод построения графа ограничений на основе диаграммы Вороного 65
3.3. Анализ эффективности метода 76
3.4. Анализ избыточности графа ограничений 77
3.5. Выводы 78
Глава 4. Использование динамического алгоритма в системе глобальной трассировки и оценки суммарной длины соединений СБИС 79
4.1. Постановка задачи 79
4.2. Метод построения графа трассировки на основе диаграммы Вороного 80
4.3. Анализ эффективности метода 85
4.4. Анализ избыточности модели на основе диаграммы Вороного по сравнению с сеточными моделями 86
4.5. Анализ точности модели на основе диаграммы Вороного по сравнению с графом пересечения каналов и другими моделями 86
4.6. Выводы 88
Глава 5. Использование динамического алгоритма в системе преобразования топологии фотошаблона в символьную модель 89
5.1. Постановка задачи 89
5.2. Метод декомпозиции манхэтгенского многоугольника на основе диаграммы Вороного 91
5.3. Анализ эффективности метода 102
5.4. Адекватность декомпозиции на основе диаграммы Вороного требованиям символьной модели топологии 103
5.5. Выводы 103
Заключение 105
Список литературы
- Проблемы построения специализированных графовых моделей
- Методы построения диаграмм Вороного
- Метод построения графа ограничений на основе диаграммы Вороного
- Анализ избыточности модели на основе диаграммы Вороного по сравнению с сеточными моделями
Введение к работе
С усложнением процессов производства интегральных схем, переходом на нанометровые технологии и увеличением степени интеграции растёт внимание к средствам автоматизации топологического проектирования (ТП) СБИС. Системы ТП решают задачи синтеза топологии ИС и включают программные средства для размещения элементов схемы, глобальной и детальной трассировки соединений, анализа и оптимизации топологии по различным критериям. Вклад в развитие систем ТП внесли ряд отечественных и зарубежных авторов: Г.Г. Казённое, В.М. Щемелинин, В.А. Селютин, Б.В. Баталов, Г.Э. Широ, A.M. Марченко, В.Е. Вулихман, А.В. Жмурин, Н. Шервани, М. Ласло, А.Б. Канг, Е. Пападопуло и др. Математический базис, используемый в отрасли, можно найти в трудах М. Шеймоса, Ф. Препараты, А. Фокса, К.Л. Кларксона, П.В. Шора, Р. Кляйна, Ф. Ауренхаммера, С. Фотьюна и
др.
В данной работе рассматриваются вопросы построения специализированных графовых моделей в системах ТП, востребованных при описании отношений и связей между элементами топологии. Здесь приходится сталкиваться со следующими проблемами. Адекватность моделей предметной области - один из главных факторов, определяющий качество систем и процент выхода годных микросхем. Уменьшение избыточности и размеров данных важно для оптимизации использования памяти и ускорения обработки данных. Эффективность алгоритмов построения моделей - требование, обусловленное
постоянно растущей степенью интеграции (более 10 транзисторов). Эффективность динамического обновления моделей особенно важна с возрастанием числа обратных связей в маршрутах проектирования, распространением итерационных методов оптимизации и интерактивного редактирования топологии. В интерактивной системе человек ожидает быстрой реакции на свои действия, в итерационном методе многократные локальные
5 корректировки топологии должны быть быстро отражены в используемых моделях.
Для комплексного решения перечисленных проблем в настоящей работе предлагается использование моделей, основанных на диаграммах Вороного. Классической диаграммой Вороного (ДВ) для точечных объектов называется разбиение плоскости на ячейки, каждая из которых есть локус точек, расположенных ближе к одному из объектов в метрике Евклида, чем к остальным. Известны модификации данного определения: для сложных объектов (отрезков, фигур и др.), в различных метриках и т.д. ДВ является плоским графом, рёбра которого суть участки средних линий между объектами. Идея использования ДВ в математическом и программном обеспечении систем ТП не является новой. Как удобный инструмент решения ряда геометрических задач, ДВ уже нашла применение в САПР, помогая строить адекватные графовые модели с относительно малыми затратами времени и памяти [ 19] [31 ] [43 ] [76] [77]. Так, известны примеры использования в системах оценки выхода годных и начального размещения.
Использование ДВ может также повысить качество и уменьшить избыточность графовых моделей в системах глобальной трассировки, проверки, исправления, сжатия и преобразования топологии СБИС. Т.е., актуальным представляется расширение области применения ДВ в математическом и программном обеспечении систем ТП, где востребованы эффективные средства представления информации о взаимном расположении элементов топологии СБИС в виде плоских графов. Существуют эффективные динамические алгоритмы построения ДВ, перестраивающие её локально быстрее, чем с нуля. Несмотря на это, до сих пор динамические диаграммы не использовались в САПР. Поэтому актуальным становится использование преимуществ динамического построения ДВ в интерактивных системах ТП, а также в итерационных методах локальной оптимизации топологии. Однако известные динамические алгоритмы применимы только к конкретным определениям ДВ, т.е. не являются универсальными. Поэтому актуальна
разработка универсального динамического алгоритма построения диаграмм Вороного разного рода, используемых в САПР. Исходя из этого, решено обратиться к концепции абстрактной диаграммы Вороного (АДВ), обобщающей широкий класс ДВ.
Цель диссертационной работы заключается в разработке эффективных динамических моделей, алгоритмов и программных средств на основе абстрактной диаграммы Вороного для использования в системах ТП СБИС. Для достижения поставленной цели автором поставлены и решены следующие задачи:
разработка метода построения графа ограничений на основе ДВ в системах проверки, исправления и сжатия топологии СБИС;
разработка метода построения планировочного графа на основе ДВ в системе глобальной трассировки и оценки суммарной длины соединений СБИС;
разработка метода декомпозиции манхэттенского многоугольника на основе ДВ в системе преобразования топологии фотошаблона в символьное представление.
разработка динамического алгоритма построения АДВ, теоретическое обоснование его корректности и эффективности;
реализация метода декомпозиции многоугольника и его внедрение в программный комплекс оптимизации топологии СБИС, эксплуатируемый в компании Интел.
Методы исследования базируются на фундаментальных положениях теории алгоритмов и вычислительной сложности, аналитической и вычислительной геометрии, общей топологии, правилах построения программного обеспечения, а также на принципах проектирования топологии интегральных схем.
Научная новизна состоит в разработке моделей, методов и алгоритмов, вносящих вклад в развитие математической теории вычислений и обработки геометрических данных, и позволяющих повысить качество и эффективность
7 систем ТП. В ходе выполнения диссертационной работы получен ряд научных результатов, на данный момент не имеющих аналогов.
Доказана теорема об эффективном удалении объекта и разработан динамический алгоритм вычисления АДВ - универсальный инструмент, повышающий эффективность различных методов ТП.
Доказано, что граф ограничений, используемый в задачах проверки, исправления и сжатия топологии является двойственным к ДВ специального вида. Этот факт лёг в основу динамического метода построения графа ограничений.
Показана целесообразность использования ДВ в метрике La, для построения планировочного графа в задачах глобальной трассировки и оценки суммарной длины соединений.
Доказаны специальные свойства ядра Вороного в метрике L,», позволившие построить динамический метод декомпозиции многоугольника в задаче преобразования топологии фотошаблона в символьное представление.
Практическая значимость работы заключается в расширении интеллектуальных возможностей вычислительных систем ТП СБИС за счёт использования АДВ и динамического алгоритма её построения. Комплексно решаются проблемы быстродействия, качества и избыточности используемых графовых моделей в системах проверки, исправления и сжатия топологии, глобальной трассировки и оценки суммарной длины соединений СБИС, преобразования топологии. Для построения трёх независимых графовых моделей впервые предложены динамические методы на основе АДВ. Динамический алгоритм вычисления АДВ даёт выигрыш во времени локального обновления графовых моделей относительно полного перестроения: 0{п) по сравнению с 0(п log п) времени, где п - размер входных данных. Оценочное ускорение - от 5-10 раз до 20-40 раз при размерах входных данных от 100 до 1 000 000 объектов. Алгоритм востребован в интерактивных системах редактирования и итерационных методах оптимизации топологии. Его
8 программная реализация в виде модуля удобна для включения в библиотеку геометрического программного обеспечения и независимого повторного использования при построении моделей на основе ДВ разного рода. Это позволяет унифицировать программный код и сократить его объём.
Достоверность научных положений и выводов, полученных соискателем, подтверждается теоретическими выкладками и успешным промышленным внедрением.
Личный вклад автора. Все основные результаты получены автором лично. Постановка задачи выполнена совместно с научным руководителем. Автор принимал активное участие в разработке архитектуры, реализации, документации и тестировании программного обеспечения, внедрённого в ЗАО «Интел А/О».
Внедрение результатов работы. Метод преобразования фотошаблонного представления проводника в символьное внедрён в программный комплекс оптимизации топологии СБИС в ЗАО «Интел А/О». При работе на символьной топологии уровня функциональных блоков (порядка 104 транзисторов) метод позволил однозначным образом осуществлять быстрое преобразование шаблонных проводников в символьные, упростить восстановление их направления и связности, ускорить локальные преобразования топологии в 10-15 раз и применить эффективные алгоритмы анализа топологии фотошаблона с интерактивным отображением в символьную модель, что в совокупности привело к общему ускорению маршрута оптимизации топологии в 1.5-2.8 раз. Результаты диссертации внедрены в учебный процесс МФТИ на базовой кафедре Интела в курсе «Математические основы САПР».
На защиту выносятся:
метод построения графа ограничений на основе ДВ;
метод построения графа глобальной трассировки на основе ДВ;
метод декомпозиции фотошаблонного проводника на основе ДВ;
динамический алгоритм вычисления АДВ, лежащий в основе предложенных методов;
результаты промышленного внедрения.
Апробация результатов работы проводилась на конференциях и семинарах: Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 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 акт о внедрении в учебный процесс.
Проблемы построения специализированных графовых моделей
Топология схемы является сложным геометрическим объектом, состоящим из манхэттенских многоугольников (со сторонами, параллельными координатным осям), в полупроводниковых и металлических слоях (рисунок 1.1). Системы топологического проектирования (ТП) решают задачи синтеза топологии СБИС по функциональному и логическому описаниям для реализации на кристалле в виде транзисторов, стандартных ячеек и электрических соединений. Для получения наиболее полного представления об истории и направлениях развития средств автоматизации ТП читатель отсылается к трудам [1][14][16][17][20][35][56][64][80], а также к материалам ежегодной международной конференции ISPD (International Symposium on Physical Design). Отметим некоторые тенденции развития современных математических и программных средств ТП и возникающие здесь проблемы.
С усложнением технологических процессов и увеличением степени интеграции ИС растёт внимание и повышаются требования к системам ТП. Особенно это характерно для производства заказных СБИС, таких как микропроцессоры. По мере того, как схемы становятся сложнее (до сотен миллионов транзисторов), а размеры элементов уменьшаются (десятки нанометров в настоящее время), приходится работать с топологиями больших размеров, одновременно учитывая разнообразные физические эффекты, возникающие на кристалле. Несмотря на развитие вычислительных мощностей, математическое и программное обеспечение систем ТП вынуждено развиваться в сторону повышения качества моделей и эффективности алгоритмов.
Маршруты синтеза топологии характеризуются большим числом обратных связей, когда по результатам последующих этапов приходится уточнять решения, полученные на предыдущих. Поэтому получили развитие итерационные методы ТП. Например, по результатам глобальной трассировки уточняют начальное размещение блоков схемы. Кроме того, требуется исправлять ошибки и проводить локальные корректировки на конечных стадиях проектирования. Так, возможны перемещения элементов топологии, вставка буферов, изменение размеров транзисторов и т.д. При этом в интерактивном режиме требуется выполнить верификацию и оптимизацию схемы (сжатие, уменьшение задержек в цепях и т.п.). В итерационных и интерактивных системах ТП востребованы динамические алгоритмы, позволяющие более эффективно работать при локальных изменениях топологии.
Наряду с эффективными средствами для хранения и доступа к данным (связанные углы, одномерные и иерархические квадранты и т.д.) в системах ТП востребованы специализированные графовые модели, описывающие разнообразные отношения и связи между элементами топологии. Использование плоских графов имеет определённые преимущества: во-первых, плоские графы являются разреженными (с линейной зависимостью числа вершин и рёбер) и приводят к моделям линейного размера с малой избыточностью; во-вторых, возможен быстрый доступ к соседним элементам, что обеспечивает константную сложность локальных операций в моделях. Среди проблем, возникающих при разработке графовых моделей, можно перечислить следующие.
Точность моделей, или адекватность моделей предметной области является одним из главных факторов, определяющим качество систем автоматизации ТП и, как результат, процент выхода годных микросхем.
Уменьшение избыточности и размеров данных важно при условии ограниченности ресурсов памяти для оптимизации её использования и ускорения обработки данных.
Эффективность алгоритмов построения моделей - требование, не перестающее быть актуальным и обусловленное постоянно растущей степенью интеграции (до сотен миллионов транзисторов на кристалле).
Эффективность динамического обновления моделей становится особенно важной с распространением итерационных методов оптимизации и интерактивного редактирования топологии. В интерактивной системе человек ожидает быстрой реакции на свои действия, в итерационном методе многократные локальные корректировки топологии должны быть быстро отражены в используемых моделях.
Методы построения диаграмм Вороного
За последние полстолетия было предложено множество алгоритмов для построения классических диаграмм Вороного и их обобщений. В большинстве случаев идеи, применяемые в алгоритмах построения разновидностей диаграмм схожи. Поэтому будем говорить об основных классах методов построения [22]: инкрементальное построение, подход «разделяй и властвуй», методика заметания плоскости и поднятие в трёхмерное пространство. Рассмотрим эти классы на примере построения классической диаграммы Вороного для точек в метрике Евклида [22]. Шеймос показал [13], что нижняя оценка сложности построения диаграммы Вороного для п точек - 0(n log п), так как к построению ДВ можно свести задачу сортировки п чисел. Для сохранения ДВ требуется линейный размер памяти [13] - 0{п). Поэтому алгоритмы, приведённые ниже и имеющие такие показатели сложности, являются оптимальными.
Поднятие в трёхмерное пространство. Известно несколько способов взаимно однозначного отображения между выпуклыми оболочками в трёх измерениях и двумерными диаграммами Вороного. Поскольку для первых известны CHnlogri) алгоритмы построения [13], то, применив простое преобразование за линейное время, получаем оптимальный метод построения диаграмм Вороного. Например, один из способов преобразования - через стереографическую проекцию [23] (рисунок 2.11 слева), другой - через проекцию на параболоид [22] (рисунок 2.11 справа). В первом случае взаимно однозначное соответствие устанавливается между рёбрами плоской триангуляции Делоне и рёбрами трёхмерной выпуклой оболочки. В последнем случае - между графом Делоне и нижней выпуклой оболочкой. Рассмотренный подход к построению ДВ хорош тем, что легко обобщается на пространства большей размерности [23].
Слева: связь ДВ с выпуклой оболочкой.
Справа: связь графа Делоне с нижней выпуклой оболочкой Подход «разделяй и властвуй». Данный подход является одним из самых мощных вообще в теории алгоритмов и часто приводит к оптимальным алгоритмам. Он заключается в рекурсивном делении множества входных данных на равновеликие подмножества (обычно два), решении задачи независимо для подмножеств и слиянии результатов. Применительно к диаграммам Вороного множество точечных объектов делится рекурсивно на примерно равновеликие части вертикальной прямой - медианой [79]. ДВ вычисляется для левого и правого подмножества, Ключевым моментом является вычисление биссектрисы левого и правого множеств, необходимое для слияния двух диаграмм (см. рисунок 2.12).
Рисунок 2.12. Слияние левой и правой ДВ в подходе «разделяй и властвуй» В [51] подобный подход применён к построению триангуляции Делоне, а в [41] горизонтальные и вертикальные медианы используются по очереди. Авторы [57] рекурсивно делят плоскость на четыре прямоугольные части в порядке, задаваемым квадродеревом. Все алгоритмы данного класса имеют оптимальную сложность 0{п log п) в худшем случае и требует линейного размера памяти.
Преимущество подхода «разделяй и властвуй» в том, что он хорошо поддаётся распараллеливанию. Параллельный алгоритм построения ДВ и графа Делоне можно найти, например, в [57].
Методика заметания плоскости, или сканирующей линии. Данная методика является мощным инструментом решения большинства геометрических задач. Общая идея состоит в следующем. Исходные геометрические данные задачи (точки) упорядочиваются по возрастанию абсциссы. Вертикальная прямая сканирует плоскость слева направо. При этом в каждый момент времени задача решена для исходных данных слева от прямой. Правая граница вычисленного результата (диаграммы Вороного) сохраняется в упорядоченном по ординате виде и называется статусом сканирующей линии, или волновым фронтом. Перемещение линии происходит в дискретные моменты, называемые событиями. Во-первых, событием является очередное чтение исходных данных (очередной точки). Также событие может относиться к обнаружению очередного результата вычисления (вершины Вороного, пересечения прямых и т.д.). Каждый окончательный результат, не влияющий на последующие вычисления, удаляется из волнового фронта. Данные новых событий, напротив, добавляются к волновому фронту. Ознакомится с алгоритмами заметания плоскости, строящими диаграмму Вороного или граф Делоне, можно в работах [36], [45] и [78]. Авторы [78] рассматривают сканирующую линию как дополнительный объект, при этом волновой фронт -это кривая, состоящая из парабол и отделяющая сканирующую линию от точечных объектов слева от неё (см. рисунок 2.13).
Метод построения графа ограничений на основе диаграммы Вороного
Диаграмма Вороного специального вида. Здесь и далее рассматривается граф горизонтальных ограничений (полученные результаты применимы и к графу вертикальных ограничений, если поменять местами оси координат). В качестве вершин графа возьмём вертикальные стороны многоугольников - элементов топологии схемы. То есть будем считать, что все многоугольники потенциально могут как двигаться, так и трансформироваться. На рисунке 3.2 показаны возможные варианты ограничений между сторонами фигур в одном топологическом слое. На рисунке 3.3 - возможные варианты ограничений для фигур в двух различных слоях топологии. Видим, что ребро в графе появляется, только если между соответствующими сторонами фигур имеется отношение видимости вдоль горизонтального направления, то есть их проекции на ось у пересекаются1.
Ограничения перекрытия (слева), расстояния (посередине) и включения (справа) фигур в различных слоях Введём понятие специальной диаграммы Вороного, отражающей это отношение видимости. Диаграмму Вороного построим для объектов -вертикальных отрезков плоскости, соответствующих вертикальным сторонам многоугольников. Зададим функцию расстояния от точки и с координатами (хиУи) до объекта-отрезка р с координатами концов (хрур1) и (хр,ур2) как d(u,p) = \хы-хр\,у„фр1,ур2], + « УиФрІ Ур2І
На рисунке 3.4 показаны всевозможные варианты биссектрис между вертикальными отрезками с заданной функцией расстояния. Видно, что при обычном определении биссектрисы как множества точек, равноудалённых от пары объектов, она может содержать вертикальный отрезок и одну или две горизонтальные плоские полосы. Такие биссектрисы нас не устраивают, поэтому уточним определение.
Возможные варианты биссектрисы как места точек, равноудалённых от пары объектов Пусть задан набор объектов - вертикальных отрезков: /?/,...,/ „, и для каждой пары объектовр{ ир/. \ i j n определена область доминированияр над q - D(p,q) = {u\d{up) d{u,q)}. Биссектрисой J(p,q) назовём теперь границу bd D(p,q). Тогда она всегда является неограниченной кривой и не содержит двумерных областей. Однако при таком определении биссектриса не является симметричной, а плоскость может содержать области, не относящиеся ни к одной из областей доминирования (рисунок 3.5).
Рисунок 3.5. Возможные варианты биссектрисы как границы области доминирования, которая определяется функцией расстояния Изменим определение биссектрисы ещё раз так, чтобы области доминирования вместе с биссектрисой покрывали всю плоскость. Пусть отрезок si находится слева от - Биссектрисой будем называть кривую, состоящую из вертикального отрезка и двух лучей (рисунок 3.6). VR(p,S) называется ячейкой Вороного объекта р, или р-ячейкой относительно множества объектов S; EVR(p,S) называется расширенной ячейкой Вороного объекта р относительно S. V(5) называется абстрактной диаграммой Вороного множества объектов S.
Можно показать, что соблюдаются также следующие два условия, необходимые для корректного определения АДВ. А именно для всех непустых подмножеств S QS 5) \fpeS VR(p,S ) 0, EVRfoS ) и VR(p,y) - линейно связные множества; 6) R2 = \J s,EVR(p,S ) - дизъюнктное объединение. Возможные варианты биссектрисы Всевозможные варианты начертания определённых выше биссектрис показаны на рисунке 3.7, а на рисунке 3.8 представлены диаграммы Вороного специального вида для набора вертикальных отрезков - сторон фигур топологии для одного слоя и для пары слоев. ДВ является плоским графом, рёбра которого суть ломаные линии, состоящие из горизонтальных и вертикальных отрезков. В общем случае ребро Вороного может содержать один вертикальный отрезок (возможно, вырожденный в точку) и до двух горизонтальных отрезков. Двойственный граф Делоне отражает отношение горизонтальной видимости между объектами, а рёбра графа ограничений напрямую соответствуют тем рёбрам Вороного, в которых содержится вертикальный участок (возможно, вырожденный в точку). Отметим, что два последних варианта биссектрисы на рисунке 3.7 соответствуют объектам, не состоящим в отношении горизонтальной видимости. Тем не менее, подобных рёбер на диаграмме Вороного можно избежать, если предположить, что топология схемы всегда имеет условные левую и правую границу -вертикальные отрезки L и R достаточно большой протяжённости, что все элементы топологии горизонтально проецируются на L справа и на R слева (рисунок 3.8).
Анализ избыточности модели на основе диаграммы Вороного по сравнению с сеточными моделями
В топологическом проектировании интегральных схем чаще всего используются две модели представлении топологии: шаблонная и символьная [80]. Шаблонная модель (mask layout, масочная модель, или топология фотошаблона) наиболее приближена к технологическому процессу производства и состоит из наборов плоских фигур в (фото)шаблонных слоях. Сегодня фигуры - это, как правило, манхэттенские многоугольники (со сторонами, параллельными координатным осям). Символьная модель (symbolic layout) - это топологическая эссенция шаблонной модели, в ней группам многоугольников (обычно прямоугольников) ставятся в соответствие символы, характеризующиеся координатами на кристалле. размерами и функциональностью (транзистор, участок соединительного проводника, сквозной переход и т.д.). Символьная модель имеет преимущества в тех случаях, когда конкретные технологические параметры неизвестны или могут меняться (как, например, в процессе миграции топологии). Также модель удобна для первоначального проектирования, хранения и дальнейшего редактирования топологии (в частности, в графических редакторах). Гем не менее, задачи САПР, близкие к технологическому процессу (проверка правильности топологии - ІЖС. сжатие, исправление топологии), более эффективно решаются на шаблонной модели. Следовательно, становится актуальным преобразование топологии из одной модели в другую. Принимая во внимание сверхбольшую степень интеграции современных схем. понимаем необходимость эффективных алгоритмов решения задачи преобразования.
Преобразование из символьной модели в шаблонную тривиально: при известных технологических параметрах, определяющих размеры символов. топология фотошаблона получается путём объединения многоугольников в каждом слое. К обратному преобразованию существуют разные подходы, дающие различные результаты.
Рассмотрим задачу преобразования соединительного проводника из шаблонного представления в символьное. В первом случае он представляется манхэттенским многоугольником в проводящем слое, во втором - набором связных прямоугольников (см. рисунок 5.1). То есть задача сводится к декомпозиции манхэттенского многоугольника на прямоугольники, объединение которых совпадает с многоугольником. Соединительные проводники в шаблонном представлении (сверху) и символьном представлении (снизу) В настоящее время широко применяется (например, в [55]) нарезание многоугольных проводников на прямоугольники, для сохранения связности которых используется структура данных «сшивания углов» (corner-stitching). Имеется несколько недостатков такого подхода. Во-первых, количество, ориентация и связность полученных прямоугольников неоднозначны (см. рисунок 5.2) и возникает вопрос выбора вариантов. Причём выбор ориентации прямоугольников требует дополнительного анализа для возможности правильного восстановления связности (рисунок 5.2). Во-вторых, отсутствуют динамические методы декомпозиции, эффективно изменяющие нарезку при деформации многоугольника. Динамические методы востребованы в системах сжатия и исправления топологии (см. раздел 3.1), воспринимающих символьную топологию в качестве исходных данных и преобразующих её в шаблонную для внутреннего представления и применения эффективных алгоритмов. Например, динамический метод полезен в случае, когда на каком-либо этапе сжатия или исправления топологии произошла локальная деформация проводника и необходимо быстро отобразить изменения в символьную модель для представления разработчику, в то время как полное преобразование всей топологии занимает слишком много времени. Таким образом, поставлена следующая задача, решаемая далее с применением диаграмм Вороного.
. Неоднозначность нарезки многоугольников на прямоугольники и сложность выбора направлений Постановка задачи. Разработать эффективный метод однозначной декомпозиции манхэттенского многоугольника на прямоугольники, сохраняющий информацию об их связности и ориентации, и позволяющий более быстрое перестроение декомпозиции при относительно небольших деформациях многоугольника.
