автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры

УДК 004.896 На права^рукописи

Рыженко Николай Владимирович

Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры

05.13.12 Системы автоматизации проектирования (вычислительная техника)

Автореферат

диссертации на соискание учёной степени кандидата технических наук

Москва - 2004 г.

Работа выполнена в Институте микропроцессорных вычислительных систем РАН.

Научный руководитель: кандидат технических наук

Жмурин Андрей Валентинович

Официальные оппоненты: доктор технических наук, профессор

Яицков Александр Сергеевич

кандидат технических наук Кречетов Евгений Георгиевич

Ведущая организация: ОАО «НИИВК имени М.А. Карцева»

Защита состоится 10 июня 2004 г. в 14:00 на заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 119435, г. Москва, Б. Саввинский переулок, д. 14.

С диссертацией можно ознакомиться в библиотеке Института микропроцессорных вычислительных систем РАН.

Автореферат разослан О-'лР^'А^ 2004 г.

Учёный секретарь

диссертационного совета |

д.ф.-м.н., профессор лМихайлюк Михаил Васильевич

Общая характеристика работы

Актуальность работы

Серьезной проблемой при проектировании электронных устройств на современных КМОП-технологиях становится дефицит трассировочного ресурса. К нему приводит несколько факторов. Увеличение плотности транзисторов при тех же технологических размерах проектируемого устройства обусловливает рост числа электрических соединений на характерную относительную единицу площади (площадь одного транзистора). С увеличением слоев металлизации трассировочный ресурс каждого слоя уменьшается, поскольку увеличивается суммарная площадь сквозных переходов между слоями. С увеличением электронного оборудования возникает проблема падения напряжения питания - для ее решения увеличивают число переходов с верхних слоев земли/питания до уровня логических элементов, что значительно снижает трассировочный ресурс промежуточных (сигнальных) слоев металлизации. Хотя уменьшение минимальной ширины электрических проводников соответствует аналогичному уменьшению размеров транзисторов, однако на практике проблема прогнозирования и учета электромиграции приводит к тому, что растет число проводников с шириной, большей минимально возможной. Аналогичное утверждение справедливо для минимального расстояния между проводниками - для уменьшения взаимной емкости и обеспечения помехоустойчивости расстояние между проводниками критических цепей делают большим, чем минимально возможное.

Негативный эффект дефицита трассировочного ресурса связан

с тем, что в процессе трассировки «в

«ИКЛИОТЕКЛ

обход» загруженных областей, а не «напрямую». Это обстоятельство приводит к увеличению величин задержек в цепях связи и уменьшению быстродействия электронного устройства в целом. Более того, высокая плотность логических элементов и, следовательно, трасс в определенных областях СБИС может привести к тому, что детальная трассировка при недостаточно качественной глобальной трассировке вообще не сможет быть осуществлена. Возможно, придется увеличить общую площадь кристалла или использовать дополнительные слои металлизации. И первый, и второй вариант снижают эффективность смены технологии и уменьшают надежность производства СБИС.

Немаловажным фактором также является время работы используемых алгоритмов. Проблемы, возникающие при проектировании СБИС на современных технологиях, приводят к тому, что изменяется сам процесс проектирования: из однопроходного он становится итерационным. Различные этапы, и в том числе процедура глобальной трассировки, повторяются неоднократно для достижения требуемых характеристик проектируемого устройства. Кроме того, высокая плотность трасс и общее увеличение числа электрических цепей приводят к тому, что итерационный процесс трассировки становится плохо сходящимся -значительно увеличивается общее число требуемых итераций.

Таким образом, актуальной становится разработка эффективных как с точки зрения качества получаемых решений, так и времени работы, методов глобальной трассировки компонентов СБИС в условиях дефицита трассировочного ресурса (высокой плотности трасс).

Цель исследования

Целью диссертационной работы являлось создание компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В соответствии с целью диссертационной работы были определены следующие задачи:

1. Исследование существующих алгоритмов построения минимальных связывающих деревьев, методов глобальной трассировки СБИС и анализ эффективности их применения для современных и перспективных КМОП технологий.

2. Разработка алгоритмического обеспечения для глобальной трассировки СБИС в условиях высокой плотности трасс.

3. Разработка методов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима при сохранении качества получаемых решений исходного алгоритма.

4. Разработка компонента САПР для глобальной трассировки СБИС.

Научная новизна работы

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:

1. Разработка способов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима путем предварительной выборки перспективных точек Штейнера.

2. Разработка эффективных способов трансформации дерева Штейнера путем перестроения ограниченного множества ребер определенного типа.

3. Решение задачи построения начального леса деревьев Штейнера с учетом возможного распределения цепей по ребрам глобального графа.

4. Решение задачи оптимизации распределения цепей по ребрам глобального графа перед этапом перетрассировки путем многократного изменения начального разбиения многотерминальных цепей на двухтерминальные цепи.

Результаты, выносимыеназащиту

В процессе проведения исследований автором получены следующие результаты:

1. Конструктивный алгоритм предварительной выборки перспективных точек Штейнера для алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

2. Ряд итеративных методов трансформации дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет добиться максимального улучшения качества результатов совместной работы вышеуказанных алгоритмов при минимальных вычислительных затратах.

3. Вычислительная эффективность и качество получаемых решений предложенного комплекса алгоритмов доказана экспериментальными результатами, в том числе на тестовых примерах Б8ТБШ из стандартной библиотеки для задач исследования операций ОК-ЫЬгагу.

4. Методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.

5. Эффективный комплексный итерационный алгоритм оптимизации укладки цепей по ребрам глобального графа.

6. На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Эффективность предложенных подходов подтверждена экспериментами на наборе тестовых примеров глобальной трассировки IBM, a также при сравнении с результатами работы программами глобальной трассировки Labyrinth и Chi.

Практическая ценность

Основным практическим результатом проведенных исследований стало создание программы глобальной трассировки Pathfinder. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

Результаты исследований, выполненных по теме диссертации, нашли применение также в программном комплексе схемного редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Make Schematic для создания схемы электрических соединений. Данное программное обеспечение используется на этапе логического проектирования и позволяет строить графическое изображение схемы по списку соединений элементов.

Личный вклад автора

