автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Исследование и разработка метода планировки цепей СБИС с равномерным заполнением области трассировки

На правах рукописи

ЗАГЛЯДИН ГЛЕБ ГЕОРГИЕВИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА ПЛАНИРОВКИ ЦЕПЕЙ СБИС С РАВНОМЕРНЫМ ЗАПОЛНЕНИЕМ ОБЛАСТИ ТРАССИРОВКИ

Специальность: 05.13.12 - системы автоматизации проектирования

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2011г.

2 ИЮН 2011

4848576

Работа выполнена на кафедре проектирования и конструирования интегральных микросхем Московского государственного института электронной техники (технического университета)

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

Казённое Геннадий Георгиевич

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

Марченко Александр Михайлович

кандидат технических наук, Дубровин Станислав Александрович

Ведущая организация: ИППМ РАН

Защита диссертации состоится «-¿Г» 2011г. на

заседании диссертационного совета Д212.134.01 при Московском государственном институте электронной техники: 124498 Москва, Зеленоград, МИЭТ.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электронной техники. С

Автореферат разослан «¿^ » ^лА. 2011г.

Ученый секретарь д.т.н., профессор Крупкина Т.Ю.

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

Аннотация.

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

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

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

В работе проведено исследование программной реализации разработанного метода планировки цепей, сравнение с традиционно применяемыми методами. Сделан вывод о перспективности предложенного подхода.

Актуальность темы.

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

количества выделяемого тепла приводит к проблеме его отвода и равномерного распределения по площади кристалла.

В связи с усилением влияния паразитных эффектов суб-ЮОнм технологии (cross-talk, IR-drop) на работоспособность нанометровых СБИС возникает необходимость учитывать их непосредственно на этапах размещения и трассировки. Коррекция паразитных эффектов оптической близости (ОРС - Optical proximity Correction) частично производится с помощью добавления принципиально новых конструкторско-технологических ограничений. Также вводятся дополнительные требования к максимальной и минимальной плотности металлизации, что должно обеспечить качество химико-механической полировки.

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

Цели и задачи работы.

Целью данной диссертационной работы является разработка математического, алгоритмического и программного обеспечения для планировки цепей СБИС с равномерным заполнением области трассировки. Для достижения данной цели в диссертационной работе решены следующие задачи:

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

2. Предложен метод планировки цепей с использованием семейств деревьев Штейнера, устраняющий выявленные недостатки;

3. Разработан алгоритм генерации семейства деревьев Штейнера;

4. Разработан алгоритм фильтрации семейства деревьев Штейнера и критерий близости структуры двух деревьев;

5. Разработан алгоритм оптимизации, выбирающий определенное дерево Штейнера для каждой цепи исходя из состава семейств;

6. Разработанные алгоритмы реализованы в виде комплекса программного обеспечения;

7. Проведена практическая апробация результатов работы.

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

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

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

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

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

Методы исследования.

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

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

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

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

Все результаты, приведенные в диссертации, получены либо лично соискателем, либо при его непосредственном участии. Можно выделить следующие наиболее значимые результаты:

1. Решена задача использования семейства деревьев Штейнера для планировки цепей СБИС с равномерным заполнением области трассировки;

2. Разработан алгоритм генерации семейства деревьев Штейнера;

3. Разработан алгоритм фильтрации семейства деревьев Штейнера на основе критерия близости структуры двух деревьев Штейнера;

4. Разработан алгоритм оптимизации, определяющий топологию цепей исходя из состава семейств деревьев Штейнера и равномерности заполнения области трассировки;

5. Создано программное обеспечение для реализации разработанных алгоритмов.

Диссертационная работа выполнена в рамках очной аспирантуры МИЭТ (ТУ).

Практическая значимость работы.

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

Реализация результатов работы.

Результаты работы в виде программных модулей для программы планировки цепей при топологическом проектировании ИС внедрены в учебный процесс МИЭТ, а также в процесс проектирования базовых матричных кристаллов на ОАО «Ангстрем».

Представляются к защите.

1. Метод планировки цепей СБИС с равномерным заполнением области трассировки, основанный на использовании семейств деревьев Штейнера.

2. Алгоритм генерации семейства деревьев Штейнера на основе остовных деревьев.

3. Алгоритм фильтрации семейства деревьев Штейнера, основанный на критерии близости структуры двух деревьев Штейнера.

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

Апробация результатов работы.

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

XIII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 19-21 апреля

2006 г.

XIV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 18-20 апреля

2007 г.

XV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 23-25 апреля 2008 г.

Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 2-11 марта 2009 г.

XVI Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 22-24 апреля

2009 г.

XVII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 28-30 апреля

2010 г.

Международная научно-техническая конференция

«Проектирование систем на кристалле: тенденции развития и проблемы», Москва, Зеленоград, 19-21 октября 2010 г.

Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 20-27 марта 2011 г..

Публикации.

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

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

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

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

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

В первой главе приводятся: постановка задачи планировки цепей, актуальные подходы и алгоритмы для ее решения. Проведен анализ эффективности решений, представленных на конкурсе планировки цепей ISPD-2008 (International Symposium of Physical Design), выявлены их основные достоинства и недостатки.

Задача планировки цепей решается в два этапа:

