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

С усложнением процессов производства интегральных схем, переходом на нанометровые технологии и увеличением степени интеграции растёт внимание к средствам автоматизации топологического проектирования (ТП) СБИС. Системы ТП решают задачи синтеза топологии ИС и включают программные средства для размещения элементов схемы, глобальной и детальной трассировки соединений, анализа и оптимизации топологии по различным критериям. Вклад в развитие систем ТП внесли ряд отечественных и зарубежных авторов: Г. Г. Казённое, В. М. Щемелинин, В. А. Селютин, Б. В. Баталов, Г. Э. Широ, 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. Результаты диссертации внедрены в учебный процесс в МФТИ на базовой кафедре Интела в курсе «Математические основы САПР».