Предложенные в диссертации алгоритм выборки перспективных дополнительных точек, алгоритм трансформации дерева Штейнера с использованием ограниченного множества ребер определенного типа, а также метод использования алгоритмов построения леса деревьев с учетом возможного распределения цепей и метод использования алгоритмов оптимизации укладки цепей разработаны лично автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в ЗАО «МЦСТ») при личном участии автора. Компонент САПР Pathfinder для глобальной трассировки СБИС создан лично автором в рамках научно-исследовательского проекта Ariadna в течение 2003 года в Институте микропроцессорных вычислительных систем РАН.

Апробация

Результаты диссертационной работы докладывались на всероссийских и вузовских научных конференциях:

1. Российская научная конференция «Экономические информационные системы на пороге 21 века», Москва, октябрь 1999.

2. V Всероссийская научная конференция студентов и аспирантов, Таганрог, октябрь 2000.

3. XLIV Научная конференция МФТИ, Москва, ноябрь 2001.

4. Юбилейная VIII Санкт-Петербургская международная конференция «Региональная информатика - 2002», Санкт-Петербург, ноябрь 2002.

5. Конкурс исследовательских проектов в области проектирования интегральных схем, проходивший при

поддержке МФТИ и представительства корпорации Intel в странах СНГ. Проект-победитель. 2003.

6. XLVI Научная конференция МФТИ, Москва, ноябрь 2003.

7. XXI Научно-техническая конференция в/ч 03425, Москва, декабрь 2003.

Кроме того, результаты диссертационной работы докладывались на научно-технических семинарах лаборатории САПР в ИМВС РАН и ЗАО «МЦСТ».

Публикации

По теме диссертации опубликовано 5 работ. Структура и объем работы.

Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 129 страниц текста, 63 иллюстрации, 29 таблиц (включая 7 таблиц приложения) и приложение на 8 листах. Список литературы и ссылок на ресурсы Internet насчитывает 61 наименование.

Содержание работы

Во. введении характеризуются, цель исследования, актуальность работы, её практическая ценность.

В первой главе определены основные понятия, необходимые для изложения результатов диссертационной работы. Выполнен анализ места минимальных связывающих деревьев в задачах САПР электронной аппаратуры. Сформулированы критерии использования тех или иных алгоритмов оценки длин и построения минимальных связывающих деревьев для решения следующих задач:

• глобальная трассировка;

• оценка длин межсоединений на этапе размещения;

• автоматическая визуализация электрических схем;

• тестопригодное проектирование.

Систематизированы результаты, полученные в области

построения минимальных связывающих деревьев. без дополнительных вершин (деревьев Краскала-Прима). Приведена оценка временной сложности алгоритмов в зависимости от использования различных структур данных. Сформулировано свойство единственности, позволяющее строить минимальные связывающие деревья с ограничением на максимальную степень точки.

Вторая глава диссертационной работы посвящена задаче Штейнера в приложении к задаче глобальной трассировки СБИС. Приводятся основные свойства деревьев Штейнера в прямоугольной метрике. Представлены точные конструктивные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности (до пяти точек включительно). Проведен анализ точных алгоритмов построения деревьев Штейнера в

прямоугольной метрике для общего случая. Показано, что точные алгоритмы, представляющие несомненный научный интерес, неприменимы из-за своей высокой временной сложности.

Далее проанализированы несколько приближенных алгоритмов, представляющих наибольшую практическую ценность для задач САПР электронной аппаратуры. К этим алгоритмам относятся:

• алгоритм последовательных локальных преобразований дерева Краскала-Прима в дерево Штейнера;

• конструктивный алгоритм построения дерева Штейнера «слева направо»;

• эвристический алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима.

Проанализированы современные требования, накладываемые на алгоритмы построения деревьев Штейнера. Невысокой временной сложности и хороших, с точки зрения длины конструируемых деревьев, решений недостаточно для успешного проектирования СБИС на современных и, тем более, перспективных технологиях. Актуальной становится проблема реализации в алгоритме сложной многопараметрической целевой функции. При построении дерева Штейнера для электрической цепи необходимо оценивать плотность распределения проводников, расстояние от источника до потребителя, задержки распространения сигналов, взаимовлияние сигналов (помехи) и другие параметры.

Показано, что наиболее предпочтительным с точки зрения реализации сложной целевой функции является алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима. Данный алгоритм последовательно вводит в текущее дерево Краскала-Прима каждую из V дополнительных

вершин решетчатого графа, где V - число точек задачи, строит новое дерево Краскала-Прима и запоминает полученный выигрыш в длине. После оценки всех дополнительных точек в текущее дерево включается точка с максимальным выигрышем (рис. 1).

а б в

Рис. 1. Последовательное введение дополнительных точек в

дерево Краскала-Прима.

В модифицированном варианте алгоритма после вычисления выигрышей выделяется множество «независимых» точек с максимальным суммарным выигрышем, которые одновременно вводятся в текущее дерево. Две точки называются независимыми, если суммарный выигрыш от их независимого выигрыша меньше или равен выигрышу от одновременного их введения. Использование предложенного подхода позволяет строить деревья Штейнера, длина которых в среднем на 11 процентов меньше длины деревьев Краскала-Прима для того же множества точек и не более чем на 0.5 процента больше оптимальной длины.

Можно кардинально сократить время работы алгоритма, избегая повторного построения дерева Краскала-Прима после попытки добавления в него очередной дополнительной точки. Предложенный для этой цели алгоритм поочередно соединяет добавляемую точку с ее ближайшими соседями, а затем удаляет самое длинное ребро в возникающем цикле. При этом достаточно ограничиться рассмотрением 4-х ближайших соседей - по одному в

каждом из 4-х квадрантов, образованных прямыми линиями, проведенными через исходную точку под углами 45 и -45 градусов.

Помимо высокого качества получаемых решений, другим главным достоинством алгоритма последовательного введения дополнительных точек является то, что в задаче глобальной трассировки данная эвристика позволяет реализовать сложную многопараметрическую целевую функцию. При введении дополнительной точки можно оценивать не только выигрыш в суммарной длине дерева, но и плотность распределения проводников, расстояние от источника до потребителя, задержки в линиях связи и другие параметры.