1. Классифицирование цепей и выбор оптимальных алгоритмов для их трассировки;

2. Трассировка всех цепей выбранными алгоритмами.

Алгоритмы трассировки отдельной цепи классифицируются

исходя из количества терминалов. Для определения топологии цепей с двумя терминалами используются алгоритмы лабиринтной (А*), лучевой и монотонной трассировки, трассировочные шаблоны (pattern routing), сдвиг ребра или же общематематические методы. Основной моделью топологии всех остальных цепей являются дерево Штейнера или остовное дерево. Остовное дерево формируется алгоритмами Прима и Краскала. Принцип их работы заключается в итерационном добавлении ребер с минимальной длиной при формировании остова. Остовное дерево также может использоваться для получения дерева Штейнера. В этом случае координаты точек Штейнера выбираются так, чтобы устранить наложения охватывающих прямоугольников ребер. Лучшие результаты способны показать алгоритмы, итерационно

добавляющие точки Штейнера в исходное остовное дерево (BIS, IIS, BUS). Наибольшей популярностью пользуется алгоритм FLUTE (Fast Lookup Table Estimation). Принцип его работы заключается в поиске точного решения по предварительно сгенерированным таблицам. Из-за факториальной зависимости размера таблицы от количества терминалов применяется разбиение на поддеревья. Для построения дерева Штейнера также могут быть применены алгоритмы декомпозиции и лабиринтной трассировки. Изменение его топологии осуществляется сдвигом ребер по одному из направлений.

Существует два подхода к трассировке множества цепей: последовательный и параллельный.

Основополагающим принципом последовательных алгоритмов является определение порядка трассировки цепей. Применение сортированного списка менее эффективно, нежели итерационный подход, поэтому его используют только для получения начального решения. Дальнейшая оптимизация осуществляется разрывом и перетрассировкой цепей (RRR - Rip-up and ReRoute). Эффективность данного подхода определяется видом целевой функции. При представлении каналов в виде вершин графа может быть применена минимизация стоимости ребер дерева Штейнера с максимальным весом.

Для одновременной трассировки множества цепей может быть применена постановка задачи многопродуктового потока (MCF -multicommodity flow) и целочисленного линейного программирования (ILP - Integer Linear Programming). Задачей MCF в таком случае будет являться сокращение либо распределение потока (цепей), проходящего через каналы. Для целочисленного программирования используется постановка задачи булевого программирования (0-1 ILP), в котором для каждой цепи может быть назначена только одна реализация.

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

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

Вместо них активно применяются трассировочные шаблоны и реструктурирование деревьев Штейнера сдвигом ребер.

Вторая глава диссертационной работы посвящена описанию разработанного автором алгоритма формирования семейства деревьев Штейнера.

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

определенного параметра Дс05(. При последующей оптимизации по

другим критериям поиск решений производится только в пределах полученного множества.

Алгоритм генерации семейства деревьев Штейнера состоит из 4 шагов, каждый из которых приводит топологию деревьев Штейнера в соответствие с требованиями, предъявляемыми к составу семейства:

1. Генерация семейства остовных деревьев с заданным ограничением стоимости;

2. Добавление точек Штейнера в остовное дерево;

3. Приведение деревьев к ортогональному виду с учетом планарности;

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

основные этапы формирования семейства деревьев Штейнера.

1. Построение семейства остовных деревьев

Построение сортированного списка ребер полного графа

Построение минимального остовного дерева

Поиск ребер для юдстановки

Составления остовных деревьев с найденными ребрами

Отсев дерепьео с нарушением стоимости

2. Добавление точек Штейнера

| Выбор осговного дерева |

И

Выбор двух смежных ребер _

Расчет координат точки Штейнера

5

[Изменениеграфа! ■

3. Приведение деревьев Штейнера К ортогональному виду

| Выбор дерева Штейнера

т~

УНет

Выбор топологии ребра

ет

Нет /'ребра

Нет

Удаление дерева

4. Исключение деревьев Штейнера со сходной топологией

'Для всех пар N деревьев /

Рисунок 1. Алгоритм формирования семейства деревьев Штейнера.

За основу алгоритма генерации семейства остовных деревьев (Рисунок 2) был выбран алгоритм Краскала. В нем сначала строится сортированный список ребер полного графа, затем происходит

формирование остова минимальной стоимости последовательным добавлением ребер в порядке возрастания их веса. Поскольку процедура формирования дерева заключается в выборе первого элемента списка, то перестановка нового ребра в его начало приведет к получению нового остова. Для формирования семейства остовных деревьев ищется множество ребер, вес каждого из которых не превышает тах(ШГ) + ДС0!,, где тах(М5Г) - вес ребра максимальной стоимости из

минимального остовного дерева. После перестановки этих ребер в начало общего списка ребер выполняется алгоритм Краскала. Временная сложность алгоритма составляет о(и2где п -количество терминалов цепи.

Рисунок 2. Блок-схема алгоритма генерации семейства остовных

деревьев.

Построение семейства деревьев Штейнера на основе семейства остовных деревьев происходит в два этапа: добавление точек Штейнера и приведение дерева в ортогональный вид.

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

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

^ в 1 к В

1 У. УЧ. : У" ?

У» Дн

■ Ул ! У. к кг

хА х„ хс г : X' х»

Рисунок 3. Добавление точки Штейнера.

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

2. Добавление точек Штейнера

| Выбор остовного дерева

Выбор двух смежных ребер

Расчет координат точки Штейнера

3. Приведение деревьев Штейнера > к ортогональному виду |

Рисунок 4. Блок-схема алгоритма добавления точек Штейнера в остовное дерево.

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

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

Рисунок 5. Блок-схема алгоритма приведения дерева Штейнера к ортогональному виду.

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

Для сравнения топологии двух деревьев используется оценка локальной коммутационной плотности. Расчет производится при помощи регулярной сетки из горизонтальных и вертикальных сечений.

3. Приведение деревьев Штейнера к ортогональному виду

■|"вы6ор "ребра |

1

со сходной топологией

Положим Вм = (с1р)

X I

Бм=(с!р)

У У

векторы, содержащие

количество ребер дерева ¡л, подпадающих под сечения регулярной сетки для столбцов и строк соответственно. Значит для пары деревьев

(МиМг)

Ьс1

[мх.мг)

XI XI XI у ] У у у j

Для оценки близости деревьев используется

1=0 V > )

+

А*

х I

(п >М2 )

¡=0 * ' ¡=0 * ' >о у 1

пх и пу - размерность сетки по осям абсцисс и ординат.

При оценке различных деревьев одной цепи шаг сетки и ее размер не меняются. Применение сетки Ханана приводит к оценке только структурных различий, тогда стоимость ребер не принимается в учет. Величина шага влияет на точность с одной стороны, и на быстродействие алгоритма с другой. Пример расчета оценки близости деревьев (1) показан на рисунке 6.

1 2 3 40(У)

1 2 ЗШу)

