Содержание к диссертации
Введение
Глава 1. Определения и понятия 9
1.1 Элементы теории графов, используемые в работе 9
1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры 15
1.3 Задача Краскала-Прима. 22
1.4 Выводы 29
Глава 2. Задача Штейнера 30
2.1 Свойства деревьев Штейнера в прямоугольной метрике 32
2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности 33
2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая 37
2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике ...41
2.5 Алгоритм выборки перспективных дополнительных точек 51
2.6 Оптимизация конфигурации дерева Штейнера... 68
2.7 Выводы 79
Глава 3. Глобальная трассировка 81
3.1 Постановка задачи и стандартная методика глобальной трассировки 1 81
3.2 Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа ... 88
3.3 Второй этап Pathfinder. Оптимизация распределения цепей по ребрам глобального графа 100
3.4 Третий этап Pathfinder. Волновая трассировка 109
3.5 Сравнение результатов Pathfinder с результатами других программ глобальной трассировки 111
3.6 Выводы 114
Заключение 116
Благодарности 117
- Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры
- Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности
- Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике
- Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа
Введение к работе
Актуальность работы
Серьезной проблемой при проектировании электронных устройств на современных КМОП-технологиях становится дефицит трассировочного ресурса. К нему приводит несколько факторов. Увеличение плотности транзисторов при тех же технологических размерах проектируемого устройства обусловливает рост числа электрических соединений на характерную относительную единицу площади (площадь одного транзистора). С увеличением слоев металлизации трассировочный ресурс каждого слоя уменьшается, поскольку увеличивается суммарная площадь сквозных переходов между слоями. С увеличением электронного оборудования возникает проблема падения напряжения питания - для ее решения увеличивают число переходов с верхних слоев земли/питания до уровня логических элементов, что значительно снижает трассировочный ресурс промежуточных (сигнальных) слоев металлизации. Хотя уменьшение минимальной ширины электрических проводников соответствует аналогичному уменьшению размеров транзисторов, однако на практике проблема прогнозирования и учета электромиграции приводит к тому, что растет число проводников с шириной, большей минимально возможной. Аналогичное утверждение справедливо для минимального расстояния между проводниками - для уменьшения взаимной емкости и обеспечения помехоустойчивости расстояние между проводниками критических цепей делают большим, чем минимально возможное.
Негативный эффект дефицита трассировочного ресурса связан
с тем, что в процессе трассировки nF оЧЧЙЙЗДЯЦЙШЙШЮйИ <<в
'М
обход» загруженных областей, а не «напрямую». Это обстоятельство приводит к увеличению величин задержек в цепях связи и уменьшению быстродействия электронного устройства в целом. Более того, высокая плотность логических элементов и, следовательно, трасс в определенных областях СБИС может привести к тому, что детальная трассировка при недостаточно качественной глобальной трассировке вообще не сможет быть осуществлена. Возможно, придется увеличить общую площадь кристалла или использовать дополнительные слои металлизации. И первый, и второй вариант снижают эффективность смены технологии и уменьшают надежность производства СБИС.
Немаловажным фактором также является время работы используемых алгоритмов. Проблемы, возникающие при проектировании СБИС на современных технологиях, приводят к тому, что изменяется сам процесс проектирования: из однопроходного он становится итерационным. Различные этапы, и в том числе процедура глобальной трассировки, повторяются неоднократно для достижения требуемых характеристик проектируемого устройства. Кроме того, высокая плотность трасс и общее увеличение числа электрических цепей приводят к тому, что итерационный процесс трассировки становится плохо сходящимся -значительно увеличивается общее число требуемых итераций.
Таким образом, актуальной становится разработка эффективных как с точки зрения качества получаемых решений, так и времени работы, методов глобальной трассировки компонентов СБИС в условиях дефицита трассировочного ресурса (высокой плотности трасс).
Цель исследования
Целью диссертационной работы являлось создание компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.
В соответствии с целью диссертационной работы были определены следующие задачи:
-
Исследование существующих алгоритмов построения минимальных связывающих деревьев, методов глобальной трассировки СБИС и анализ эффективности их применения для современных и перспективных КМОП технологий.
-
Разработка алгоритмического обеспечения для глобальной трассировки СБИС в условиях высокой плотности трасс.
-
Разработка методов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима при сохранении качества получаемых решений исходного алгоритма.
-
Разработка компонента САПР для глобальной трассировки СБИС.
Научная новизна работы
Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:
1. Разработка способов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима путем предварительной выборки перспективных точек Штейнера.
-
Разработка эффективных способов трансформации дерева Штейнера путем перестроения ограниченного множества ребер определенного типа.
-
Решение задачи построения начального леса деревьев Штейнера с учетом возможного распределения цепей по ребрам глобального графа.
-
Решение задачи оптимизации распределения цепей по ребрам глобального графа перед этапом перетрассировки путем многократного изменения начального разбиения многотерминальных цепей на двухтерминальные цепи.
Резул ътаты, выносимыеназащиту
В процессе проведения исследований автором получены следующие результаты:
-
Конструктивный алгоритм предварительной выборки перспективных точек Штейнера для алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.
-
Ряд итеративных методов трансформации дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет добиться максимального улучшения качества результатов совместной работы вышеуказанных алгоритмов при минимальных вычислительных затратах.
-
Вычислительная эффективность и качество получаемых решений предложенного комплекса алгоритмов доказана экспериментальными результатами, в том числе на тестовых примерах ESTEIN из стандартной библиотеки для задач исследования операций OR-Library.
-
Методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.
-
Эффективный комплексный итерационный алгоритм оптимизации укладки цепей по ребрам глобального графа.
-
На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Эффективность предложенных подходов подтверждена экспериментами на наборе тестовых примеров глобальной трассировки IBM, а также при сравнении с результатами работы программами глобальной трассировки Labyrinth и Chi.
Практическая ценность
Основным практическим результатом проведенных исследований стало создание программы глобальной трассировки Pathfinder. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.
Результаты исследований, выполненных по теме диссертации, нашли применение также в программном комплексе схемного редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Make Schematic для создания схемы электрических соединений. Данное программное обеспечение используется на этапе логического проектирования и позволяет строить графическое изображение схемы по списку соединений элементов.
Личный вклад автора
Предложенные в диссертации алгоритм выборки перспективных дополнительных точек, алгоритм трансформации дерева Штейнера с использованием ограниченного множества ребер определенного типа, а также метод использования алгоритмов построения леса деревьев с учетом возможного распределения цепей и метод использования алгоритмов оптимизации укладки цепей разработаны лично автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в ЗАО «МЦСТ») при личном участии автора. Компонент САПР Pathfinder для глобальной трассировки СБИС создан лично автором в рамках научно-исследовательского проекта Ariadna в течение 2003 года в Институте микропроцессорных вычислительных систем РАН.
Апробация
Результаты диссертационной работы докладывались на всероссийских и вузовских научных конференциях:
-
Российская научная конференция «Экономические информационные системы на пороге 21 века», Москва, октябрь 1999.
-
V Всероссийская научная конференция студентов и аспирантов, Таганрог, октябрь 2000.
-
XITV Научная конференция МФТИ, Москва, ноябрь 2001.
-
Юбилейная VIII Санкт-Петербургская международная конференция «Региональная информатика - 2002», Санкт-Петербург, ноябрь 2002.
-
Конкурс исследовательских проектов в области проектирования интегральных схем, проходивший при
поддержке МФТИ и представительства корпорации Intel в странах СНГ. Проект-победитель. 2003.
-
XLVI Научная конференция МФТИ, Москва, ноябрь 2003.
-
XXI Научно-техническая конференция в/ч 03425, Москва, декабрь 2003.
Кроме того, результаты диссертационной работы докладывались на научно-технических семинарах лаборатории САПР в ИМВС РАН и ЗАО «МЦСТ».
Публикации
По теме диссертации опубликовано 5 работ.
Структура и объемработы.
Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 129 страниц текста, 63 иллюстрации, 29 таблиц (включая 7 таблиц приложения) и приложение на 8 листах. Список литературы и ссьшок на ресурсы Internet насчитывает 61 наименование.
Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры
Графы, у которых присутствуют все возможные ребра, называются полными графами. Степень каждой вершины полного графа равна V — 1. Разреженный граф есть граф, средняя степень вершин которого d - это число, небольшое по сравнению с числом вершин графа; в противном случае граф называют плотным или насыщенным графом. Оценкой для d может служить или logP. В ряде случаев использование специальных структур данных позволяет конструировать для разреженных графов более эффективные алгоритмы решения тех или задач, чем для насыщенных графов.
Определение 1.4. Связный граф без циклов называется деревом. Остовное дерево (или остове связного графа есть подграф, который содержит все вершины этого графа и представляет собой дерево. Лесом называют множество деревьев.
Дерево, состоящее из V вершин, содержит F-Іребро. Дерево с корнем - это дерево, в котором один узел назначен корнем дерева. Для таких деревьев вводится понятие уровня (полагается, что корень дерева лежит на уровне 0).
Определение 1.5. Уровень узла в дереве на единицу выше уровня его родительского узла. Высота дерева-максимальный уровень всех узлов дерева.
Каждый узел (за исключением корня) имеет только один узел над ним, который называется его родительским узлом; узлы, расположенные непосредственно под данным узлом, называются его дочерними узлами. Узлы, не имеющие дочерних узлов, называются листьями.
Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. Простейшим типом такого дерева является бинарное дерево. Сбалансированное бинарное дерево - это такое дерево, на каждом уровне і которого находится Iі узлов, за исключением, возможно, самого нижнего уровня. На этом уровне, то есть на высоте дерева h, может находиться от одного до 2Н листьев.
Определение 1.6. Куча (англ. heap) - это абстрактная структура данных, состоящая из набора элементов, каждому из которых приписан некий ключ, для которого определена операция сравнения.
В дальнейшем вместо слова куча мы будем использовать для обозначения термина более привычный английский вариант - heap. Для /reo/7-структуры определены следующие основные операции: добавить новый элемент с заданным ключом в heap; найти элемент с минимальным ключом, не удаляя его из heap; найти элемент с минимальным ключом и удалить его из heap; Операции произвольного доступа к элементам Леяр-структуры, такие как изменить значения ключа элемента и удалить элемент, определены в том случае, если известна позиция данного элемента в Ле зр-структуре. Отметим, что все операции над элементами fteo/г-структуры за исключением операций, не изменяющих число элементов и не изменяющих значения ключей элементов, в общем случае требуют процедуры перестроения элементов heap-структуры, которую называют операцией обновить (перестроить) heap. В работе [1] предложена структура данных на основе сбалансированного бинарного дерева, в которой временная сложность всех операций не превьппает 0(logV), где V — число элементов в heap. При этом операция найти элемент с минимальным ключом требует 0(1) вычислений. Данная структура данных находит эффективное применение в большинстве алгоритмов, в ходе работы которых требуется находить минимальное значение некоторого динамического множества данных. Задача построения минимального связывающего дерева или дерева Краскала-Прима формулируется следующим образом. В связном графе G(V, Е) каждому ребру ееЕ приписывается мера с(е). Задача состоит в построении связного подграфа Т, содержащего все вершины G и такого, чтобы его полная мера была минимальной. В терминах теории графов задача построения дерева Краскала-Прима для некоторого множества точек, лежащих в плоскости, формулируется следующим образом. Множеству точек ставится в соответствие полный граф с числом вершин, равным числу точек; каждой вершине графа соответствует одна точка из исходного множества. Ребра графа взвешены;, вес ребра равен расстоянию между точками, инцидентными этому ребру. Задача построения дерева Краскала-Прима для исходного множества точек сводится к построению минимального остова на соответствующем полном графе. В задаче Штейнера на графе требуется найти наикратчайшее дерево Т, которое содержит заданное подмножество PczV вершин графа G(V,E). Другие вершины, принадлежащие V - Р, могут либо содержаться деревом Т, либо нет. Таким образом, задача Штейнера на графе эквивалентна нахождению минимального связывающего дерева произвольного подграфа G(V,E) графа G при условии с V с V, Е с Е. В задаче Штейнера на плоскости некоторое множество точек Р необходимо соединить отрезками линий так, чтобы сумма длин отрезков была минимальной; при этом допускается пересечение любых двух отрезков в точках вне заданного множества Р, называемых дополнительными точками или точками Штейнера. Исходное множество точек, множество дополнительных точек и множество отрезков, соединяющих исходные и дополнительные точки, называют деревом Штейнера на плоскости или просто деревом Штейнера. Кратчайшее или оптимальное дерево Штейнера - это дерево Штейнера, у которого сумма длин отрезков, входящих в него, минимальна. На рис. 1.1 изображено кратчайшее дерево Штейнера для четырех точек в эвклидовой (рис. 1.1а) и прямоугольной (рис. 1Л б) метриках. В данной работе задача построения дерева Штейнера рассматривается только для случая прямоугольной метрики, поскольку именно эта метрика используется в задачах САПР электронной аппаратуры.
Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности
В первом разделе данной главы приводятся основные свойства деревьев Штейнера в прямоугольной метрике. Все алгоритмы построения деревьев Штейнера, как точные, так и приближенные, в той или иной мере используют эти базовые свойства, поэтому автор счел необходимым вынести их в отдельный раздел, предваряющий последующее изложение материала.
Во втором разделе представлен обзор точных конструктивных алгоритмов построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности (до пяти точек включительно). Подробное описание этих, в общем-то, давно известных алгоритмов приводится по следующей причине. В следующей главе, посвященной проблеме глобальной трассировки в условиях повышенной плотности трасс, автором предложен ряд методик построения деревьев Штейнера с учетом текущего распределения проводников. В частности, для задач малой размерности на основе указанных алгоритмов предлагается способ выбора конфигураций деревьев, оптимальных по длине и максимально приемлемых для последующей трассировки.
В третьем разделе представлен обзор точных алгоритмов построения деревьев Штейнера в прямоугольной метрике для общего случая. Цель данного раздела показать, что точные алгоритмы, представляющие несомненный научный интерес, не находят практического применения из-за своей высокой временной сложности.
В четвертом разделе представлено несколько приближенных алгоритмов, имеющих с точки зрения автора, наибольшую практическую ценность для задач САПР электронной аппаратуры. Также в данном разделе представлены современные требования, накладываемые на алгоритмы построения деревьев Штейнера. Невысокой временной сложности и хороших, с точки зрения длины конструируемых деревьев, решений недостаточно для успешного проектирования СБИС на современных и, тем более, будущих технологиях. Актуальной становится проблема реализации в алгоритме сложной многопараметрической целевой функции. При построении дерева Штейнера для электрической цепи необходимо оценивать плотность распределения проводников, расстояние от источника до потребителя, задержки распространения сигналов и другие параметры. В частности, в разделе приведено описание алгоритма [36, 34], временные и качественные характеристики позволили успешно использовать его в коммерческих пакетах САПР СБИС \9r4.1 и v8r4.ll (1998 г.) компании Compass/Avanti. Однако «жесткость» этого алгоритма делает его использование в современных САПР как минимум нецелесообразным, а в будущих САПР просто неприемлемым. Идеальным с точки зрений требований актуальных задач проектирования является алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима [8], чье подробное описание также приведено в указанном разделе.
Пятый раздел посвящен вопросу ускорения алгоритма [8], поскольку по временным показателям он уступает не только многим приближенным алгоритмам, но даже появившемуся через несколько лет после него самому эффективному на текущий момент точному алгоритму [31]. Решения данной проблемы является одной из главных задач данной работы. Автором был разработан и реализован конструктивный комплексный алгоритм предварительной выборки точек. Этот алгоритм позволяет кардинальным образом сократить время работы алгоритма [8] за счет предварительной «отбраковки» тех точек, чья вероятность оказаться в оптимальном дереве Штейнера равна нулю или крайне мала. Четыре этапа работы предложенной методики позволяют сократить количество предполагаемых точек Штейнера в несколько раз, качество решений при этом остается сравнимым с результатом работы исходного алгоритма,
В шестом разделе автором предлагается ряд эффективных методов перестроения дерева Штейнера. Предлагается использовать их после процедуры выборки перспективных точек и работы основной части алгоритма [8]. Это позволяет исправить «огрехи» предварительного этапа, поскольку существует маленькая, но все же ненулевая вероятность исключить из рассмотрения точку, которая дала бы выигрыш в длине при включении в дерево Штейнера. Попутно исправляются недостатки основного алгоритма - исходное дерево трансформируется в дерево с лучшей, а зачастую, оптимальной конфигурацией. В разделе показано, что использование данной процедуры занимает лишь малую часть от времени, сэкономленного за счет удаления из рассмотрения неперспективных точек. Что касается качества получаемых решений, то, в среднем, результат, полученный для тестовых примеров ESTE1N из стандартной библиотеки OR-Library [17], отличается от оптимального [31] на 0.11 процента.
В седьмом разделе приведены выводы по результатам исследований и разработок, представленных в данной главе. Основные свойства деревьев Штейнера в прямоугольной метрике [18, 20] приводятся ниже: Свойство 2.1. Степень р исходной точки v, в оптимальном дереве Штейнера может принимать следующие значения: 1 p{v,) 4. Свойство 2.2. Степень р дополнительной точки s, в оптимальном дереве Штейнера может принимать следующие значения: 3 й p(ss) 4. Свойство 2.3. Число дополнительных точек в оптимальном дереве Штейнера не превосходит V - 2, где V— число исходных точек. Свойство 2.4. (Сетка Ханана). Если через каждую точку из исходного множества точек на плоскости провести вертикальные и горизонтальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных дополнительных точек Штейнера только точки пересечения полученной сетки линий. Из свойства 2.4 можно сделать следующее важное замечание. Пусть граф G построен так, что множество его вершин V является множеством пересечения некоторой сетки линий, а ребра графа соответствуют линиям сетки, соединяющим две точки пересечения. Тогда задача Штейнера в прямоугольной метрике для точек на плоскости переходит в задачу Штейнера на графе. Свойство 2.5- Пусть исходное множество точек разделяется на две части некоторой прямой вертикальной линией. Тогда, если слева (справа) от нее находится только одна точка, то точки Штейнера могут располагаться только на этой линии или справа (слева) от нее. Аналогичное утверждение справедливо для горизонтальных линий. В отличие от задачи Краскала-Прима задача построения дерева Штейнера является іУР-полной [11]. Однако для случая прямоугольной метрики для задач до пяти точек включительно существуют оптимальные конструктивные алгоритмы. Рассмотрим некоторые из них. Назовем ограничивающим прямоугольником минимальный прямоугольник, внутри и на границах которого располагаются все точки исходной задачи. Свойства, перечисленные в разделе 2.1, позволяют воспользоваться процедурой «обжатия». Исходная конфигурация точек поочередно «обжимается» с четырех сторон до тех пор, пока на каждой из сторон ограничивающего прямоугольника не окажутся как минимум две точки (рис. 2.1).
Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике
Одно из достоинств данного алгоритма заключается в том, что он обеспечивает точное решение для задач с размерностью до четырех точек включительно. Временные и качественные характеристики позволили успешно использовать его в коммерческих пакетах САПР СБИС компании Compass/Avanti. В частности, в последних версиях х9г4.1 и v8r4.ll (1998 год) данный алгоритм используется в качестве универсального инструмента для всех задач, требующих построения минимальных связывающих деревьев.
В табл. 2.4 представлены результаты работы алгоритма, полученные на машине Sun Ultra 5Т для задач с числом точек от б до 70 (тестовые наборы точек получены случайным образом по 10 тысяч на каждую размерность задачи). Приведены средний процент улучшения длины дерева Краскала-Прима (%) и среднее время счета одной задачи (/) в миллисекундах.
Следует отметить несколько недостатков алгоритма. Во-первых, с ростом числа точек качество решений снижается, что видно из табл. 2.4. Во-вторых, при неудачном расположении первых точек длина окончательного дерева Штейнера может значительно отличаться не только от оптимального значения, но и от длины дерева Краскала-Прима (рис. 2.14). И, .наконец, самый главный недостаток алгоритма заключается в его «жесткости». Трудно реализовать сложную многопараметрическую целевую функцию, поскольку на каждом шаге алгоритма для строго заданной точки упорядоченного списка выбирается строго заданная конфигурация ребра, соединяющего точку с деревом. Это является главным препятствием в использовании данного алгоритма для задачи глобальной трассировки в современных САПР, ведь при построении дерева Штейнера необходимо не только минимизировать суммарную длину дерева, но и учитывать другие факторы, в частности, равномерно распределять проводники по области трассировки.
Гораздо более предпочтительным с точки зрения реализации сложной целевой функции является представленный ниже алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима.
В работе [33] представлен алгоритм, использующий тот же подход, что и алгоритм [22], а именно преобразование дерева Краскала-Прима в дерево Штейнера. Данный алгоритм (iterated 1-Steiner algorithm) последовательно вводит в текущее дерево Краскала-Прима каждую из Vі дополнительных вершин решетчатого графа, строит новое дерево Краскала-Прима и запоминает полученный выигрыш в длине. После оценки всех дополнительных точек в текущее дерево включается точка с максимальным выигрышем. При этом чтобы избежать в процессе преобразования появления избыточных точек, необходимо учитывать, что точки Штейнера могут иметь, согласно свойству 2.2, только степень 3 и 4. Рис. 2.15 иллюстрирует вышесказанное.
В модифицированном варианте алгоритма (batched 1-Steiner algorithm) после вычисления выигрышей выделяется множество «независимых» точек с максимальным суммарным выигрышем, которые одновременно вводятся в текущее дерево. Две точки называются независимыми, если суммарный выигрыш от их независимого введения меньше или равен выигрышу от одновременного их введения. Использование предложенного подхода позволяет строить деревья Штейнера, длина которых в среднем на 11 процентов меньше длины деревьев Краскала-Прима для того же множества точек и не более чем на 0.5 процента больше оптимальной длины.
В работе [8] показано, каким образом можно кардинально сократить время работы алгоритма, избегая повторного построения дерева Краскала-Прима после попытки добавления в него очередной дополнительной точки. Предложенный для этой цели алгоритм {dynamic minimal Spanning tree maintenance) поочередно соединяет добавляемую точку с ее ближайшими соседями, а затем удаляет самое длинное ребро в возникающем цикле. При этом, как и раньше, достаточно ограничиться рассмотрением 4-х ближайших соседей - по одному в каждом из 4-х квадрантов, образованных прямыми линиями, проведенными через исходную точку под углами 45 и -45 градусов (рис. 2.16).
Помимо высокого качества получаемых решений другим главным достоинством алгоритма последовательного введения дополнительных точек является то, что в задаче глобальной трассировки данная эвристика позволяет реализовать сложную многопараметрическую целевую функцию. При введении дополнительной точки можно оценивать не только выигрыш в суммарной длине дерева, но и плотность распределения проводников, расстояние от источника до потребителя, задержки в линиях связи и другие параметры.
Что касается временных характеристик (табл. 2.5), то данный алгоритм уступает не только двум вышеописанным приближенным алгоритмам, но даже появившемуся через несколько лет после него самому эффективному на данный момент точному алгоритму [31].
Поэтому, несмотря на все выше перечисленные достоинства алгоритма, его невысокие временные показатели делают крайне сомнительным целесообразность его использования для решения задач САПР электронной аппаратуры. Разработка и реализация методов ускорения данного алгоритма является одной из главных задач данной работы.
Забегая вперед, отметим, что автором была предложена эффективная методика предварительной «отбраковки» неперспективных дополнительных точек [35], которая позволила сократить время работы исходного алгоритма в несколько раз (табл. 2.6). При этом качество получаемых решений осталось тем же самым. Подробному описанию данной методики посвящен следующий раздел, отметим только, что временные характеристики представленного алгоритма с использованием указанной методики позволяют успешно использовать его на этапе глобальной трассировки. В табл. 2.5 и 2.6 приведено среднее время счета одной задачи для рабочей станции Sun Sparc 2.
Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа
Актуальной проблемой при проектировании электронных устройств на современных КМОП-технологиях становится дефицит трассировочного ресурса. К этому приводит несколько факторов [46, 58, 59]. Увеличение плотности транзисторов при тех же технологических размерах проектируемого устройства обуславливает рост числа электрических соединений на характерную относительную единицу площади (площадь одного транзистора). С увеличением слоев металлизации трассировочный ресурс каждого слоя уменьшается, поскольку увеличивается суммарная площадь сквозных переходов между слоями. С увеличением электронного оборудования возникает проблема падения напряжения питания - для ее решения увеличивают число переходов с верхних слоев земли/питания до уровня логических элементов, что значительно снижает трассировочный ресурс промежуточных (сигнальных) слоев металлизации. Хотя уменьшение минимальной ширины электрических проводников соответствует аналогичному уменьшению размеров транзисторов, однако на практике проблема прогнозирования и учета электромиграции приводит к тому, что растет число проводников с шириной, большей минимально возможной. Аналогичное утверждение справедливо для минимального расстояния между проводниками - для уменьшения взаимной емкости и обеспечения помехоустойчивости расстояние между проводниками критических цепей делают большим, чем минимально возможное. Негативный эффект дефицита трассировочного ресурса связан с тем, что в процессе трассировки проводники назначаются «в обход» загруженных областей, а не «напрямую». Это обстоятельство приводит к увеличению величин задержек в цепях связи и уменьшению быстродействия электронного устройства в целом. Более того, высокая плотность логических элементов и, следовательно, трасс в определенных областях СБИС может привести к тому, что детальная трассировка при недостаточно качественной глобальной трассировке вообще не сможет быть осуществлена. Возможно, придется увеличить общую площадь кристалла или использовать дополнительные слои металлизации. И первый, и второй вариант снижают эффективность смены технологии и уменьшают надежность производства СБИС. Поэтому при переходе на нано технологии проблема прогнозирования и устранения дефицита ресурса трассировки становится одной из важнейших задач в процессе проектирования СБИС.
Недостатком стандартной методики глобальной трассировки, проводимой в условиях повышенной плотности трасс и дефицита трассировочного ресурса, является то, что задача равномерного распределения проводников решается на этапе перетрассировки, в то время как её необходимо начинать решать уже с этапа построения деревьев. Необходимо строить деревья для каждой электрической цепи с учетом возможной картины распределения цепей по ребрам глобального графа.
Вторым недостатком является то, что разбиение многотерминальной цепи на множество двухтерминальных цепей на этапе перетрассировки остается неизменным. Оптимизация переполнения глобального графа достигается за счет изменения конфигурации проводников между парами жестко зафиксированных точек. Это нецелесообразно, и исследования, проведенные ниже, это показали. Дерево должно динамически перестраиваться в процессе перетрассировки, разбиение цепи на пары точек должно меняться, а не оставаться фиксированным.
Для устранения указанных недостатков автором был разработан комплексный алгоритм глобальной трассировки. Данный алгоритм состоит из трех этапов. На первом этапе (см. раздел 3.2) для каждой цепи строится дерево Штейнера с учетом текущей картины распределения уже построенных деревьев по ребрам решетчатого графа. Причем эта процедура выполняется дважды. Причина очевидна: первые деревья строятся на очень разреженной картине распределения, поэтому их конфигурации с точки зрения переполнения не оптимальны. На следующем этапе (см. раздел 3.3) изменяются конфигурации тех деревьев, которые проходят по ребрам с ненулевым переполнением. Этот этап является совокупностью нескольких взаимодополняющих оптимизационных подходов и алгоритмов. Задача этого этапа — максимально уменьшить общее переполнение ребер графа за счет минимальной деградации суммарной длины всех деревьев. Главное отличие от стандартной методики заключается в том, что улучшение в переполнении достигается не за счет изменения конфигурации проводника между какими-то двумя жестко зафиксированными точками, а за счет того, что дерево частично или даже полностью перестраивается, разбиение цепи на пары точек постоянно изменятся. Это позволяет достичь гораздо лучших результатов с минимальными потерями в суммарной длине. В качестве заключительного этапа (см. раздел 3.4) используется волновая трассировка. Предложенный комплексный алгоритм был реализован автором в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna [37]. Данный проект ведется сотрудниками ИМВС РАН с января 2003 года в сотрудничестве с Intel Strategic CAD Lab. В табл. 3.1 приведены результаты работы трех программ глобальной трассировки Pathfinder, Labyrinth [41] и СЫ [60] на тестовых наборах IBM. Labyrinth -свободно распространяемая программа, разработанная в 2000 году в отделении электронного и компьютерного проектирования Калифорнийского Университета [56]. СЫ - самая современная из известных программ глобальной трассировки (впервые представлена на конференции DAC в июне 2003 года). Более подробно Labyrinth и Chi будут представлены ниже в соответствующем разделе. Отметим только лишь, что в Labyrinth и в Chi реализована стандартная методика глобальной трассировки со всеми указанными недостатками.