Что касается временных характеристик, то данный алгоритм уступает даже появившемуся через несколько лет после него самому эффективному на данный момент точному алгоритму. Разработка способов ускорения данного алгоритма при сохранении качества получаемых решений является одной из задач данной работы.

Автором был разработан и реализован конструктивный комплексный алгоритм предварительной «отбраковки» тех дополнительных точек, чья вероятность оказаться в оптимальном дереве Штейнера равна нулю или крайне мала. Четыре этапа работы алгоритма позволяют сократить количество предполагаемых точек Штейнера в несколько раз. Это позволяет многократно уменьшить время работы исходного алгоритма при сохранении качества получаемых решений.

Алгоритм выборки перспективных дополнительных точек составляют четыре этапа:

1. процедура «обжатия»;

2. процедура исключения угловых точек;

3. использование дерева Краскала-Прима;

4. использование прямоугольников, содержащих три и только три глобальных точки.

На первом этапе проводится процедура «обжатия» исходного множества точек. Исходная конфигурация точек поочередно «обжимается» с четырех сторон до тех пор, пока на каждой из сторон ограничивающего прямоугольника не окажутся как минимум 2 точки (рис. 2). В некоторых случаях данная процедура может привести к снижению размерности исходной задачи, при этом фаза последовательного введения дополнительных точек может даже и не потребоваться, поскольку для задач с размерностью до 5-ти точек включительно существуют точные конструктивные алгоритмы построения деревьев Штейнера.

Рис. 2. Сокращение числа возможных дополнительных точек в результате процедуры «обжатия».

В качестве модели для полученной «обжатой» сетки Ханана используется двумерный массив. В программной реализации значения элементов массива, соответствующих глобальным точкам, равны индексам этих точек (предлагается индексация от 0 до V-1,

где V - число точек после обжатия). Элементы массива, соответствующие дополнительным точкам, принимают некоторое начальное значение, например, -1.

На втором этапе из рассмотрения исключаются те дополнительные точки, которые лежат вне области, «натянутой» на крайние глобальные точки каждого ребра ограничивающего прямоугольника и глобальные точки, лежащие внутри прямоугольника. Будем называть такие дополнительные точки угловыми, а остальные точки, соответственно, внутренними (рис. 3). В работе показано, что угловые дополнительные точки не могут присутствовать ни в одном оптимальном дереве Штейнера.

Рис. 3. Разделение дополнительных точек на угловые и внутренние.

На третьем этапе на множестве глобальных точек строится дерево Краскала-Прима с использованием реальных расстояний между точками. После этого для каждого ребра этого дерева в массиве проводится следующая операция: в минимальном ограничивающем прямоугольнике, построенном на концевых точках ребра, значения всех элементов (если это не глобальная точка и не угловая точка, исключенная на втором этапе) уменьшаются на 2. На рис. 4 показан пример процедуры для ребер (3,7) и (7,1).

Рисунок 4. Использование дерева Краскала-Прима для оценки точекШтейнера.

На четвертом этапе для оценки дополнительных точек используется следующая процедура. Для каждой глобальной точки ищется множество минимальных прямоугольников, каждый из которых содержит эту точку и две и только две другие глобальных точки. Для каждой тройки точек, полученной таким образом, определяется точка Штейнера. Если это не глобальная точка, и не точка, не исключенная на втором этапе, тогда ее значение уменьшается на две единицы.

Самый простой и самый неэффективный алгоритм нахождения таких прямоугольников - это полный перебор точек. Ясно, что этот алгоритм имеет кубическую временную сложность. Автором был разработан и реализован алгоритм с квадратичной временной сложностью. Поиск троек точек осуществляется с использованием вышеописанного двумерного массива. Поиск начинается от исходной точки и идет поочередно по четырем направлениям: вверх, вниз, влево и вправо.

В окончательную выборку перспективных дополнительных точек попадают точки со значением < - 5.

Экспериментальные исследования показали, что процедура выборки перспективных точек позволяет в несколько раз сократить время работы алгоритма последовательного введения

дополнительных точек в дерево Краскала-Прима. В табл. 1 приведено отношение времени работы исходного алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима к времени работы того же алгоритма с использование предложенной процедуры «отбраковки» точек.

Табл. 1. Сокращение времениработы исходного алгоритма.

Что касается качества получаемых решений, то улучшение дерева Краскала-Прима для модифицированного алгоритма в среднем на несколько сотых долей процента лучше, чем тот же самый показатель для исходного алгоритма. Причем эта тенденция отмечается на задачах всех размерностей. Этот факт объясняется тем, что, сокращая число дополнительных точек и рискуя «забраковать» точку, которая обязательно должна быть в точном решении, мы тем самым сокращаем число возможных локальных минимумов алгоритма. Попав в такой минимум, алгоритм уже не может выйти из него, добавляя поочередно точки. В итоге, в среднем, для указанных стратегий выборки получается более качественный результат. Это можно отнести к достижениям предложенной методики выборки перспективных дополнительных точек, изначально разрабатываемой для ускорения работы известного алгоритма.

В диссертации предложен ряд эффективных методов перестроения дерева Штейнера для использований их после процедуры выборки перспективных точек и работы основной части алгоритма последовательного введения точек для решения второй задачи данной работы, а именно гарантированного обеспечения

качества исходного алгоритма. Предложен комплекс алгоритмов трансформации дерева Штейнера, позволяющий исправить «огрехи» предварительного этапа, поскольку существует небольшая вероятность исключения из рассмотрения точки, которая дала бы выигрыш в длине при включении в дерево Штейнера. Попутно исправляются недостатки основного алгоритма - исходное дерево трансформируется в дерево с лучшей, а зачастую оптимальной,-конфигурацией.

Исследования показали специфический характер возникающих отклонений от оптимальной конфигурации дерева Штейнера при совместной работе алгоритма выборки перспективных точек и алгоритма введения точек в дерево Краскала-Прима, что позволяет воспользоваться ограниченным множеством ребер особого типа для работы предложенных алгоритмов трансформации дерева. Это так называемые «свободные» ребра и ребра, инцидентные дополнительным вершинам. Динамическое перестроение дерева занимает лишь малую часть от времени, сэкономленного за счет удаления из рассмотрения неперспективных точек. Что касается качества получаемых решений, то, в среднем, результат, полученный для тестовых примеров ESTEIN из стандартной библиотеки OR-Library, отличается от оптимального на 0.11 процента.