Р(р,,М2)=355

Рисунок. 6. Пример расчета оценки близости деревьев.

Для фильтрации семейства деревьев Штейнера осуществляется перебор всех возможных пар деревьев, количество которых в • наихудшем случае будет составлять Т-{Т-\) > т.е. сложность алгоритма

2

не будет превышать 0(Т2к2), где Г-количество деревьев в семействе, к- шаг регулярной сетки для расчета оценки близости деревьев.

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

4. Исключение деревьев Штейнера, со сходной топологией .

Удаление дерева

Выход

Рисунок 7. Блок-схема алгоритма фильтрации семейства деревьев

Штейнера.

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

Проблему выбора дерева Штейнера можно представить следующим образом: необходимо выбрать такое дерево ¡Л^ € М,, где

М, - семейство деревьев Штейнера, которое способствует оптимизации по выбранному критерию (Рисунок 8).

м м*1

■¡1 ^

Рисунок 8. Выбор определенного дерева Штейнера для каждой цепи.

Алгоритм выбора деревьев Штейнера основан на алгоритме Кернигана-Лина. В нем необходимо на каждой итерации определять, какое дерево будет использовано для перестановки в определенном семействе.

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

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

На рисунке 9 приведена его блок-схема алгоритма выбора деревьев Штейнера.

Алгоритм выбора деревьев Штейнера

Построить список цепей

Разблокировать цепи

• + ........

целевой функции

Т---

Отсортировать список

~—гт;

Для каждой цепи / У—»■

Воспроизвести к шагов

Найти номер шага к,

Сменить дерево

Заблокировать цепь

^ Выход

Рисунок. 9. Алгоритм выбора деревьев Штейнера.

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

записывается в векторы О = (с! ) и В = (с! ) . мЬ) = — У1 г/ и

* * л х Пхыох1

