Разработка математического и программного обеспечения систем топологического проектирования СБИС с использованием диаграмм Вороного тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Малинаускас, Костас Костович

• Малинаускас, Костас Костович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Малинаускас, Костас Костович

Введение

Глава 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. Результаты диссертации внедрены в учебный процесс в МФТИ на базовой кафедре Интела в курсе «Математические основы САПР».

Список литературы диссертационного исследования кандидат физико-математических наук Малинаускас, Костас Костович, 2007 год

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/ь и'^л-у- д.т.н. В.Е. Вулихман' .-.■•/->-••■/ ■ к.т.н. А.В. Жмурин/ ■