Третья глава диссертационной работы посвящена решению проблемы глобальной трассировки в условиях высокой плотности трасс. Формулируется математическая модель глобальной трассировки, описывается стандартная методика глобальной трассировки, отмечается её актуальность и анализируются недостатки.

Функцией, определяющей качество глобальной трассировки, есть переполнение глобального графа. Эта величина показывает

суммарное превышение максимально допустимого числа трасс, назначенных в ребра глобального графа. Минимизация переполнения глобального графа — основная задача глобальной трассировки.

Недостатком стандартной методики глобальной трассировки, проводимой в условиях повышенной плотности трасс и дефицита трассировочного ресурса, является то, что задача равномерного распределения проводников решается на этапе перетрассировки, в то время как её необходимо начинать решать уже с этапа построения деревьев. Необходимо строить деревья для каждой электрической цепи с учетом возможной картины распределения цепей по ребрам глобального графа.

Вторым недостатком стандартной методики глобальной трассировки является то, что разбиение многотерминальной цепи на множество двухтерминальных цепей на этапе перетрассировки остается неизменным. Оптимизация функции переполнения глобального - графа достигается за счет изменения конфигурации проводников между парами жестко зафиксированных точек. Это нецелесообразно, и проведенные исследования это показали. Дерево должно динамически перестраиваться в процессе перетрассировки, разбиение цепи на пары точек должно меняться, а не оставаться фиксированным.

Устранение указанных недостатков является следующей задачей данной работы. Для ее решения автором был разработан 3-х этапный комплексный алгоритм глобальной трассировки.

На первом этапе для каждой электрической цепи строится дерево Штейнера с учетом текущей картины распределения уже построенных деревьев по ребрам решетчатого глобального графа. Для задач малой размерности (до пяти точек включительно) используются точные алгоритмы. Среди нескольких возможных

оптимальных конфигураций дерева Штейнера выбирается та, которая вносит минимальное переполнение в текущую картину распределения цепей по ребрам глобального графа. Показано, что если имеется несколько равноценных вариантов конфигураций дерева Штейнера, то необходимо выбирать наиболее эластичный вариант. Понятие эластичности прямоугольных деревьев Штейнера подробно характеризуется и анализируется в работе.

Для задач большой размерности (свыше пяти точек) используется алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима. При введении очередной точки оцениваются выигрыш в длине дерева, переполнение глобального графа, величина текущего заполнения ребер глобального графа и эластичность дерева. На основании результатов экспериментальных исследований делается вывод, что алгоритм последовательного введения дополнительных точек в дерево Краскала-Прима является наиболее предпочтительным для задачи глобальной трассировки как с точки зрения качества получаемых решений, так и с точки зрения возможности реализации в рамках алгоритма сложной многопараметрической целевой функции.

Процедура построения начального леса деревьев выполняется несколько раз. Последовательно перестраиваются все деревья Штейнера, проходящие по переполненным ребрам глобального графа. Это процедура значительно снижает переполнение глобального графа. При начальном построении первые деревья строятся на очень разреженной картине распределения цепей, поэтому их конфигурации с точки зрения переполнения глобального графа не оптимальны.

На следующем этапе изменяются конфигурации тех деревьев, которые проходят по ребрам с ненулевым переполнением. Этот этап

является совокупностью нескольких взаимодополняющих оптимизационных подходов и алгоритмов. Часть алгоритмов - это представленные выше алгоритмы трансформации деревьев, отличающиеся лишь целевой функцией. Задача второго этапа — максимально уменьшить общее переполнение ребер графа за счет минимального увеличения суммарной длины всех деревьев. В отличие от стандартной методики глобальной трассировки улучшение в переполнении достигается не за счет изменения конфигурации проводника между какими-то двумя жестко зафиксированными точками, а за счет того, что дерево частично или даже полностью перестраивается, разбиение цепи на пары точек постоянно изменятся. Это позволяет значительно уменьшить переполнение глобального графа с минимальными потерями в суммарной длине.

В качестве заключительного этапа используется волновая трассировка.

Предложенный комплексный алгоритм глобальной трассировки был реализован автором в программе Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna. Данный проект ведется сотрудниками ИМВС РАН с января 2003 года в сотрудничестве с Intel Strategic CAD Lab.

В табл. 2 приведены результаты работы трех программ глобальной трассировки Pathfinder, Labyrinth и Chi на тестовых наборах IBM. Labyrinth - свободно распространяемая программа, разработанная в 2000 году в отделении электронного и компьютерного проектирования Калифорнийского университета. Chi - самая современная из известных программ глобальной трассировки (впервые представлена на конференции DAC в июне 2003 года). В

Labyrinth и Chi реализована стандартная методика глобальной трассировки со всеми указанными недостатками.

Окончательная суммарная длина всех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14-20 процентов, у Chi на 1-3 процента. Однако главный критерий - это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Табл. 2. СравнениерезультатовLabyrinth, Chi и Pathfinder

ÄLab - отличие суммарной длины Pathfinder от суммарной длины Labyrinth в процентах к длине Labyrinth.

Дан - отличие суммарной длины Pathfinder от суммарной длины Chi в процентах к длине Chi.

тест Переполнение глобального графа Суммарная длина леса деревьев Штейнера Аиь До..

Lab. Chi Path. Lab. Chi Path.

ibmOl 398 189 10 76517 64355 65434 14.48 -1.67

ibm02 492 66 0 204734 175368 169850 17.03 3.14

ibm03 209 7 0 185194 149695 146365 20.96 2.22

ibm04 882 411 21 196920 170440 169793 13.77 0.37

ibm05 251 - 0 689671 - 410217 40.51 -

ibm06 834 16 0 346137 284700 278127 19.64 2.30

ibm07 697 251 0 449213 373739 366556 18.40 1.92

ibm08 665 71 0 469666 410507 404071 13.96 1.56

ibm09 505 35 0 481176 420691 413724 14.01 1.65

ibmlO 588 116 0 679606 589503 580208 14.62 1.57