м(в\ = —, пх и и.у - размерность сетки по осям абсцисс

и ординат. Целевая функция для оценки равномерности заполнения области трассировки выглядит следующим образом:

-мт2+^ -мт2 ■

£о " ' п *

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

= (2)

Временная сложность полученного алгоритма оптимизации составляет

оИ

, где N - количество цепей. Четвёртая глава посвящена рассмотрению аспектов программной реализации разработанных в диссертации алгоритмов.

Метод был реализован с использованием языка С++. При увеличении ДС05( возникает эффект насыщения размера получаемых

семейств, что позволяет ограничить диапазон значений данного параметра значениями от 1% до 15% длины минимального остовного дерева. Алгоритм фильтрации отсекает возможные дубликаты деревьев в семействе и дает возможность уменьшить размерность решаемой задачи.

Для того, чтобы исследовать разработанный метод, из открытого интернет-ресурса «opencores.org» был получен набор тестовых примеров (Таблица 1). Для каждого блока последовательно производились этапы: логического синтеза, планировки кристалла, размещения элементов, планировки цепей, детальной трассировки и верификации.

Таблица 1. Описание тестовых схем.

№ Название Кол- во цепей Описание

1 sin 124 Генератор синусоидального сигнала

2 fht 221 Быстрое преобразование Адамара, 8 бит

3 keypad scanner 409 Сканирование цифровой клавиатуры

4 hw looping 475 Зацикливание аппаратного обеспечения

5 leml 95 485 П Дополнение набора команд

6 arbgen 641 Генератор сигналов произвольной формы

7 wb led 654 Контроллер буквенно-цифрового индикатора

8 Keyboard controller 721 Контроллер клавиатуры

9 ptc 764 ШИМ, таймер, счетчик

10 plasma 846 32-6HTRISC

11 openFPU64 940 Математический сопроцессор

12 ClaiRISC 1275 Микроконтроллер PIC, 12-бит

13 quadratic func 1396 Полином 2-й степени

14 cowgirl 1819 Процессор

15 spi top 2332 SPI- микроконтроллер

В таблице 2 представлены результаты исследований. В качестве эталона использовалась коммерческая САПР. Реализацией разработанного метода является прикладное ПО «вгаЫа». Для измерения загруженности использовалось количество сегментов, проходящих через сечения регулярной сетки расчета целевой функции (2). Среднее и максимальное количество сегментов представлены как средняя и максимальная загруженность соответственно. Как видно в таблице 2, разработанный метод показывает значительное уменьшение коммутационной плотности схем, понижая при этом среднюю и максимальную загруженность коммутационных областей.

Таблица 2. Сравнение результатов метода и коммерческой САПР.

№ Суммарная длина цепей, мм Средняя загруженность Максимальная загруженность

Эталон СгаЫа Д,% Эталон СгаЫа Д,% Эталон СгаЫа Д,%

1 3,2363 3,3469 3,4 93,0143 71,519 -23,1 300 208 -30,7

2 4,6538 4,6621 0,2 140,8 102,267 -27,4 360 269 -25,3

3 9,53 9,5226 -0,1 241,056 176,846 -26,6 552 395 -28,4

4 38,862 38,597 -0,7 77,0701 61,5233 -20,2 418 296 -29,2

5 8,7643 8,977 2,4 223,108 166,324 -25,5 467 363 -22,3

6 1,2479 12,402 -0,6 320,263 221,421 -30,9 776 518 -33,2

7 1,2174 12,174 0,0 312,605 220,887 -29,3 782 525 -32,9

8 28,5924 28,1491 -1,6 503,905 311,087 -38,3 974 604 -38,0

9 19,3765 19,572 1,0 365,811 255,182 -30,2 798 576 -27,8

10 21,0514 21,2616 1,0 382 263,043 -31,1 840 596 -29,0

11 217948 21,3635 -2,0 472,955 307,727 -34,9 1066 666 -37,5

12 25,8618 26,1745 1,2 445,042 303,905 -31,7 890 568 -36,2

13 37,2057 36,2457 -2,6 678,422 418,118 -38,4 1347 749 -44,4

14 48,9366 49,4437 1,0 651 438,616 -32,6 1090 772 -29,2

15 47,3249 48,1229 1,7 692,033 490,267 -29,2 1206 818 -32,2

На рисунке 10 представлено изменение загруженности для каждого тестового примера. Серым цветом отмечена средняя загруженность, а черным - максимальная, в среднем улучшение составило 29,96% и 31,75% соответственно. Следует отметить, что в действительности улучшение составило менее 30%, поскольку эталонная САПР дополнительно производила оптимизацию рабочей частоты, чего не было у исследуемой системы. Поэтому в среднем ухудшение временных характеристик схем составило 17,83%.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 № тестового примера

Рисунок 10. Уменьшение загруженности коммутационного пространства.

Одновременно с распределением загруженности коммутационного пространства разработанный метод оказывает влияние на суммарную длину цепей. Для того же тестового набора данный параметр в среднем не увеличился (Рисунок 11).

9 10 11 12 13 14 15 _ № тестового примера

Рисунок 11. Изменение суммарной длины цепей.

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

Выводы. Разработанный метод планировки сигнальных цепей СБИС показывает увеличение эффективности распределения коммутационных ресурсов при незначительном увеличении суммарной длины цепей. Данный метод применим не только для трассировки блоков с высокой плотностью коммутаций, но и при минимизации влияния паразитных эффектов суб-100нм технологии.

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

В приложении приведены акты внедрения результатов диссертационной работы.

Основные результаты работы.

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

2. Разработан метод планировки цепей, использующий семейства деревьев Штейнера для равномерного заполнения области трассировки.

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

4. Введены критерий сравнения структуры двух деревьев Штейнера и целевая функция, основанная на оценке равномерности заполнения области трассировки.

5. Разработан алгоритм оптимизации для этапа планировки цепей, основанный на выборе конечной топологии цепи из состава

семейства деревьев Штейнера с помощью введенной целевой функции.

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

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

1. Заглядин Г.Г., Панфилов C.B. Инфраструктура и подсистема планировки кристалла для САПР топологии ИС. // Микроэлектроника и информатика-2006, М.: МИЭТ, 2006. стр. 120.

2. Заглядин Г.Г. Реализация этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. II Микроэлектроника и информатика-2007, М.: МИЭТ, 2007. стр. 67.

3. Заглядин Г.Г. Исследование реализации этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. // Сб. науч. Трудов «Проектирование электронной компонентной базы и систем на кристалле» под ред. М.Г. Путри, М.: МИЭТ, 2007. с. 49-55.

4. Заглядин Г.Г. Планировка цепей высокопроизводительных ИС. II Микроэлектроника и информатика-2008, М.: МИЭТ, 2008. стр. 72.

5. Заглядин Г.Г., Многокритериальная планировка цепей СБИС. // Микроэлектроника и информатика-2009, М.: МИЭТ, 2009. стр. 85.

6. Gleb Zaglyadin, Multiobjective Global Routing. Il MB-JASS 2009, Москва, 2009.

7. Заглядин Г.Г, Разработка метода многокритериальной глобальной трассировки СБИС. // Микроэлектроника и информатика-2010, М.: МИЭТ, 2010. стр. 73.

8. Заглядин Г. Г., Сырцов И. А., Школа А. В. Алгоритм синтеза множества остовных деревьев для выполнения глобальной

■ трассировки заказных СБИС. // Известия высших учебных заведений. Электроника. №5(85). М: МИЭТ, 2010. стр. 36-40.

9. Заглядин Г. Г., Сырцов И. А. Глобальная трассировка заказных СБИС с использованием множества остовных деревьев. // Естественные и технические науки. №4(48). М: «Спутник+», 2010. стр. 322-326.

10. Заглядин Г.Г. Метод глобальной трассировки цепей субмикронных СБИС с использованием семейства деревьев Штейнера. // Проектирование систем на кристалле: тенденции развития и проблемы, М.: МИЭТ, 2010. стр. 13.

Подписано в печать Заказ № 1'сЧ Тираж 1°° экз. Уч.-изд. л. О Формат 60x84 1/16. Отпечатано в типографии МИЭТ (ТУ). 124498, Москва, Зеленоград, проезд 4806, д.5. МИЭТ (ТУ).

Введение.

Глава 1. Обзор алгоритмов и методов планировки цепей.

1.1. Этапы решения задачи трассировки.

1.2. Модели представления коммутационного пространства.

1.3. Методы планировки цепей.

1.3.1. Алгоритмы лабиринтной трассировки.

1.3.2. Алгоритмы трассировки многотерминальных цепей.

1.3.3. Методы оптимизации множества цепей.

1.4. Алгоритмы планировки цепей с конкурса 1БРО 08.

1.5. Выводы.

Глава 2. Алгоритм построения множества деревьев Штейнера.

2.1. Необходимость разработки нового алгоритма для построения деревьев Штейнера.

2.2. Постановка задачи построения семейства деревьев Штейнера.

2.3. Алгоритм построения семейства деревьев Штейнера.

2.3.1. Алгоритм построения семейства остовных деревьев.

2.3.2. Алгоритм преобразования остовных деревьев к деревьям Штейнера с ортогональными ребрами.

2. 4. Фильтрация семейства деревьев.

2.4.1. Оценка близости двух деревьев.

2.4.2. Фильтрация семейства деревьев Штейнера.

2.5. Выводы.

Глава 3. Метод планировки цепей с использованием семейств деревьев

Штейнера.

3.1. Постановка задачи.

3.1. Выбор деревьев для равномерного заполнения области трассировки.

3.2. Алгоритм оптимизации с использованием семейства деревьев Штейнера.

3.2.1. Целевая функция для оценки распределения загруженности области трассировки.

3.2.2. Алгоритм выбора деревьев из семейства.

3.3. Демонстрация работы алгоритма выбора деревьев Штейнера.

3.5. Выводы.

Глава 4. Программная реализация метода планировки цепей и результаты тестирования.

4.1. Программная реализация метода планировки цепей.

4.1.1. Программная реализация алгоритма генерации семейства деревьев Штейнера.

4.1.2. Программная реализация алгоритма выбора деревьев Штейнера.

4.2. Исследование реализации алгоритмов.

4.2.1. Результаты тестирования быстродействия.

4.2.2. Результаты тестирования эффективности предложенных алгоритмов. 88 4.4. Выводы.

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

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

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

В работе проведено исследование программной реализации разработанного метода планировки цепей, сравнение с традиционно применяемыми методами. Сделан вывод о перспективности предложенного подхода.

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

В связи с усилением влияния паразитных эффектов суб-ЮОнм технологии (cross-talk, IR-drop) на работоспособность нанометровых СБИС возникает необходимость учитывать их непосредственно на этапах размещения и трассировки. Коррекция паразитных эффектов оптической близости (ОРС - Optical proximity Correction) частично производится с помощью добавления принципиально новых консгрукторско-технологических ограничений. Также вводятся дополнительные требования к максимальной и минимальной плотности металлизации, что должно обеспечить качество химико-механической полировки.

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

Целью данной диссертационной работы является разработка математического, алгоритмического и программного обеспечения для планировки цепей СБИС с равномерным заполнением области трассировки. Для достижения данной цели в диссертационной работе решены следующие задачи:

1) Проведен анализ существующих методов построения и оптимизации деревьев Штейнера, рассмотрены их преимущества и недостатки;

2) Предложен метод планировки цепей с использованием семейств деревьев Штейнера, устраняющий выявленные недостатки;

