Содержание к диссертации
Введение
1. Обзор и анализ алгоритмов сжатия топологии сбис 11
1.1 Постановка задачи сжатия 11
1.2 Классификация алгоритмов сжатия топологии СБИС 12
1.3 Одномерное сжатие 14
1.4 1.5-мерное сжатие 28
1.5 Двухмерное сжатие 32
1.6 Иерархическое сжатие 37
1.7 Выводы 39
2. Разработка подхода к задаче сжатия топологии СБИС ... 40
2.1 Постановка задачи 40
2.2 Подход к решению задачи 43
2.3 Пример процесса сжатия ячейки мультиплексора 45
2.4 Выводы 56
3. Разработка методов описания топологии СБИС на базе набора примитивов 57
3.1 Общие сведения 57
3.2 Разработка методов создания и описания примитивных геометрических объектов 59
3.3 Разработка метода описания слоев и конструкторских правил 75
3.4 Построение абстрактных объектов для компонентов СБИС 80
3.5 Разработка методики описания технологических правил для изготовления СБИС 83
3.6 Методика расчета основных параметров ячеек 88
3.7 Выводы 91
4. Разработка методов и алгоритмов модификации топологии сбис 92
4.1 Разработка алгоритма перемещения узла 92
4.1.1 Разработка алгоритма определения возможности перемещения узла 99
4.1.2 Разработка алгоритма построения очереди примитивов для модификации топологии 111
4.2 Определение временной сложности алгоритмов модификации топологии 122
4.3 Выводы 123
5. Разработка алгоритма двухмерного сжатия топологии сбис на основе метода имитации отжига 124
5.1 Общие сведения 124
5.2 Разработка алгоритма сжатия топологии СБИС на основе метода имитации отжига 127
5.3 Выбор целевой функции 130
5.4 Выводы 135
6. Экспериментальное исследование разработанного алгоритма сжатия топологии СБИС 136
6.1 Выбор параметров целевой функции 136
6.2 Выбор значений управляющих параметров процесса имитации отжига 144
6.3 Определение временной сложности алгоритма сжатия топологии СБИС 146
6.4 Сравнение предложенного алгоритма с аналогами 153
6.5 Выводы 154
Заключение 156
Литература
- Классификация алгоритмов сжатия топологии СБИС
- Пример процесса сжатия ячейки мультиплексора
- Разработка метода описания слоев и конструкторских правил
- Определение временной сложности алгоритмов модификации топологии
Введение к работе
Возникшая в 60-х годах XX века технология создания интегральных схем развилась, за короткое время, от создания интегральных схем, объединяющих несколько транзисторов, до интеграции миллионов транзисторов в одной схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с набором сопротивлений, предназначенное для выполнения какой-либо логической функции. ИС способны выполнять сложнейшие функции. В настоящее время, элементы могут иметь геометрические размеры до 0.25 микрона. Современная технология позволяет разместить 10-15 миллионов транзисторов на схеме размером 25мм. X 25мм. Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [1]. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС) интенсивно используют средства автоматизации проектирования и многие фазы могут быть полностью или частично автоматизированы [1-25].
Цикл проектирования СБИС включает следующие основные фазы: спецификация системы, функциональное проектирование, логическое проектирование, схемное проектирование, конструкторское проектирование, изготовление, сборка, тестирование и контроль.
Спецификация системы заключается в разработке описания системы. Основными определяющими факторами являются производительность, функции и физические размеры системы. Спецификация системы - это компромисс между - --рыночными требованиями, технологическими и экономическими возможностями^4 -Результатом спецификации является описание размеров, производительности и функциональных возможностей системы.
На этапе функционального проектирования определяются основные функциональные устройства системы, определяются взаимосвязи между ними. Основной задачей ставится определение поведения входов, выходов и задержек каждого компонента системы, без определения его внутренней структуры.
Фаза логического проектирования заключается в определении размера слов, распределения регистров и управляющих потоков, арифметических и логических операций. Для логического описания систем используют язык VHDL. Логическое
описание включает минимизированные булевы функции и описание временных задержек. При логическом проектировании делается моделирование и тестирование системы для проверки корректности построенной системы.
Целью схемного проектирования является преобразование результатов логического проектирования в схемы. На этом этапе выполняется схемное моделирование для проверки корректности и задержек каждого компонента. Результатом схемного проектирования является подробное схемное представления системы.
Следующим этапом является конструкторское проектирование. На этом этапе схемное представление системы преобразуется в геометрическое представление. Строится множество геометрических образов, которые выполняют требуемые логические функции представленных компонентов. Соединения между различными компонентами также представляют в виде геометрических образов. Конструкторское проектирование - это комплексный процесс, включающий в себя множество шагов. Результатом этого этапа является проверенное описание топологии схемы.
После верификации топология схемы преобразуется в набор масок. Использование масок, во время различных технологических процессов, позволяет изготовить твердотельную структуру схемы. Обычно на одной пластине кремния диаметров 20 см. удается разместить несколько сотен чипов.
На последних этапах производится тестирование и контроль полученных схем, осуществляется сборка, помещение в защитный корпус и маркировка.
Этап конструкторского проектирования подразделяется на разбиение, планирование, размещение, трассировку, сжатие и верификацию.
Поскольку сейчас ИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группирование компонентов на блоки. В результате разбиения формируется множество блоков и множество соединений между блоками. Задача планирования заключается в определении взаимного расположения блоков относительно друг друга. Задачей размещения является определение конкретного места для каждого блока на кристалле. Трассировка заключается в конструктивной
реализации связей между элементами.
После завершения детальной трассировки топология является функционально полной. На этом этапе топология готова для производства СБИС. Однако после алгоритмов размещения и трассировки в топологии остаются пустые места. Для того чтобы уменьшить себестоимость СБИС и увеличить производительность уменьшают площадь топологии путем уменьшения пустого места без изменения функциональности СБИС. Задачей сжатия топологии является уменьшение размеров топологии во всех направлениях для уменьшения общей площади схемы. Сжатие позволяет уменьшить длину связей и временные задержки между компонентами схемы. Уменьшение площади одного чипа с помощью сжатия позволяет размещать большее число чипов на площади одной подложки.
На последнем этапе делается верификация топологии спроектированной схемы. Она заключается в проверке геометрических размеров, ограничений, временных задержек и других параметров, влияющих на работоспособность схемы.
Цель сжатия топологии - минимизация общей площади топологии без нарушения производственных ограничений и ограничений, заданных проектировщиком. Существует три способа уменьшения площади:
Уменьшение расстояний между элементами. Это выполняется перемещением элементов так близко друг к другу как это возможно. При этом необходимо соблюдать конструкторские ограничения расстояний между элементами.
Уменьшение размеров элементов. При этом необходимо соблюсти конструкторские ограничения размеров элементов.
Изменение форм элементов. При этом необходимо сохранить
электрические характеристики при изменении формы. Ранние попытки автоматизированного сжатия топологии использовали только прямоугольники вдоль осей х и у. Эти методы минимизировали топологию вдоль каждой осп независимо. Такие методы известны, как одномерное сжатие. Основная проблема при таком подходе состоит в том, что сжатия по горизонтали и вертикали не являются взаимозаменяемыми и получаемая топология силыю зависит от исходной конфигурации. Двухмерные методы соединяли два одномерных сжатия в одно. Было доказано, что такой метод является NP-сложным. Оба метода,
ограничиваются проводниками, которые не могут изгибаться.
Сжатие топологии это сложный этап в цикле проектирования СБИС. На этом этапе используется информация о многочисленных деталях производственного процесса, таких как проектировочные правила и ограничения. Сжатие топологии важно для проектирования полностью заказных СБИС, особенно если необходима высокая производительность полученной СБИС.
В этой связи, тема работы, связанная с разработкой новых методов сжатия топологии СБИС является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является разработка новых и модифицированных методов и алгоритмов сжатия топологии СБИС, позволяющих уменьшать площадь топологии и длину соединительных проводников.
В данной работе разработан новый метод для сжатия интегральным схем, использующий криволинейную структуру. С использованием непрямоугольной геометрии, даже без сжатия, можно улучшить использование площади на плоскости за счет произвольной относительной ориентации различных элементов цепей. Проводники рассматриваются как эластичные ленты, плотно натянутые вокруг препятствий. Не требуется проведения вставки изломов, так как в такой структуре не существует прямоугольных ограничений. Элементы цепи рассматриваются как пластичные объекты, которые можно поворачивать и сгибать в пределах параметрических ограничений.
Оптимизация такой структуры - более сложная задача, чем двухмерное сжатие. В данной работе сжатие топологии СБИС будет производиться с помощью стохастического метода оптимизации - метода имитации отжига. Отжиг - это процесс нагревания и медленного охлаждения металла для формирования оптимизированной структуры. Моделирование отжига напоминает процесс, происходящий в металле. Этот метод сжатия выдаст чрезвычайно компактные схемы, с оптимизацией площади топологии и длины проводников. Получаемые топологии, как минимум, не уступают по плотности топологиям созданным вручную.
Для достижения поставленной цели были поставлены следующие задачи: 1. Разработка схемы процесса эволюционного поиска для задач сжатия топологии СБИС.
Разработка структуры данных для представления топологии в криволинейном виде.
Разработка процедур перехода от одного решения к другому.
Разработка целевой функции для оценки качества решения.
Исследование эволюционных алгоритмов для сжатия топологии СБИС.
Для решения поставленных задач были использованы следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории алгоритмов, элементы теории эволюционного поиска.
ОСНОВНЫЕ ПОЛОЖЕНИЯ И РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ:
Новый метод описания топологии СБИС, имеющей криволинейную структуру.
Новый алгоритм видоизменения и модификации топологии СБИС, с учетом выполнения конструкторских ограничений.
Новый общий подход и алгоритм сжатия топологии СБИС, основанный на методе имитации отжига.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
1. Впервые представлен метод описания топологии СБИС, имеющей
криволинейную структуру, упрощающий процедуру видоизменения и
модификации топологии СБИС.
Разработан алгоритм видоизменения и модификации топологии с учетом выполнения конструкторских ограничений, имеющий линейную временную сложность.
Создан общий подход и алгоритм сжатия топологии СБИС, основанный на методе имитации отжига.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
Метод представления топологии СБИС в криволинейном виде.
Алгоритм и программа сжатия топологии СБИС, позволяющие уменьшить площадь топологии СБИС и длину соединительных проводников.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Результаты работы внедрены в РОСНИИ ИТ и АП (Москва) и НИИ ТКБ (Таганрог) в качестве ПО САПР проектирования топологии СБИС.
Кроме того, материалы диссертации использованы в учебном процессе па кафедре САПР ТРТУ при проведении практических занятий и курсовом проектировании по курсам «Методы генетического поиска» и «Автоматизация конструирования ЭВА».
АПРОБАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Основные результаты диссертационной работы обсуждались и были одобрены на научных семинарах ТРТУ «Генетические алгоритмы», на IV Всероссийской конференции студентов и аспирантов ТРТУ, на Всероссийской конференции "Интеллектуальные САПР-97", на XLIII студенческой научной конференции ТРТУ (секция Интеллектуальный САПР).
ПУБЛИКАЦИИ.
Результаты диссертации отражены в 6 печатных работах.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.
Диссертационная работа состоит из введения, шести глав, заключения, списка литературы. Работа содержит 164 страницы, включая 133 рисунков, 8 таблиц, список литературы из 108 наименований, 25 страниц приложений с актами об использовании работы, примерами топологий, полученных в результате экспериментальных исследований и примерами топологий, полученных для стандартных тестов.
Общий принцип построения диссертации состоит в следующем: в начале проводится обзор предыдущих исследований структуры методологии конструирования и ранних методов сжатия. После этого описывается принцип работы предлагаемого алгоритма сжатия топологии СБИС. Затем представляется структура примитивов и способы ее изменения. Далее показывается, как метод оптимизации моделированием отжига используется для сжатия ячеек. В конце приводятся экспериментальные исследования и анализ метода сжатия.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приводится обзор существующих алгоритмов сжатия топологии СБИС. Приводится постановка задачи сжатия. Приведена классификация алгоритмов сжатия топологии СБИС. Затем рассмотрены
алгоритмы, осуществляющие одномерное, 1.5-мерное и двухмерное сжатие топологии. Описана проблема иерархического сжатия топологии СБИС основанного на построении графа ограничений. Рассмотрены недостатки современных алгоритмов.
ВТОРАЯ ГЛАВА дает представление о принципах работы предложенного алгоритма решения задачи сжатия топологии СБИС. Показан подход к решению задачи сжатия. Проиллюстрирована работа алгоритма на примере сжатия топологии мультиплексора. Показаны промежуточные топологии мультиплексора на различных стадиях охлаждения при использовании метода имитирования отжига. Производится сравнение результатов ортогонального и криволинейного сжатий.
ТРЕТЬЯ ГЛАВА описывает новую структуру, специально разработанную для двухмерного криволинейного сжатия. Такая структура данных адаптируется под любую специальную технологию производства. Описано множество примитивов, которые будут использоваться для построения интегральных цепей.
ЧЕТВЕРТАЯ ГЛАВА описывает методы модификации структуры. Рассмотрен алгоритм передвижения узлов. Также описаны дополнительные утилитные функции. Описан процесс изменения полигональной границы ячейки.
ПЯТАЯ ГЛАВА рассматривает процесс оптимизации методом моделирования отжига и его применение к сжатию интегральных цепей. Представлена целевая функция.
В ШЕСТОЙ ГЛАВЕ представлены результаты экспериментальных исследований. Проведен анализ этих результатов. Оценена временная сложность системы. Проведено сравнение предложенного алгоритма с существующими аналогами.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложения содержат копии актов о внедрении и актов об использовании в учебном процессе результатов представленной работы, топологии, полученные в процессе экспериментальных исследований скорости работы алгоритма и примеры топологий, полученных для стандартных тестов.
Классификация алгоритмов сжатия топологии СБИС
Алгоритмы сжатия могут быть классифицированы двумя разными способами. Первый способ - это классификация по направлению перемещения элементов во время сжатия: одномерное сжатие и двухмерное сжатие [4]. При одномерном сжатии элементы перемещаются только по оси х или по оси у. В результате изменяются либо х- либо у- координаты элементов. Если сжатие выполняется вдоль оси х, то оно называется х-сжатисм. Соответственно, если сжатие выполняется вдоль оси у, то оно называется у-сжатием. На рис. 1.1 показан пример х-сжатия, а затем у-сжатия. В случае двухмерного сжатия элементы могут перемещаться одновременно вдоль обеих осей. В результате, во время двухмерного сжатия, изменяются и х- и у- координаты элементов для минимизации площади топологии. На рис. 1.2 показан пример двухмерного сжатия.
Второй способ классификации основывается на методе вычисления минимальных расстояний между элементами [1]. Существует два метода: сжатие с помощью графа ограничений и сжатие с помощью виртуальной сетки. При использовании графа ограничений соединения и минимальные расстояния описываются с помощью линейных неравенств, которые могут быть смоделированы, используя взвешенный ориентированный граф (граф ограничений) как показано на рис. 1.3. Затем граф ограничений используется для вычисления новых позиций элементов.
Другой метод, метод виртуальной сетки, предполагает, что топология располагается на сетке. Каждый элемент рассматривается прикрепленным к линии сетки. Во время сжатия алгоритм сдвигает лини сетки ближе друг к другу вместе с элементами расположенными на них. Минимальное расстояние между двумя смежными линиями сетки зависит от элементов расположенных на этих линиях. Преимущество этого метода состоит в том, что для выполнения такой процедуры требуются простые и легко применяемые алгоритмы. Однако метод виртуальной сетки не дает хорошего результата в сравнении с методом графа ограничений.
Алгоритмы сжатия также можно классифицировать по уровню иерархии сжимаемой схемы. Если сжатие применяется к разным уровням иерархии топологии, то оно называется иерархическим сжатием. Любой из выше упомянутых методов может быть расширен до иерархического сжатия. Некоторые алгоритмы сжатия перед своей работой убирают все уровни иерархии. В таком случае не всегда возможно реконструировать иерархию после сжатия.
В этом разделе рассмотрим два метода одномерного сжатия: - сжатие с помощью графа ограничений - сжатие с помощью виртуальной сетки.
Алгоритмы одномерного сжатия применяются последовательно по X и Y осям до тех пор, пока сжатие возможно.
Рассмотрим сжатие с помощью графа ограничений [8]. Граф ограничений G = (V, Е) является взвешенным графом. Каждая вершина VGV представляет собой элемент. Каждое ребро представляет собой ограничение. Существует два типа ограничений, которые должны быть выполнены во время в процессе сжатия: ограничения па минимальные расстояния между элементами (в дальнейшем ограничения расстояний) ограничения для осуществления физических соединений элементов (в дальнейшем ограничения соединений)
Оба типа ограничений могут быть представлены графом ограничений. Ограничение расстояния между двумя элементами может быть представлено с помощью взвешенного ориентированного ребра между двумя вершинами, представляющими элементы, с весом равным минимальному расстоянию между ними. Например, если два элемента А и В должны быть дальше друг от друга как минимум на d единиц, то это правило можно записать следующим образом (пусть А находится слева от В): Bx Ax + d, (1.3) где Ах - х-координата элемента А. Такое неравенство представляется в графе ограничений как ребро из А в В с весом d (см. рис. 1.4). На рис. 1.5 показано ограничение соединения, которое требует, чтобы два элементы были не дальше друг от друга, чем на d единиц. Физическое соединение может быть представлено циклом из двух ребер, т.к. условие Ах - Вх d может быть записано двумя следующими ограничениями: Ах Вх - d и Ах Вх - d. Эти два ограничения представляются в графе как пара ограничений между Ах и Вх, каждое с весом равным -d.
Граф ограничений также содержит две дополнительных вершины, L (Left) и R (Right), которые представляют две физических границы левую и правую. Вершину L можно представить как источник графа ограничений, т.к. все остальные вершины находятся справа от L, другими словами ребра смежные с L только выходят из нее. Соответственно, R можно рассматривать как приемник графа. На рис. 1.6 дан пример графа ограничений включающего в себя вершины L и R.
В процессе сжатия во время перемещения элементов необходимо сохранить исходные электрические соединения. Большинство программ сжатия получают информацию об электрических соединениях из перекрытий элементов в исходной топологии. Рассмотрим два типа ограничений соединений и методы представления их в графе ограничений:
соединение типа проводник - блок: соединения блока с горизонтальным проводником, вертикальным проводником и широким вертикальным проводником проиллюстрированы на рис 1.7.
Пример процесса сжатия ячейки мультиплексора
Для решения задачи сжатия топологии СБИС будем применять метод имитации отжига. Происхождение названия метода объясняется тем, что идея позаимствована из области исследования процессов отжига металла. Если раскалить кусок металла, его внутренняя энергия достигнет высокого значения. Если охлаждение проводить медленно (отжиг), то с плавным уменьшением температуры тепловые колебания узлов решетки около состояния минимума энергии будут плавно уменьшаться, и в результате решетка будет иметь высокую упорядоченность, а энергия системы достигнет глобального минимума. Эта идея лежит в основе математической модели данного метода. Метод имитации отжига позволяет преодолеть локальные минимумы и искать глобальный минимум целевой функции. "Плата" за это - медленная работа алгоритма в случае большой размерности целевой функции, так как множество шагов по параметрам сети осуществляется в случайных, ненужных направлениях. Этот метод был предложен в 1983 году С. Кирпатриком, С. Гелатта и М. Веччи [2].
Чтобы применить моделирование отжига к задаче двумерного сжатия, требуется простое, легко модифицируемое представление. Разнообразие объектов: транзисторы, контакты, резисторы, проводники и т.д., и их размеров в СБИС делает поиск такого представления достаточно сложной задачей. Раннее использование моделирования отжига в молекулярной динамике подсказало идею представления, которое было использовано в данной работе. Элементарные элементы, называемые узлами - соединяются проводниками. Узлы - это объекты с жесткой структурой, которые передвигались бы в процессе отжига, если бы они были молекулами. Проводники, соединяющие узлы, - это растягиваемые объекты, которые постоянно трансформируются, следуя кратчайшему пути меду узлами, которые они соединяют, и учитывая все геометрические ограничения, применяемые к этим проводникам. Они представляют собой силы притяжения между узлами в процессе отжига.
Геометрические конструкторские ограничения описаны с помощью множества таблиц, отображающих технологию для данного представления. Ограничения, используемые в данных таблицах, применяются к конкретным узлам и проводникам. Уникальным свойством такого представления является тот факт, что ограничения разбиты на несколько независимых слоев. Каждому слою присваивается свой цвет, который используется при проверки соответствия ограничениям. Для проверки геометрических ограничений, необходима булева функция, для определенного слоя, соотносимого с двумя элементами. Проверка геометрических ограничений в каждом слое независима друг от друга. Таким образом, проверка ограничений сводится к монохромной задаче. Соответственно, геометрические конструкторские ограничения выполняются, когда они выполняются для каждого соответствующего слоя. Когда цепи вводятся с помощью графического интерфейса, проводится проверка на соответствие конструкторским ограничениям. Эти проверки также выполняются в процессе моделирования отжига. Более подробно геометрические ограничения описаны в Главе 3. Предлагаемый алгоритм управляется таблицами, описывающими технологию. Это удобно при изменении технологии. Учитывая, что структура данных табличная, таблицы можно изменить в соответствии с новыми технологическими требованиями, а топология изменится соответствующим образом в процессе отжига.
Множество объектов в СБИС сводится к двум типам примитивных элементов, как описано в Главе 3. Структура, которая будет использоваться много раз, будет создаваться с помощью модели узлов и проводников. Она может быть создана, когда это потребуется. Выстраивая модели, из двух примитивных компонентов, индивидуальные элементы каждой модели могут передвигаться независимо и, следовательно, модель будет гибкой в процессе отжига.
В процессе исследований одним из основных требований стала простота изменения структуры данных. Маленькие ячейки могут быть сжаты за достаточно небольшое количество компьютерных циклов с помощью стандартного представления, но это можно сделать и вручную. С ростом размеров ячеек эффективность ручного конструирования снижается и создание представления, которое уменьшит временные затраты на моделирование отжига, становится важной задачей.
Рассмотрим пример процесса сжатия ячейки мультиплексора 4 к 1. Логическая диаграмма мультиплексора показана на рисунке 2.3.
Транзисторная диаграмма для nMOS ячейки показана на рисунке 2.3. Входные сигналы обозначены цифрами от 1 до 4, а каналы выбора - буквами А и В. Выход ячейки обозначен словом out. Первоначальная модель ячейки показана на рисунке 2.4. Отметим, что элементы состоят из двух типов: круглых объектов, называемых узлами и соединительных проводников. Эти объекты называют примитивными элементами или примитивами. Узлы являются окончанием проводников. На рисунке 2.4 видно как проводники огибают препятствия.
Ячейка создается с использованием графического редактора, который позволяет помещать, передвигать и удалять элементы. Редактор не позволяет нарушать конструкторские геометрические ограничения. Устройство, которое назовем «моделью» - это набор проводников и узлов, который формирует транзистор или контакт.
Разработка метода описания слоев и конструкторских правил
СБИС состоит из нескольких слоев. В данной работе каждый слой ассоциируется с цветом. Будем сопоставлять слои с цветами.
В предыдущей части были определены примитивы для одного слоя или монохромного слоя. Эта часть расширит определения примитива для многих слоев. Каждый примитив будет иметь среди своих свойств объект Атрибуты, который определяет слои для примитивов в соответствии с размерами различных слоев.
Геометрические конструкторские правила для СБИС имеют два типа отношений для правил минимальной дистанции. Существует минимальная дистанция между объектами одного слоя и минимальная разделительной дистанции на разных слоях. Например, может существовать правило между красным объектом и зеленым объектом с определенной минимальной дистанцией. Необходимо привести межслойное правило к единственному слою. Это приведение достигается введением нового цвета для каждого межслоиного правила взаимодействия. Межслойное правило формулируется в новом цвете. Для всех объектов в обоих слоях новый цвет добавляется к объекту и ширина объекта для нового цвета будет максимальной шириной для взаимодействующих слоев для объекта. Например, пусть бардовый цвет представляет межслойное правило для красного и зеленого. Бардовый цвет добавляется ко всем объектам цвета красный и зеленый. Ширина бардового слоя для объекта устанавливается максимуму красного или зеленого. Минимальная дистанция для бардового - это межслойная минимальная дистанция для красного и зеленого цветов. Следовательно, бардовый цвет сводит правило межслоиного взаимодействия для красного и зеленого цветов к монохромному правилу бардового цвета.
Существует потенциальная проблема, если межслойное разделительное правило больше, чем нормальное разделительное правило. Этот необычный случай рассматривается путем игнорирования межслоиного правила, если существует правило в данном слое.
Цвета используются не только для процесса сжатия топологии СБИС. Цвета можно группировать по различным признакам, например группа цветов
ПроизвЦв[] будет использоваться для производства. Наименования цветов в нашей системе задается с помощью массива цветов ВсеЦвета[], где количество цветов -это ВсеЦвета. Цвета нумеруются от 1 до N. Необходимо знать соответствует ли цвет заданной группе. Каждая группа имеет булев список, проиндексированный номерами цветов. Можем протестировать на соответствие группе определенный цвет булевого массива с помощью Массив[НомерЦвета], где Массив - это имя булева массива. Логическая операция на булевом массиве - это операция над каждым соответствующим элементом.
Следующая таблица определяет использование глобальных цветов. Булев тип используется для определения наличия цвета в группе.
В данной таблице все массивы имеют размерность от 1 до N, где N - это количество цветов, используемое для описания конкретной технологии.
Рассмотрим определение правил для примитивов Объект Атрибуты описывает атрибуты для примитивов. Геометрические конструкторские правила для примитива заданы в объекте Атрибуты. Также задается контролирующая информация для графического редактора. Атрибуты описывает возможность использования данного правила для шлюза. Цвета, которые отображаются для пользователя в графическом редакторе, также описаны в этом разделе. Правила для определенной технологии также описаны в технологическом файле. Задаем принцип правила, представленного в разделе 3.2 с помощью списка:
Атрибуты(название, использЦв[], отобрЦв[], огрЦв[], размеры[], соединЦв[], создУзел, создШлюз, создПров, вес)
Атрибуты задает атрибуты для примитивов. Расширим количество цветов для правила, так чтобы оно соответствовало цветам, заданным булевым массивом использЦв[]. Булев массив отобрЦв[] задает цвета примитивам, которые показаны в процессе работы с графическим редактором. Не все цвета будут отображаться. Например, цвета, используемые для межслойного взаимодействия. Булев массив огрЦв[] определяет цвета для конструкторских геометрических правил. Массив вещественных чисел размеры[] определяет размер примитивов.
Поля, которые контролируют графическое редактирование - соединЦв, создУзел, создШлюз, создПров. Булев массив соединЦв[] позволяет другим примитивам соединяться с данным, если логическое «или» соответствующих примитивам соединЦв[] имеет какие-нибудь общие цвета. СоздУзел - это булев массив, который позволяет создавать узлы с помощью этого правила. СоздПров позволяет использовать правило для создания проводников. Ячейка, создаваемая в процессе редактирования будет иметь внешние связи с окружающим миром с помощью шлюзов. СоздШлюз - контролирует использования правила для шлюза.
Реальные названия и количество цветов контролируется в технологическом файле. Раздел о технологии nMOS опишет создание технологического файла для nMOS.
Геометрические конструкторские правила - это множество ограничивающих неравенств, необходимых для создания работающего чипа. Минимально возможная ширина, расширение, наложение и разделительные дистанции - это примеры геометрических конструкторских правил. Создатель технологического файла задает правила для определенной технологии, которую он собирается использовать. В предложенной структуре отсутствует концепция минимальной ширины для примитива, но для каждого типа примитивов описаны индивидуальные значения ширины. Ширина задается в технологическом файле с помощью объекта Атрибуты. Расширение - это минимальная дистанция расширения одного слоя относительно другого. Это расширение достигается с помощью определения модели с новым узлом. Расширение также иногда описывается методом наложения. Наложение - это минимальное значение, на которое один слой может быть больше другого. Правило может быть составлено, определяя ширину наложения равной ширине одного слоя плюс наложение. Ограничение разделения задается между двумя объектами, где сумма ширины двух объектов плюс минимальная разделительная дистанция больше или равна дистанции между двумя объектами. Ограничения могут быть наложены, как для объектов из разных слоев, так и для объектов из одного слоя.
Определение временной сложности алгоритмов модификации топологии
Большая часть времени затрачивается на поиск примитивов. Желательно уменьшить время поиска. Можно рассчитать ограничивающий прямоугольник для треугольников и алгоритма СВОБПУТЬ и тестировать только те примитивы, которые находятся внутри этой области. Это уберет некоторые из проверок, но порядок ВСА будет 0(N), где N- количество примитивов.
Проблема сокращения была бы значительно проще, если бы примитивы имели фиксированные размеры и имели фиксированные места расположения. Однако объекты могут быть разных размеров и могут находиться в любом месте ячейки. Поиск примитивов происходит внутри областей разных размеров. Воспользуемся троичным деревом с левой L, центральной С и правой R ветвями. Верхний узел дерева разделит ячейку на две части, где объекты слева от центральной разделительной линии, будут прикреплены к левой ветви дерева, объекты, пересекающие центральную разделительную линию, будут прикреплены к центральной ветви, а объекты справа от разделительной линии будут прикреплены к правой ветви. Каждая ветвь указывает на очередное дерево, которое снова разделит область пополам и пересчитает объекты.
Каждый узел дерева будет кортежем из (Sd, V, L, С, R, CI, Ch), где Sd определяет ось разделения, V определяет координату разделения, L, С, R - ветви узла, CI, Ch - координаты границы области центрального узла. Границы области центрального узла ограничивают поиск для центральной ветви до тех объектов, которые пересекают центральный канал. Каждый узел может разделить область ячейки по оси х или по оси у. Каждый узел разделяет оставшуюся область перпендикулярно к длине максимальной оси.
Предположим, что область поиска равна а и общая площадь ячейки равна А. Общее количество элементов равно N. Тогда время поиска составит 0(log(A)+k N a/A), (4.23)
Разработан метод модификации ячейки. Основные преимущества метода заключаются в том, что модифицированная ячейка не имеет нарушений конструкторских ограничений и имеет минимальную длину проводников.
Разработана методика описания изменений в топологии с помощью списков примитивов, что значительно упрощает расчет изменения целевой функции, а также отмену изменения топологии. Создан алгоритм перемещения узла, использующий разработанные алгоритмы определения возможности перемещения узла и построения очереди примитивов для модификации топологии.
Произведена теоретическая оценка временной сложности алгоритма перемещения узла. Основное время затрачивается на поиск примитивов находящихся в рассматриваемой области. При использовании троичного дерева ВСА сводится к 0(log(A)+k N a/A), где а - область поиска, А - общая площадь ячейки, N - общее количество элементов.
Существует такой класс комбинаторных задач, время решения которых растет экспоненциально с размером задачи. Такие задачи называют NP-полными. В [1] было показано, что двухмерное сжатие относится к этому классу задач. Исследования разных авторов показали, что моделирование отжига является эффективным методом для нахождения решений NP-полных задач близких к оптимальному решению.
Оптимизация методом имитации отжига соответствует подогреву и медленному охлаждению металла. Быстрое охлаждение металла не создает упорядоченную кристаллическую решетку. По этой причине, когда проводится отжиг, для создания сжатой структуры необходимо медленно охлаждать систему. Такой же подход необходим и для имитации отжига при сжатии топологии СБИС. Для нахождения глобального минимума, необходимо охлаждать систему медленно. При этом исследуются конфигурации топологий, которые не приводят к локальному минимуму. Это позволяет использовать метод с отходом, для принятия конфигураций которые немного хуже существующих. Слишком быстрое охлаждение соответствует последовательной оптимизации, которая принимает только наилучшие решения. Такой метод приводит к локальному минимуму. Только в случае отсутствия локального минимума, эти два алгоритма приведут к одинаковому результату.
Метод имитации отжига, предложенный Кикпатриком (Kirkpatrick) - это адаптированный метод Метрополиса (Metropolis). Он интенсивно используется при моделировании физических процессов в статистической механике. При этом усредненные свойства физической системы описываются как функция температуры. Для перехода к новому решению алгоритм использует распределение вероятности Больцмана е"Е/кт, где Е - это энергия системы, а к - это постоянная
Болыдмана. Алгоритм Метрополиса ртспользует N твердых сфер в двухмерном пространстве. Моделирование идет следующим образом. Первоначальная конфигурация создается случайным размещением сфер. Сфера выбирается случайным образом и передвигается в случайном направлении на небольшое расстояние, затем рассчитывается АЕ. Если АЕ 0 то это передвижение принимается. Если АЕ 0, то этот ход принимается с вероятностью е лн/кТ. Т.е.
генерируется случайное число г от 0 до 1. Если г е АЕ/кт, то ход принимается. Иначе сфера возвращается в предыдущую позицию. Затем процедура повторяется. Когда система достигает теплового равновесия, распределение различных состояний энергии будет соответствовать распределению Больцмана. В алгоритме Метрополиса не указано, какое время необходимо для достижения равновесия.
Адаптация алгоритма Метрополиса для оптимизации целевой функции Н следующая. Будем используем Хі для представления і-ой конфигурации. Стоимость (вес) конфигурации Xi - Н(Хі). Параметр Ті будет соответствовать тепловой энергии кТ.
Моделирование при определенной температуре будет протекать следующим образом. 1. Случайным образом выбирается новое состояние Xj, близкое к текущему состоянию Xi. Пусть АН = H(Xj) - H(Xi). 2. Если АН 0, то Xi = Xj. 3. Если АН 0, то если г е_лн/т , то Xi = Xj, где г - это равномерно -" -распределенное псевдослучайное число между 0 и 1. 4. Повтор шагов 1-3, до тех пор, пока условие останова, определяющее тепловое равновесие, не выполнится.
Метод имитации отжига работает следующим образом. Вначале система принимает хаотичный характер при высокой температуре. Температура достаточна высока, при условии, что еще большее ее повышение практически не изменит средней энергии. Затем систему медленно поэтапно (каждому этапу соответствует своя температура Ті) охлаждают до достижения теплового равновесия. Последовательность температур и условия останова называют расписанием отжига.