Выводы по результатам диссертации

Основной результат диссертационной работы заключается в разработке алгоритмической основы и создания компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В процессе исследования автором были получены следующие результаты:

1. Разработан алгоритм оценки перспективных дополнительных точек. Использование данного алгоритма позволяет в несколько раз сократить время работы алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

2. Временные и качественные характеристики предложенного модифицированного алгоритма позволяют успешно использовать его в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna. Также предложенный алгоритм нашел применение в программном комплексе редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Маке Schematic.

3. Разработан и практически реализован алгоритм динамического перестроения дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет за приемлемое время значительно улучшить качественные показатели модифицированного алгоритма. Экспериментально доказано, что процедура перестроения дерева использует лишь

незначительную часть времени, сэкономленного за счет «отбраковки» неперспективных точек. Высокое качество получаемых решений подтверждено экспериментально на тестовых примерах ESTEIN из стандартной библиотеки OR-Library. Данный тестовый набор представляет собой совокупность задач с размерностью 10,20,30,40, 50,60,70, 90, 100, 250 и 500 точек - по 15 задач на каждую размерность. Отличие от оптимального значения в среднем для всех задач составляет 0.11 процента.

4. Разработан комплекс алгоритмов и методов для глобальной трассировки СБИС в условиях повышенной плотности трасс.

5. Предложенный комплекс алгоритмов реализован лично автором в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

6. Проведено сравнение результатов работы Pathfinder и других программ глобальной трассировки Labyrinth и Chi на тестовых примерах IBM. Суммарная длина всех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14-20 процентов, у Chi на 1-3 процента. Однако главный критерий -это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Публикации по теме диссертации

1. ИрбенекВ.С, РыженкоН.В. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. Сб. докладов российской научной конференции «Экономические информационные системы на пороге 21 века», Москва, 1999, стр. 361-366.

2. Рыженко Н.В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 3, Труды ИМВС РАН, Москва, 2002, стр. 48-61.

3. Ирбенек В.С, Рыженко Н.В. Алгоритмы проектирования топологии электрических соединений в САПР электронной аппаратуры. «Зарубежная радиоэлектроника. Успехи современной радиоэлектроники», №7,2002, стр. 71-79.

4. Рыженко Н.В. Задача построения дерева Штейнера для этапа глобальной трассировки. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 4, Труды ИМВС РАН, Москва, 2003, стр. 96-105.

5. Рыженко Н.В. Программа глобальной трассировки Pathfinder. Тезисы докладов XXI Научно-технической конференции в/ч 03425, Москва, декабрь2003.

Сдано в печать 27.04.04 Формат 60x90/16 Объем 1,5 печ. л Тираж 60 экз. Зак. № 9

Отпечатано в ООО "Эдэль-М" 105005, г.Москва, ул.Бауманская д.43/1

JH-SÔ 1 в

8 i 9 8 - ai

Введение.

Глава 1. Определения и понятия.~.

1.1 Элементы теории графов, используемые в работе.

1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры.

1.3 Задача Краскала-Прима.

1.4 Выводы.

Глава 2. Задача Штейнера.

2.1 Свойства деревьев Штейнера в прямоугольной метрике.

2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности.

2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая.

2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике.;.'.

2.5 Алгоритм выборки перспективных дополнительных точек.

2.6 Оптимизация конфигурации дерева Штейнера.

2.7 Выводы.

Глава 3. Глобальная трассировка.

3.1 Постановка задачи и стандартная методика глобальной трассировки.i.

3.2 Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа.".

3.3 Второй этап Pathfinder. Оптимизация распределения цепей по ребрам глобального графа.

3.4 Третий этап Pathfinder. Волновая трассировка.

3.5 Сравнение результатов Pathfinder с результатами других программ глобальной трассировки.

3.6 Выводы.

Актуальность работы.

Серьезной проблемой при проектировании электронных устройств на современных КМОП-технологиях становится дефицит трассировочного ресурса. К нему приводит несколько факторов. Увеличение плотности транзисторов при тех же технологических размерах проектируемого устройства обуславливает рост числа электрических соединений на характерную относительную единицу площади (площадь одного транзистора). С увеличением слоев металлизации трассировочный ресурс каждого слоя уменьшается, поскольку увеличивается суммарная площадь сквозных переходов между слоями. С увеличением электронного оборудования возникает проблема падения напряжения питания - для ее решения увеличивают число переходов с верхних слоев земли/питания до уровня логических элементов, что значительно снижает трассировочный ресурс промежуточных (сигнальных) слоев металлизации. Хотя уменьшение минимальной ширины электрических проводников соответствует аналогичному уменьшению размеров транзисторов, однако на практике проблема прогнозирования и учета электромиграции приводит к тому, что растет число проводников с шириной, большей минимально возможной. Аналогичное утверждение справедливо для минимального расстояния между проводниками - для уменьшения взаимной емкости и обеспечения помехоустойчивости расстояние между проводниками критических цепей делают большим, чем минимально возможное.

Негативный эффект дефицита трассировочного ресурса связан с тем, что в процессе трассировки проводники назначаются «в обход» загруженных областей, а не «напрямую». Это обстоятельство приводит к увеличению величин задержек в цепях связи и уменьшению быстродействия электронного устройства в целом. Более того, высокая плотность логических элементов и, следовательно, трасс в определенных областях СБИС может привести к тому, что детальная трассировка при недостаточно качественной глобальной трассировке вообще не сможет бьггь осуществлена. Возможно, придется увеличить общую площадь кристалла или использовать дополнительные слои металлизации. И первый, и второй вариант снижают эффективность смены технологии и уменьшают надежность производства СБИС.

Немаловажным фактором также является время работы используемых алгоритмов. Проблемы, возникающие при проектировании СБИС на современных технологиях, приводят к тому, что изменяется сам процесс проектирования: из однопроходного он становится итерационным. Различные этапы, и в том числе процедура глобальной трассиращси, повторяются неоднократно для достижения требуемых характеристик проектируемого устройства. Кроме того, высокая плотность трасс и общее увеличение числа электрических цепей приводят к тому, что итерационный процесс трассировки становится плохо сходящимся — значительно увеличивается общее число требуемых итераций.