3) Разработан алгоритм генерации семейства деревьев Штейнера;

4) Разработан алгоритм фильтрации семейства деревьев Штейнера и критерий близости структуры двух деревьев;

5) Разработан алгоритм оптимизации, выбирающий определенное дерево Штейнера для каждой цепи исходя из состава семейств;

6) Разработанные алгоритмы реализованы в виде комплекса программного обеспечения;

7) Проведена практическая апробация результатов работы.

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

1) Разработан, реализован и исследован метод планировки цепей СБИС, основанный на использовании семейств деревьев Штейнера, что позволяет при оптимизации учитывать деревья целиком, а не разбивать их на составляющие;

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

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

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

Реализация. Результаты работы в виде программных модулей для программы планировки цепей при топологическом проектировании ИС внедрены в учебный процесс МИЭТ, а также в процесс проектирования базовых матричных кристаллов на ОАО «Ангстрем».

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

Апробация результатов работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях:

XIII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 19-21 апреля 2006 г.

XIV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 18-20 апреля 2007 г.

XV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 23-25 апреля 2008 г.

Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 2-11 марта 2009 г.

XVI Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 22-24 апреля 2009 г.

XVII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, 28-30 апреля 2010 г.

Международная научно-техническая конференция «Проектирование систем на кристалле: тенденции развития и проблемы», Москва, Зеленоград, 19-21 октября 2010 г.

Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 20-27 марта 2011 г.