Таким образом, актуальной становится разработка эффективных как с точки зрения качества получаемых решений, так и времени работы, методов глобальной трассировки компонентов СБИС в условиях дефицита трассировочного ресурса (высокой плотности трасс).

Цель исследования.

Целью диссертационной работы являлось создание компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В соответствии с целью диссертационной работы были определены следующие задачи:

1. Исследование существующих алгоритмов построения минимальных связывающих деревьев, методов глобальной трассировки СБИС и анализ эффективности их применения для современных и перспективных КМОП технологий.

2. Разработка алгоритмического обеспечения для глобальной трассировки СБИС в условиях высокой плотности трасс.

3. Разработка методов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима при сохранении качества получаемых решений исходного алгоритма.

4. Разработка компонента САПР для глобальной трассировки СБИС.

Научная новизна работы.

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:

1. Разработка способов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима путем предварительной выборки перспективных точек Штейнера.

2. Разработка эффективных способов трансформации дерева Штейнера путем перестроения ограниченного множества ребер определенного типа. 3

3. Решение задачи построения начального леса деревьев Штейнера с учетом возможного распределения цепей по ребрам глобального графа.

4. Решение задачи оптимизации распределения цепей по ребрам глобального графа перед этапом перетрассировки путем многократного изменения начального разбиения многотерминальных цепей на двухтерминальные цепи.

Результаты, выносимые на защиту.

В процессе проведения исследований автором получены следующие результаты:

1. Конструктивный алгоритм предварительной выборки перспективных точек Штейнера для алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

2. Ряд итеративных методов трансформации дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет добиться максимального улучшения качества результатов совместной работы вышеуказанных алгоритмов при минимальных вычислительных затратах.

3. Вычислительная эффективность и качество получаемых решений предложенного комплекса алгоритмов доказана экспериментальными результатами, в том числе на тестовых примерах ESTEIN из стандартной библиотеки для задач исследования операций OR-Library.

4. Методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.

5. Комплексный итерационный алгоритм оптимизации укладки цепей по ребрам глобального графа.

6. На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Эффективность предложенных подходов подтверждена экспериментами на наборе тестовых примеров глобальной трассировки IBM, а также при сравнении с результатами работы программы глобальной трассировки Labyrinth.

Практическая ценность."

Основным практическим результатом проведенных исследований стало создание программы глобальной трассировки Pathfinder. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

Результаты исследований, выполненных по теме диссертации, нашли применение также в программном комплексе схемного редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Make Schematic для создания схемы электрических соединений. Данное программное обеспечение используется на этапе логического проектирования и позволяет строить графическое изображение схемы по списку соединений элементов.

Личный вклад автора.

Предложенные в диссертации алгоритм выборки перспективных дополнительных точек, алгоритм трансформации дерева Штейнера с использованием ограниченного множества ребер определенного типа, а также метод использования алгоритмов построения леса деревьев с учетом возможного распределения цепей и метод использования алгоритмов оптимизации укладки цепей разработаны лично-автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в ЗАО «МЦСТ») при личном участии автора. Компонент САПР Pathfinder для глобальной трассировки СБИС создан лично автором в рамках научно-исследовательского проекта Ariadna в течение 2003 года в Институте микропроцессорных вычислительных систем РАН.

Апробация.

Результаты диссертационной работы докладывались на всероссийских и вузовских научных конференциях:

1. ИрбенекВ. С., Рыженко Н. В. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. Российская научная конференция «Экономические информационные системы на пороге 21 века», Москва, октябрь 1999.

2. Рыженко Н. В. Алгоритмы построения минимальных связывающих деревьев и га применение в САПР электронной аппаратуры. V Всероссийская научная конференция студентов и аспирантов, Таганрог, октябрь 2000.

3. Рыженко Н. В. Алгоритм щ> строения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. XLIV Научная конференция МФТИ, Москва, ноябрь 2001.

4. Рыженко Н. В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Юбилейная VIII Санкт-Петербургская международная конференция «Региональная информатика - 2002», Санкт-Петербург, ноябрь 2002.

5. Рыженко Н. В. Pathfinder. Конкурс исследовательских проектов в области проектирования интегральных схем, проходивший при поддержке МФТИ и представительства корпорации Intel в странах СНГ. Проект-победитель. 2003.

6. Рыженко Н. В. О подходах к решению задачи глобальной трассировки СБИС для случая большой плотности трасс. XLVI Научная конференция МФТИ, Москва, ноябрь 2003.

7. Рыженко Н. В. Программа глобальной трассировки Pathfinder. XXI Научно-техническая конференция в/ч 03425, Москва, декабрь 2003.

Кроме того, результаты диссертационной работы неоднократно докладывались . »и обсуждались на научно-технических семинарах ИМВС РАН и ЗАО «МЦСТ».

Публикации.

По теме диссертации опубликовано 5 работ:

1. ИрбенекВ. С., Рыженко Н. В. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. В сборнике докладов российской научной конференции «Экономические информационные системы на пороге 21 века», Москва, 1999, стр. 361-366.

2. Рыженко Н. В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 3, Труды ИМВС РАН, Москва, 2002, стр. 48-61.

3. Ирбенек В. С., Рыженко Н. В. Алгоритмы проектирования топологии электрических соединений в САПР электронной аппаратуры. «Зарубежная радиоэлектроника. Успехи современной радиоэлектроники», №7,2002, с. 71-79.

4. Рыжещсо Н. В. Задача построения дерева Штейнера для этапа глобальной трассировки. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 4, Труды ИМВС РАН, Москва, 2003, стр. 96-105.

5. Рыженко Н. В. Программа глобальной трассировки Pathfinder. В сборнике тезисов докладов XXI Научно-технической конференции в/ч 03425, Москва, декабрь 2003.

Структура и объем работы.

Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 129 страниц текста, 63 иллюстрации, 29 таблиц (включая 7 таблиц приложения) и приложение на 8 листах. Список литературы и ссылок на ресурсы Internet насчитывает 61 наименование.

3.6 Выводы.

Результаты, представленные в данной главе, можно сформулировать следующим образом:

1. Проанализированы основные проблемы глобальной трассировки для современных и перспективных технологий производства СБИС. Систематизированы основные факторы, приводящие к дефициту трассировочного ресурса. Проанализированы стандартная методика глобальной трассировки, ее актуальность и недостатки в условиях дефицита трассировочного ресурса и высокой плотности трасс.

2. Разработан комплекс алгоритмов и методов для глобальной трассировки СБИС в условиях повышенной плотности трасс.

3. Предложена методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.

4. Предложен способ использования эластичности прямоугольных деревьев Штейнера для более качественного распределения цепей по ребрам глобального графа перед этапом перетрассировки.

5. Предложен способ оптимизации распределения цепей по ребрам глобального графа путем многократного перестроения начальных деревьев Штейнера.

6. Предложен эффективный комплексный итерационный алгоритм оптимизации укладки цепей по ребрам глобального графа. В отличие от стандартной методики глобальной трассировки оптимизация переполнения достигается не за счет изменения конфигурации проводника между какими-то двумя жестко зафиксированными точками, а за счет того, что дерево частично или даже полностью перестраивается, разбиение цепи на пары точек постоянно изменяется. Это позволяет значительно уменьшить переполнение глобального графа с минимальными потерями в суммарной длине.

7. На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

8. Проведено сравнение результатов работы Pathfinder и других программ глобальной трассировки Labyrinth и Chi на тестовых примерах IBM. Суммарная длина^рсех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14-20 процентов, у Chi на 1-3 процента. Однако главный критерий - это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Заключение. - —

Основной результат диссертационной работы заключается в разработке алгоритмической основы и создания компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В процессе исследования автором были получены следующие результаты:

1. Разработан алгоритм оценки перспективных дополнительных точек. Использование данного алгоритма позволяет в несколько раз сократить время работы алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

2. Временные и качественные характеристики предложенного модифицированного алгоритма позволяют успешно использовать его в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna. Предложенный алгоритм нашел применение также в программном комплексе редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Маке Schematic.

3. Разработан и практически реализован алгоритм динамического перестроения дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет за приемлемое время значительно улучшить качественные показатели модифицированного алгоритма. Экспериментально доказано, что процедура перестроения дерева использует лишь незначительную часть времени, сэкономленного за счет «отбраковки» неперспективных точек. Высокое качество получаемых решений подтверждено экспериментально на тестовых примерах ESTEIN из стандартной библиотеки OR-Library. Данный тестовый набор представляет собой совокупность задач с размерностью 10, 20, 30, 40, 50, 60, 70, 90, 100,250 и 500 точек - по 15 задач на каждую размерность. Отличие от оптимального значения в среднем для всех задач составляет 0.11 процента.

4. Разработан комплекс алгоритмов и методов для глобальной трассировки СБИС в условиях повышенной плотности трасс.

5. Предложенный комплекс алгоритмов реализован автором в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

116

6. Проведено сравнение результатов работы Pathfinder и других программами глобальной трассировки Labyrinth и Chi на тестовых примерах IBM. Суммарная длина всех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14—20 процентов, у Chi на 1-3 процента. Однако главный критерий - это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Благодарности.

Автор выражает искреннюю признательность научному руководителю Андрею Валентиновичу Жмурину за необходимое руководство и всемерную поддержку в подготовке и написании диссертационной работы. Большое спасибо Валентину Евсеевичу Вулихману, Александру Сергеевичу Калачеву и Валерию Владимировичу Шилову за ценные замечания и рекомендации, учтенные в работе. Автор благодарен Валентину Сергеевичу Ирбенеку - без помощи, участия и поддержки этого человека, столь неожиданно ушедшего из жизни, данная работа не состоялась бы.

1. J. Vuillemin. A data structure for manipulating priority queues. Commun. ACM 21,4 (April 1978), pp. 309-315.

2. H. Кристофидес. Теория графов. Алгоритмический подход. Москва, мир, 1978.

3. R. С. Prim. Shortest connection networks and some generalizations. Bell System Tech. J., 36,1957, pp. 1389-1401.

4. M. Kruskal. On the shortest spanning subtree of the the graph, and the traveling salesman problem. Proc. Amer. Math. Soc., 7, 1956, pp. 48-50.

5. C. Berge, A. Choilla-Houri. Programming, games and transportation networks. N.Y., John Wiley & Sons, 1965.

6. A. C.-C. Yao. An О (E log log V) algorithm for finding minimum spanning trees. Inf. Proc. Lett. 4,1975, pp. 21-25.

7. M. L. Fredman, R. E. Taijan. Fibonacci heaps and their uses in improved network optimization algorithms. Proceedings of 25th IEEE Symposium on the Foundations of Computer Science, Singer Island, 1984.

8. T. Barrera, J. Griffith, G. Robins, T. Zhang. Closing the gap: near-optimal Steiner trees in polynominal time. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 13, November 1993.

9. S. М. Sait, Н. Youssef. VLSI physical design automation. Theory and Practice. The Institute of Electrical and Electronics Engineers, New York, 1995.

10. M. R. Garey, R. L. Graham, D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. of Appl. Math., 32,1977.

11. The International Technology Roadmap for semiconductors. Interconnect. 2003.

12. В. Ф. Уткин. Новые методы построения графического изображения схем, представленных списком соединений. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники №7,2002, стр. 80-86.

13. В. Ф. Уткин. Исследование алгоритмических методов визуализации электрических схем. Диссертационная работа на соискание степени к.т.н., ИМВС РАН, 2002.

14. М. J. S. Smith. Application-Specific Integrated Circuits. Addison Wesley. 1997.

15. В. С^ Ирбенек. Временная верификация и оптимизация размещения компонентов предельных по быстродействию ЭВМ. Диссертационная работа на соискание степени д.т.н., ИМВС РАН, 2001.

16. J. Е. Bestley. OR-Library is a collection of test data sets for a variety of Operations Research (OR) problems, http://mscmga.ms.ic.ac.uk/info.html

17. M. Hanan. On Steiner's problem with rectilinear distance. SIAM J. Applied Math., 14,1966.

18. J. P. Cohoon, D. S. Richards, J. S. Salowe. An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of the rectangle. IEEE Transactions on Computer-Aided Design, Vol. 9, Apr. 1990.