Публикации. Основные результаты диссертационной работы опубликованы в двух научных статьях [91,92] и семи докладах [84,85,8790,93] в трудах научно-технических конференций (еще одна статья находится в печати).

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы.

4.4. Выводы.

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

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

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

4) Предложены способы повышения эффективности и быстродействия реализованного метода планировки цепей.

Заключение.

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

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

2. Разработан метод планировки цепей, использующий семейства деревьев Штейнера для равномерного заполнения области трассировки.

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

4. Введены критерий сравнения структуры двух деревьев Штейнера и целевая функция, основанная на оценке равномерности заполнения области трассировки.

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

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

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

По сравнению с эталонной САПР:

- равномерность загруженности коммутационных областей улучшилось в среднем на 29%,

- временные характеристики ухудшились в среднем на 17%,

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

1. International Technology Roadmap for Semiconductors (ITRS), 2006.

2. J. Cong. Challenges and opportunities for design innovations in nanometer technologies. // in SRC Design Science Concept Papers, 1997.

3. Казеннов Г. Г. Основы проектирования интегральных схем и систем. М.: БИНОМ. Лаборатория знаний. 2005.

4. Т. Gao and С. L. Liu. Minimum crosstalk switchbox routing. // in Proc. IEEE Int. Conf. Computer-Aided Design. 1994.

5. J. Westra, P. Groeneveld, T. Yan, and P. H. Madden. Global Routing ¡Metrics, Benchmarks, and Tools. // in IEEE DATC Electronic Design Process, 2005.

6. R. M. Karp. Complexity of computer computations. // in Reducibility Among Combinatorial Problems. New York: Plenum, 1972.

7. J. Hu and S. S. Sapatnekar. A survey on multi-net global routing for integrated circuits. // Integration, the VLSI Journal, vol. 31, no. 1, 2001. pp. 1-49.

8. Т. H. Cormen, С. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.

9. M. Kurant, A. Markopoulou and P. Thiran. On the bias of BFS (Breadth First Search). // International Teletraffic Congress (ITC 22), 2010.

10. C. Y. Lee. An algorithm for path connection and its application. // in IRE Trans. Electronic Computer, 1961.

11. E. F. Moore. The shortest path through a maze. // In Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, Cambridge, 1959. pp. 285-292.

12. S. Akers. A modification of lee's path connection algorithm. // IEEE Transactions on Electronic Computers, EC-16(2): 97-98, 1967.

13. S. Akers. Routing. // Vol. 1. Prentice-Hall, Englewood Cliffs, NJ, 1972.

14. F. 0. Hadlock. A shortest path algorithm for grid graphs. // Networks, 7(4): 323-334, 1977.

15. J. Soukup. Fast maze router. // In Proceedings of the 15th Design Automation Conference, IEEE Press,Piscataway, NJ, pp. 100-102, 1978.

16. K.Mikami and K. Tabuchi. A computer program for optimal routing of printed circuit connectors. // In IFIPS Proceedings, H47: 1475-1478, 1968.

17. D. W. Hightower. A solution to line-routing problems on the continuous plane. // In Proceedings of the 6th Annual Conference on Design Automation, ACM, NY, pp. 1-24, 1969.

18. R.Kastner, E. Borzorgzadeh, andM. Sarrafzadeh, Predictable routing. // in Proc. IEEE Int. Conf. Computer-Aided Design, 2000.

19. R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh. Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling. // IEEE TCAD 21(7), pp. 777-790, 2002.

20. J. Westra, C. Bartels, and P. Groeneveld. Probabilistic Congestion Prediction. // in Proc. Int. Symp. on Physical Design, 2004.

21. J. Westra, C. Bartels, and P. Groeneveld. Is Probabilistic Congestion Estimation Worthwhile? // in Proc. System-Level Interconnect Prediction, 2005.

22. M. Pan and C. Chu. Fastroute: A step to integrate global routing into placement. // In Proceedings of International Conference on Computer Aided Design, IEEE Press, Piscataway, NJ, pp. 464-471, 2006.

23. Eisner, Jason. State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. // Manuscript, University of Pennsylvania, April, pp 78, 1997.

24. Eugene F. Krause. Taxicab Geometry. Dover. 1987.

25. M. Hanan. On Steiner's problem with rectilinear distance. // SIAM Journal of Applied Mathematics, 14:255-265, 1966.

26. M. Garey and D. S. Johnson. The rectilinear Steiner problem is NP-complete. // SIAM Journal of Applied Mathematics, 32(4): 826-834, 1977.

27. F. K. Hwang. On Steiner minimal trees with rectilinear distance. // SIAM Journal of Applied Mathematics, 30(1): 104-114, 1976.

28. A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.

29. A. B. Kahng and G. Robins. A new family of Steiner tree heuristics with good performance: The iterated 1-steiner approach. // In Proceedings of the IEEE International Conference Computer-Aided Design, pp. 428-431, Santa Clara, CA, November 1990.

30. A. B. Kahng and G. Robins. On performance bounds for a class of rectilinear Steiner tree heuristics in arbitrary dimension. // IEEE Transactions Computer-Aided Design, 11(11): 1462-1465, November 1992.

31. G. Robins. On Optimal Interconnections. // PhD thesis, Department of Computer Science, UCLA, Los Angeles, CA, CSD-TR-920024, 1992.

32. M. Burstein and R. Pelavin. Hierarchical Wire Routing. // IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, vol. 2, no. 4, pp. 223-234, 1983.

33. Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48-50.

34. R. C. Prim. Shortest connection networks and some generalizations. // Bell System Technical Journal, 36 (1957), pp. 1389-1401.

35. J. M. Ho, G. Vijayan, and C. K. Wong. New algorithms for the rectilinear Steiner tree problem. // IEEE Transactions Computer-Aided Design, 9(2): 185-193, 1990.

36. D. S. Richards. Fast Heuristic Algorithms for Rectilinear Steiner Trees. // Algorithmica, 4 (1989), pp. 191-207.

37. M. Borah, R.M. Owens, and M. J. Irwin. A fast and simple Steiner routing heuristic. // Discrete and Applied Mathematics, 90(1-3): 51-67, 1999.

38. M. Sarrafzadeh and C. K. Wong. Hierarchical Steiner tree construction in uniform orientations. // IEEE Transactions Computer-Aided Design, 11(9): 1095-1103, September 1992.

39. C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. Prim-Dijkstra tradeoffs for improved performance-driven routing tree design. // IEEE Transactions Computer-Aided Design, 14(7):890-896, 1995.

40. A. B. Kahng and G. Robins. A new class of iterative steiner tree heuristics with good performance. // IEEE Transactions Computer-Aided Design, 11(7): 893-902, July 1992.

41. A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.

42. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.

43. G. Georgakopoulos and C. H. Papadimitriou. The 1-Steiner tree problem. // Journal of Algorithms,8:122-130, 1987.

44. A. B. Kahng, 1.1. Mandoiu, and A. Z. Zelikovsky. Highly scalable algorithms for rectilinear and octilinear Steiner trees. // In Proceedings of the Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 827833, 2000.

45. A. Zelikovsky. An 11/6-approximation for the network Steiner tree problem. // Algorithmica 9 (1993), pp. 463-470.

46. C. Chu. FLUTE: Fast lookup table based wirelength estimation technique. // in Proc. ICCAD, 2004, pp. 696-701.

47. C. C. N. Chu and Y.-C. Wong. Fast and accurate rectilinear Steiner minimal tree algorithm for VLSI design. // in Proc. ISPD, 2005, pp. 28-35.

48. M. Cho and D. Z. Pan. BoxRouter: A New Global Router Based on Box

49. Expansion and Progressive ILP. // in Proc. Design Automation Conf., July 2006.

50. M. Pan and C. Chu. FastRoute: A step to integrate global routing into placement. // in Proc. ICCAD, 2006, pp. 464-471.

51. M. Pan and C. Chu. FastRoute 2.0: A High-quality and Efficient Global Router. // In Proc. ASPDAC, pp. 250-255, 2007.

52. B. S. Ting and B. N. Tien. Routing techniques for gate array. // IEEE Transactions on Computer Aided Design, CAD-2(4):301-312, October 1983.

53. R. Nair, S. J. Hong, S. Liles, and R. Villani. Global wiring on a wire routing machine. // In Proceedings of the ACM/IEEE Design Automation Conference, pages 224-231, 1982.

54. K. W. Lee and C. Sechen. A global router for sea-of-gate circuits. // In Proceedings of the European Design Automation Conference, p. 242-247, 1991.

55. V. Betz and J. Rose. Directional bias and non-uniformity in FPGA global routing architectures. // In International Conference on Computer Aided Design, IEEE Computer Society, Washington, DC, pp. 652-659, 1996.

56. V.Betz and J.Rose. VPR:A new packing, placement and routing tool for FPGAresearch. // In 7th International Workshop on Field-Programmable Logic, pp. 213-222, 1997.

57. C. Ebeling, L. McMurchie, S. A. Hauck, and S. Burns. Placement and routing tools for the triptych FPGA. // IEEE Transactions on VLSI Systems, IEEE Press, Piscataway, NJ, pp. 473-482, 1995.

58. M. M. Ozdal and M. D. F. Wong. Archer: A history-driven global routing algorithm. // In Proceedings of International Conference on Computer Aided Design, IEEE Press, Piscataway, NJ, pp. 488-495, 2007.

59. J.A.Roy and I. L.Markov. High-performance routing at the nanometer scale. // In Proceedings of International Conference on Computer Aided