19. Ore. Theory of graphs. Colloquium publications, 38, American Mathematical Society, Providence, 1962 (русский перевод: О. Ope. Теория графов. Москва, Наука, 1968).

20. Y. Y. Yang, О. Wing. Optimal and suboptimal solution algorithms for the wiring problem. Proceedings of IEEE International Symposium on Circuit Theory, 1972.

21. J. Ho, G. Vijayan, С. K. Wong. New algorithms for the rectilinear Steiner problem. Annals of Discrete Mathematics 53, Amsterdam, Netherlands, 1992.

22. J. S. Salowe, D. M. Warme. An exact rectilinear Steiner tree algorithm. Proceedings of International Conference on Computer Design, 1993.

23. C. D. Thomborson, L. L. Deneen, G. Shute. Computing a rectilinear Steiner minimaltree in 0{п0{Гп) time. Parallel Algorithms and Archtectures, Berlin, Germany, 1987.

24. Y. T. Wong, M. Pecht. A solution for Steiner problem. Placement and Routing of Electronic modules, New York, 1993.

25. S. E. Dreyfiis, R. A. Wagner. The Steiner problem in graphs. Networks, 1,1972.

26. J. L. Ganley, J. P. Cohoon. A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees. Proceedings of 4th Great Lakes Symposium on VLSI, 1994.

27. F. K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM J. Applied Mathematics, 30, 1976.

28. F. K. Hwang, D. S. Richards, P. Winter. The Steiner tree problem. North Holland, 1992.

29. J. L. Ganley, J. P. Cohoon. Optimal rectilinear Steiner trees in 0(n2 2.62") time. Proceedings of 6th Canadian Conference on Computation Geometry, 1994.

30. D. M. Warme. A new exact algorithm for rectilinear Steiner trees. INFORMS Conference, San-Diego, California, 1997.119

31. В. Ирбенек, Н. В. Рыженко. Алгоритмы проектирования топологии электрических соединений в САПР электронной аппаратуры. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники №7,2002.

32. Т. Barrera, J. Griffith, S. А. McKee, G. Robins, Т. Zhang. Toward a Steiner engine: enhanced serial and parallel implementations of the iterated 1-Steiner MRST algorithm. Proceedings of Great Lakes Symposium on VLSI, Kalamazoo, MI, March 1993.

33. F. K. Hwang. The Rectilinear Steiner Problem. Journal of Design Automation and Fault-Tolerant Computing, Vol. 2,1978.

34. H. В. Рыженко. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Труды ИМВС РАН №3,2002.

35. М. Hanan. Net Wiring for Large Scale Integrated Circuits. IBM Research Report RC 1375,1965.

36. A. Ayupov, I. Bychkov, V. Lyssyi, D. Rybin, N. Ryzhenko, A. Sorokin, A. Usenkov, V. Utkin, O. Venger. Ariadna. Technical Report, IMCS RAS, December 2003.

37. IBM benchmarks for global routing, http://beiiing.cs.ucla.edu/benchmarks/gr-input/

38. A standard-cell placer DRAGON. http://er.cs.ucla.edu/Dragon/

39. R. Nair. A Simple Yet Effective Technique for Global Wiring. In IEEE Transactions on Computer Aided Design. March 1987.41 .A global router Labyrinth, http://www.ece.ucsb.edu/~kastner/labvrinth/

40. J. Cong, P. H. Madden. Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs. Proceedings of ACM/IEEE Design Automation Conference, 1998.

41. Tsung-Yi Ho, Yao-Wen Chang, Sao-Jie Chen, D. T. Lee. A Fast Crosstalk- and Performance-Driven Multilevel Routing System. ICCAD'03, November 2003.

42. S.-P. Lin, Y.-W. Chang. A novel framework for multilevel routing considering routability and performance. ICCAD'02, November 2002.

43. J. S. Rose. LocusRoute: A Parallel Global Router for Standard Cells. In Proceedings of the 25th Design Automation Conference, June 1988.

44. Coundert. Timing and Design Closure in Physical Designs Flows. Proceedings of the International Symposium on Quality Electronic Design, 2002.

45. M. Lai and D. F. Wong. Maze routing with buffer insertion and wire sizing. DAC, 2000.

46. J. Lillis, С. К. Cheng, T-.T.^Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model ICCAD-95,1995.

47. T. Okamoto, J. Cong. Buffered Steiner tree construction with wire sizing for interconnect layout optimization. ICCAD-96,1996.

48. H. Zhou, D. F. Wong, I. M. Liu, A. Aziz. Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Location. DAC, 1999.

49. A. H. Salek, J. Lou, M. Pedram. A simultaneous routing tree construction and fanout ' optimization algorithm. ICCAD, 1998.

50. A. H. Salek, J. Lou, M. Pedram. MERLIN: semi-order-independent hierarchical ■ buffered routing tree generation using local neighborhood search. DAC, 1999.

51. E. Bozorgzadeh, R. Kastner, M. Sarrafzadeh. Creating and Exploiting Flexibility in Rectilinear Steiner Trees. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems. May 2003.

52. R. Kastner, E. Bozorgzadeh, M. Sarrafzadeh, Predictable Routing. ACM/IEEE International Conference on Computer-Aided Design, 2000.

53. University of California, Santa Barbara, http://www.ucsb.edu/

54. Department of Electrical and Computer Engineering. University of California, Santa Barbara, http:// www.ece.ucsb. edu/

55. Конкурс исследовательских проектов в области автоматизации проектирования интегральных схем, проходивший при поддержке МФТИ и представительства корпорации Intel в странах СНГ. http://www.curricula.ru/CAD contest.esp

56. Row Но, Kenneth W. Mai, Mark A. Horowitz. The future of wires. Proceedings of IEEE, Vol. 89, No. 4, April 2001.

57. D. Sylvester, K. Keutzer. Getting to the Bottom of Deep Submicron II: A Global Wiring Paradigm. In proceedings of Intl. Symposium on Physical Design, 1999.

58. R. T. Hadsell, P. H. Madden. Improved Global Routing through Congestion Estimation. DAC, June 2003.

59. M. Borah, R. M. Owens, M. J. Irwin. An edge-based heuristic for Steiner routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(12), December 1994.