60. Design, IEEE Press, Piscataway, NJ, pp. 496-502, 2007.

61. M. Cho, K. Lu, and D. Z. Pan. Boxrouter 2.0: Architecture and implementation of a hybrid and robust global router. // In Proceedings of International Conference on Computer Aided Design, Press, Piscataway, NJ, pp. 503-508, 2007.

62. J. D. Cho and M. Sarrafzadeh. Four-bend top-down global routing. // IEEE Transactions on Computer-Aided Design, 17(9):793-802, 1998.

63. J. Hu and S. S. Sapatnekar. A timing-constrained algorithm for simultaneous global routing of multiple nets. // In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 99103, 2000.

64. G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. // In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 44-47, 1990.

65. C. Albrecht. Provably good global routing by a new approximation algorithm for multicommodity flow. // In International Symposium on

66. Physical Design, ACM, NY, pp. 19-25, 2000.

67. C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. // in IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, pp. 622-632, 2001.

68. D. G. Luenberger. Linear and nonlinear programming. Addison-Wesley Publishing Company, Reading, MA, 1984.

69. N. Karmarkar. A new polynomial-time algorithm for linear programming. // Combinatorica, 4(4):373-395, 1984.

70. P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. // Combinatorica, 7(4):365-374, 1987.

71. A. Vannelli. An adaptation of the interior point method for solving the global routing problem. // IEEE Transactions on Computer-Aided Design, 10(2): 193-203, 1991.

72. T. C. Hu and E. S. Kuh. Theory and concepts of circuit layout. In T. C. Hu and E. S. Kuh, editors, VLSI Circuit Layout: Theory and Design, pages 3-18. IEEE Press, New York, NY, 1985.

73. R. W. Thaik, N. Lek, and S.-M. Kang. A new global router using zero-one integer linear programming techniques for sea-of-gates and custom logic arrays. // IEEE Transactions on Computer-Aided Design, 12(12): 1479-1494, 1992.

74. J. Heisterman and T. Lengauer. The efficient solution of integer programs for hierarchical global routing. // IEEE Transactions on Computer-Aided Design, 10(6):748-753, 1991.

75. ISPD 2006: http://www.sigda.org/ispd2006/contest.html

76. ISPD 2008: http://www.siqda.org/ispd2QQ8/contest.html

77. D. Kucar. "Partitioning and Clustering" in "The Handbook of Algorithms for VLSI Physical Design Automation," C. 3. Alpert, D. P. Mehta, and S. S.

78. Sapatnekar, editors, pp. 100-132, 2007.

79. L. R. Ford, Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, Princeton, NJ, 1962.

80. N. Karmarkar. A new polynomial-time algorithm for linear programming. // Combinatorica, 4(4):373-395, 1984.

81. R.Tessier. Negotiated A* Routing for FPGAs. // in Proceedings of the Fifth Canadian Workshop on Field-Programmable Devices, 1998.

82. P. O. Fjallstrom. Algorithms for graph partitioning: A survey. // Linkoping Electronic Articles in Computer and Information Science, 3(10), 1998.84. http://www.opencores.org

83. Заглядин Г.Г., Панфилов C.B. Инфраструктура и подсистема планировки кристалла для САПР топологии ИС. // Микроэлектроника и информатика-2006, М.: МИЭТ, 2006. стр. 120.

84. Заглядин Г.Г. Реализация этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. // Микроэлектроника и информатика-2007, М.: МИЭТ, 2007. стр. 67.

85. Заглядин Г.Г. Исследование реализации этапа декомпозиции при создании учебно-исследовательской САПР топологии СБИС. // Сб. науч. Трудов «Проектирование электронной компонентной базы и систем на кристалле» под ред. М.Г. Путри, М.: МИЭТ, 2007. с. 49-55.

86. Заглядин Г.Г. Планировка цепей высокопроизводительных ИС. // Микроэлектроника и информатика-2008, М.: МИЭТ, 2008. стр. 72.

87. Заглядин Г.Г., Многокритериальная планировка цепей СБИС. // Микроэлектроника и информатика-2009, М.: МИЭТ, 2009. стр. 85.

88. Gleb Zaglyadin, Multiobjective Global Routing. // MB-JASS 2009, Москва, 2009.

89. Заглядин Г.Г, Разработка метода многокритериальной глобальной трассировки СБИС. // Микроэлектроника и информатика-2010, М.:1121. МИЭТ, 2010. стр. 73.

90. Заглядин Г. Г., Сырцов И. А., Школа А. В. Алгоритм синтеза множества остовных деревьев для выполнения глобальной трассировки заказных СБИС. // Известия высших учебных заведений. Электроника. №5(85). М: МИЭТ, 2010. стр. 36-40.

91. Заглядин Г. Г., Сырцов И. А. Глобальная трассировка заказных СБИС с использованием множества остовных деревьев. // Естественные и технические науки. №4(48). М: «Спутник+», 2010. стр. 322 326.

92. Заглядин Г.Г. Метод глобальной трассировки цепей субмикронных СБИС с использованием семейства деревьев Штейнера. // Проектирование систем на кристалле: тенденции развития и проблемы, М.: МИЭТ, 2010. стр. 13.