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

РГ6 од

- / АПР 2X3

ДАНИЛИН Александр Александрович

МНОГОКРИТЕРИАЛЬНЫЙ СИНТЕЗ ТОПОЛОГИИ ЦИФРОВЫХ И АНАЛОГОВЫХ БИС НА ОСНОВЕ ОПЕРАТОРНОЙ МОДЕЛИ СВИЧБОКСА

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

Автореферат

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

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

¿Шеи*

Москва -1999

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

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

профессор Щемелинин В.М.

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

профессор Широ Г.Э. Кандидат технических наук Горбунов Ю.З.

Ведущая организация: ГУЛ НИИМА «Прогресс» . Защита состоится «_»_■ на заседании

о —» 11 , ........ ■

диссертационного совета Д 053.02.01 Московского Государственного Инетитута-Электронной Техники (технического университета) (Москва, 103498)

С диссертацией можно ознакомиться в библиотеке МИЭТ.

Автореферат разослан «_»_1999г.

Ученый секретарь Диссертационного совета

кандидат технических наук Н.8. Воробьев

/ /

. /ГЯ - о Л -Л-г>5~, О

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Современная БИС содержит порядка 10-15 миллионов вентилей на кристалле размером 25x25 мм с минимальным топологическим размером ~0.18д. Конструирование такой сложной системы является чрезвычайно трудоемкой и многоплановой задачей, которую невозможно решить без автоматизации проектирования. Одним из самых трудоемких этапов проектирования СБИС является трассировка; для большой схемы требуется обработать ~107-108 соединений. Учет конфигурации соединения может.еще на порядок увеличить размерность задачи. Даже мощности современных вычислительных комплексов для этого недостаточно. Необходимо применять иерархический подход, при котором весь кристалл разбивается на блоки, каждый из которых проектируется отдельно путем его рззбиения на субблоки. Для цифровых БИС важно, чтобы сигнальные цепи и цепи синхронизации попадали в отведенные для них временные рамки, поэтому для уменьшения задержки надо минимизировать длину цепей и количество переходов из слоя и слой. Для аналоговых БИС важно избегать, например, паразитных емкостей, для чего необходимо минимизировать количество теневых сегментов проводников. Оптимальный синтез топологии цифровых и аналоговых БИС во многом зависит от эффективного проектирования прямоугольной топологической ячейки с выводами на ее границе (сзичбокса).

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

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

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

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

Анализ структуры современной схемы проектирования БИС и основных ее алгоритмов.

Анализ существующих методов трассировки свичбокса.

Разработка нового подхода к трассировке свичбокса.

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

Тестирование программного комплекса на стандартных и усложненных примерах.

Методы исследования "В ходе выполнения работы использовались методы общей алгебры, теория множеств, теория графов, алгоритмы на графах, исследование операций, методы объектно-ориентированного программирования.

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

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

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

- На алгебраическом уровне введено понятие Х- простейшей трассировки.' Обоснован синтез топологии в классе Х- простейших трассировок. Показаны возможности ухода от ЫР-полноты задачи трассировки при таком подходе.

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

- Сформулированы критерии оптимизации эскиза на основе предложенных характеристик. Проведена классификация критериев по уровням модели.

- Проведена оценка сложности операторного метода трассировки свичбокса. Показано, что сложность операторного метода синтеза оптимальной Х-трассировки равна 0(n2 logn), где п - число активных выводов на границе свичбокса.

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

Разработаны алгоритмы синтеза трассировки свичбокса на ochodg предложенной математической модели, которые обеспечивают

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

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

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

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

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

Результаты диссертационной работы внедрены в учебный процесс МИЭТ (Зеленоград) и использовались при проектировании топологии БИС на основе базовых кристаллов в ООО «Ангстрем - PTMt, о ^м свидетельствуют прилагаемые акты внедрения

На защиту выносятся:

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

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

- Настройка модели ячейки на различные способы расслоения.

- Эффективные алгоритмы построения оптимальной топологии ячейки.

- Эффективный выбор средств реализации алгоритмов оптимизации топологии ячейки в среде WINDOWS 95/98/NT для персональных ЭВМ.

Структура и объем диссертационной работы Диссертационная работа содержит введение, пять глав, заключение, список литературы (191 наименование) и приложение. Полный объем работы - 176 страниц, в том числе 7 таблиц и 42 рисунка.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении кратко рассматривается современное положение в области проектирования БИС и формулируется цель работы.

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

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

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

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

Мы считаем, что так же как и для общей задачи трассировки, сначала следует разработать план будущего решения, а затем его постепенно уточнять. Этот путь позволяет также преодолеть проблему сложности этой ЫР - полной задачи за счет ограничения на каждой стадии получения решения множества рассматриваемых свойств объекта. На наш взгляд, метод решения задачи свичбокса должен быть;

- многоуровневым (по уровням абстракции),

- многовариантным (внутри каждого уровня абстракции),

- многокритериальным.

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

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

решения расширяется, что увеличивает вероятность реализации эскиза. В то же время это расширение ограничено рассматриваемыми на данном уровне критериями (свойствами решения). Можно показать, что при такой постановке исходная проблема уже не является МР - полной.

Постановка задачи. Ядром современных информационных технологий проектирования БИС является трассировка свичбокса. Под свичбоксом понимается прямоугольная область фиксированных размеров с фиксированными выводами (терминалами) на всех четырех ее сторонах. Выводам приписаны номера цепей. Множество терминалов с одинаковым номером представляет некоторую цепь. Имеется два коммутационных слоя. Выводы назначаются слоям заранее. Задача состоит в соединении выводов каждой цепи внутри области так, чтобы выполнялись условия на минимальные размеры сегментов цепей и минимальные промежутки между сегментами. Реализация цепи представляет собой связное множество горизонтальных и вертикальных сегментов. Переход из одного коммутационного слоя в другой возможен только в концах сегмента. Цепи не должны пересекаться. В первоначальной постановке добавлялись следующие требования: С1. Область свичбокса покрыта сеткой. Выводы и сегменты цепай находятся на ребрах сетки. Соединения сегментов и переходы из слоя в слой возможны только в узлах сетки. Требование не перекрытия (включая касание) в одном слое сегментов разных цепей здесь заменяет все правила проектирования, выраженные на языке геометрических размеров. С2. Горизонтальные сегменты располагаются в одном слое,

вертикальные - в другом. СЗ. Выводы на горизонтальной паре сторон назначены в слой вертикальных сегментов, а выводы на вертикальной паре сторон - в слой горизонтальных сегментов С<? Не разрешается касание (но не пересечение) сегментов различных цепей даже в разных слс-ях

Требования задачи трассировки свичбокса в современной постановке имеют следующий вид:

М1. Имеется не менее двух коммутационных слоев. Псе слои могут быть металлическими или содержать один поликремневый слой.

М2. Каждый слой содержит сегменты преимущественно одного направления.

МЗ. Выводы могут располагаться нерегулярно на Есех сторонах в любом слое, в том числе - друг над другом.

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

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

Мб. Некоторые критические цепи имеют при трассировке приоритет.

М7. Число выводов свичбокса исчисляется сотнями.

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

Анализ известных алгоритмов трассировки свичбокса показывает, что они ориентированы на требования С1 - С4 с небольшими отклонениями от С2 в системе BEAVER в результате постпроцессорной обработки решения.

Нам однако неизвестны трассировщики, способные успешно справляться с современными требованиями (М1 - М7).

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

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

Уточнение характеристик объекта происходит в следующем порядке: сначала рассматривается простота многосвязной области, где нас интересует оценка взаимодействия элементарных областей. Затем осуществляется привязка выводов к стороне или их группировка. Далее вводится прямоугольная форма объекта и направление сегмента (горизонтальное/вертикальное). После чего осуществляется точная привязка вывода и сегмента стороне и слою (расслоение), и вводятся физические размеры.

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

Класс топологических трассировок. Основным элементом предлагаемого подхода является ограничение класса топологических вариантов трассировок свичбокса, в котором ищется решение.

Пусть А=(а).....ап) - циклический вектор границы свичбокса; а,е1 =

{1.....т}, (¡=1,...,п); I - множество номеров цепей; б,,...^™- число

компонент каждой цепи в А.

Граница свичбокса отображается непрерывной замкнутой кривой без самопересечений с точками, соответствующими компонентам вектора А.

Количественные характеристики вектора границы представим набором

Ы1=<П,ГП, Б).....зт >.

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

Количественные характеристики топологической трассировки представим набором Мт=< кг, ко. кп >, где кг, ко, кп - число граней, точек соединений ветвей и пересечений цепей.

Определение 1. Топологическая трассировка Т0 называется простейшей, если число ее граней

ь° = тт*г (1)

НА) '

Определение 2. Топологическая трассировка Т называется X-простейшей, если число ее граней

кг<;*?+Х (2)

где Х>0 - некоторый параметр.

В дальнейшем поиск решения будет вестись в классе простейших или Х-простейших трассировок.

Количественные характеристики трассировки зависят от значений набора и порядка компонент вектора А.

Определим связь простейших топологий с характеристикой кс. Топология отдельной цепи может иметь несколько вариантов, два из которых показаны на Рис 1.

(а) (б)

Рис.1 Варианты топологии цепи.

Очевидно следующее

Утверждение 1. Число граней трассировки отдельной цепи не зависит от ее топологии.

В варианте топологии типа звезда (Рис. 1а) кс=1 принимает наименьшее возможное значение, а в топологии с точками ссединенил кратности 3 Рис.16) кс=5,-2 принимает наибольшее значение.

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

(а) кг=8 (б) кп=7

Рис. 2. Варианты трассировки двух цепей.

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

Поэтому справедливо следующее

Утверждение 2. Существует подкласс простейших трассировок, для которых

-2) = и-2я» (3)

I*)

Заметим, что при в,=2 точка соединения ветвей не вводится, так как она не влияет на простоту трассировки.

Следствие. Процесс построения простейшей топологической трассировки сводится к реализации некоторой последовательности пар ветвей цепей.

Рассмотрим влияние параметра кп на простоту трассировки.

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

Из выражения (1) и сделанного замечания следует, что число граней трассировки цепей, каждая из которых (для б,>2) реализована на основе точек соединения ветвей кратности 3, равно

к1=п-т+км+1 (4)

Замечание. Из выражений (1), (2), (4) следует, что простейшая топологическая трассировка содержит наименьшее возможное число пересечений, а параметр X имеет смысл допустимого превышения этого числа.

Поиск решения в классе простейших и X - простейших топологических трассировок можно обосновать следующими соображениями:

Структура простейшей трассировки свидетельствует о хорошем стиле проектирования, так как в ней отсутствуют лишние пересечения (Рис. 3)

Рис. 3. Пример избыточных пересечений двух цепей.

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

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

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

н=ь- ГгП

(а) (б)

Рис. 4. Пример противоречия критериев простоты топологической трассировки и площади.

X - простота трассировки характеризует простоту взаимодействия цепей в процессе их укладки в области сгичбокса.

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

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

Кроме того, имеется некий инструмент, позволяющий для критических цепей управлять временной (порядок следования) и пространственной ■ (назначение в слой) приоритетностью реализации соединений.

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

Постановка задачи. Рассматривается прямоугольная область на плоскости с границей P={T,L,B,R}, где T,L,B,R - верхняя, левая, нижняя и правая стороны. На границе определяют множество X позиций, отсчитываемых для Т и В слева направо, а для L и R - снизу вверх. На множестве X задана целочисленная функция f(x), равная 0 для незадействованной позиции х и номеру инцидентной цепи из списка N={1,2,...,п} для задействованной. Таким образом, образуется разбиение

н

Х= IJ X,, где Х,={х: f(x)=i}. Требуется для каждого X, (i*0) построить внутри

/•О

области связное множество вертикальных и горизонтальных сегментов M,=Vi и G„ причем каждое хеХ; является концом некоторого элемента из М^ Сегмент определяется парой точек - его концами. При построении системы деревьев на X однонаправленные сегменты разных множеств не должны пересекаться. Разнотипные сегменты могут пересекаться, но не касаться друг друга. Нельзя в качестве сегментов использовать участки границы. Решение должно быть оптимальным по заданному критерию.

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

Заметим, что эта задача является более общей, чем та, что представлена в главе 2.

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

- взаимное расположение задействованных выводов;

- соответствие выводов сторонам; понятия горизонтали и вертикали;

- взаимное расположение пар выводов на противоположных сторонах;

- точное расположение выводов на границе.

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

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

Граница Р описывается замкнутым циклическим вектором

А = (а,, а2.....а„) (5)

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

Область трассировки разбивается на кольцеобразные зоны, границы между которыми также моделируются замкнутыми циклическими векторами. Графическим образом множества М, является некоторое дерево на Х^. Система деревьев описывается узлами, соединяющими ветви, и пересечениями ветвей, приписанными зонам по некоторым правилам.

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

Т(А)=(Ао,А,.....Ак); (6)

Ао=А; Ам=Ч',(А|), (¡=0.....К-1); А„=0. (7)

Операторы У, являются композициями выбираемых из некоторого базиса операторов, отображающих узлы, пересечения или их сочетания. Возможные базисы отличаются сложностью элементов: П, = {ф., 1., 0.}; Л2 ={а($,я), р(5,я)}, (8) где «р, - перестановка местами а» и а,.,(а, ф а,.,), Т. и 9, - удаление а, из вектора (при а, = а,„ в первом и уникальности а, во втором случае); ^(з.р) - перестановка а, с I различными компонентами справа (я>0) и слева (д<0) от нее; «(э^) - композиция операторов ф(э.д) и а р(з,д) -операторов «(б^) и 0,.„(я>0); аналогично определяются « и [I для д<0.

Заметим, что операторы <р, и f. моделируют пересечение и узел, а a(s,q) и P(s,q) - более сложный конструкторский элемент типа "диффузионный канал".

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

Построение оптимальной трассировки сводится к синтезу соответствующего минимального оператора, например, в базисе Cî2={a(s,q), P(s,q)}. Минимальным оператором называется композиця наилучших независимых операторов а и (3, то. есть таких, для которых каждая компонента а вектора фазы трассировки, выбираемая из соответствующего интервала, удовлетворяет условию bA3aAibA2a (q>0) аДэЬД2аЛ,Ь (q<0) (9)

где Дз, Ai, Д2 - части вектора не содержащие ни а ни b, а ограничивающие а и b соответствуют концам интервала.

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

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

простейших многосвязных областей трассировки. Сужение множества М(Т) выполняется при использовании новых критериев отбора.

Заметим, что критерий минимизации числа пересечений, выражающий простоту области трассировки, может вступить в некоторое противоречие с критериями на более низких уровнях модели объекта, например, с его площадью. Для достижения компромисса между конкурирующими критериями допускается расширение множества М(Т) включением в него алгебраических моделей близких к оптимальным (>.-простейших трассировок).

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

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

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

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

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

Оценка сложности операторного метода трассировки свичбокса.

Пусть А=(а1.....ап) - вектор границы свичбокса, где п- число активных

выводов.

Оценим сложность метода в наихудшем случае.

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

М,= с, п2+ с2п!одп=0(п2) Рассмотрим граф, вершинами которого являются пары, а ребро между двумя парами существует тогда и только тогда, когда они не могут быть выбрать в один минимальный оператор. Тогда перечисление всех минимальных операторов на отдельной фазе трассировки сводится к поиску максимальной клики графа, который имеет сложность 0(п1одп). Одновременно выбирается оптимальный по заданным критериям минимальный оператор. Таким образом,

N2= 0(п1одп).

Число фаз в наихудшем случае равно п-1.

Поэтому сложность синтеза операторной модели простейшей трассировки в наихудшем случае равна 1одп

Ы= Ы,+(п-1) Ыг=0(п21одп).

Очевидно, что при фиксированном X ту же ассимптотическую оценку имеет сложность синтеза операторной модели Х-простейшей трассировки в наихудшем случае.

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

Для иллюстрации подхода и его изучения была разработана программа Operator Model Router (OMR). Она представляет собой 32х разрядное приложение, написанное под Windows 95/98/NT на Delphi 3 и предназначена для поиска решений трассировки свичбоксов различной сложности. Максимальная оценка размерности решаемой задачи - около 300-400 выводов на границе свичбокса,

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

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

Интерфейс программы позволяет сосредоточиться на самом примере и на его свойствах. Основными элементами работы с программой являются разделы «Данные» и «Лог».

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

Раздел «Лог» предназначен для отображения результатов обработки информации. Он разбит на две основных секции: секцию текстовой

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

Графическая секция раздела представляет собой собственно топологию свичбокса. По своей сути она интерактивна, что позволяет как во время процесс построения решения, так и после него считывать/изменять или дополнять информацию (см. Работа с графической моделью решения).

Общий алгоритм работы программы сводится к следующим основным шагам:

- Загрузка и анализ описания свичбокса

- Загрузка и анализ критериев минимизации

- Формирование списка пар с учетом ограничений, разбиение их на группы.

- Формирование списка операторов, получение готового решения.

Это самый верхний уровень описания процесса построения модели.

Новый конструкторский элемент. Один из путей дальнейшего

развития методов проектирования нам видится в создании новых конструкторских элементов.

Рассмотрим ситуацию, изображенную на Рис. 5.

а). б). в).

Рис. 5. Пример использования разделяемого узла сетки

традиционного решения для такой ситуации. Из рисунка видно, что тратится четыре узла сетки. Представим себе, что технология позволяет нам качественно реализовывать так называемые разделяемые узлы сетки (Рис.6). Тогда рассматриваемый пример можно решить с использованием только одного узла сетки (Рис.56, в).

Такой новый конструкторский элемент позволил бы нам решать задачу трассировки значительно эффективнее, ведь площадь области трассировки уменьшилась, что повлекло бы за собой снижение потребляемой мощности и

Исследования

проводились на IBM-совместимом компьютере с процессором Pentium 100 МГц. Размер оперативной памяти - 64Мб.

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

Пример Дейча. Сложный пример свичбокса Дейча хорошо известен и встречается во многих статьях. Мы проводили тестирование на сложном (dificult) и более сложной (more dificult) примере Дейча. В большинстве из них приводится только одно решение для него.

стоимости кристалла.

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

Рис. 6. Новые конструкторские элементы

Рис 7. Результат трассировки примера сложного примера Дейча Мы же приведем несколько, продемонстрировав возможности 1ашего подхода настраиваться на различные критерии.

Ниже приведены две таблицы сравнительных характеристик работы 1звестных алгоритмов для этого примера. Габл.2 Сложный пример Дейча

Трассировщик Число перех. Длина Доп. Треки Время (сек)

DETCUR 67 564 - ?

GSR 58 577 1 . 1

MCR 63 567 - ?

BBLSR 59 560 - 5

WEAVER 41 531 / - 1508

SWR 65 543 - 3

BEAVER 35 547 - 1

OMR 41 559 - 0.01

Табл.3 Более сложный пример Дейча

Трассировщик Число перех. Длина Время (сек.)

GSR 39 541 4

MIGHTY 64 539 70

BEAVER 34 536 1

OMR 41 544 0.015

Результат работы программы с критерием минимизации LEVEL = SclearbendS +$vias$ +$length$ +$shadow$ (см. Табл. 1) показан на Рис.7.

Результат работы программы с критерием минимизации LEVEL = $vias$ +$length$ (см. Табл. 1) показан на Рис.8.

— — — I t

— _ __ —

—---

—

—

- _ — L

— — — -

— — -- — -i —

*7S«7III« ♦ « • И « • Р I в t

Рис. 8 Пример Дейча с нестрогим расслоением

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложен новый метод решения задачи трассировки свичбокса, отличающийся следующими основными чертами:

- многоуровневость

- многовариантность

- ^ногокритериапьность

2. Выделены алгебраический, топологический и геометрический уровни задачи трассировки свичбокса.

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

4. Доказано, что оценка временной сложности синтеза Х-простейшей трассировки свичбокса в наихудшем случае равна О(п21одп), где п -число задействованных цепями выводов свичбокса.

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

6. Сформулированы критерии оптимизации эскиза на основе предложенных характеристик. Проведена классификация критериев по уровням модели.

7. Предложены и обсуждены варианты трассировки критических цепей.

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

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

10. Разработан входной язык исходных данных, позволяющий пользователю формировать любой критерий проектирования.

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

МИЭТ (Зеленоград) и использовались при проектировании топологии БИС на основе базовых кристаллов в ООО «Ангстрем - РТМ», о чем свидетельствуют прилагаемые акты внедрения.

1С

По материалам диссертации опубликованы следующие печатные

работы:

1. Данилин А.А, Представление и обработка данных операторной модели трассировки свичбокса, Всероссийская межвузовская научно-техническая конференция «Микроэлектроника i информатика -98». Тезисы докладов, М.: МИЭТ, 1997, с.31.

2. Щемелинин В.М., Данилин А.А, Программная реализация трассировки свичбокса, Известия вузов. ЭЛЕКТРОНИКА. №3-4, 1997 с.75-79

3. Данилин А.А., Концепция построения топологии на основе операторного метода, Всероссийская межвузовская научно-техническая конференция «Микроэлектроника и информатика -98» Тезисы докладов, ч.1. М.: МИЭТ, 1998, с.21

4. Данилин А.А., Исследования многоуровневой модели трассировм свичбокса, Всероссийская межвузовская научно-техническая конференция «Микроэлектроника и информатика -99». Тезись докладов, М.: МИЭТ, 1999, с.100

5. Щемелинин - В.М., Данилин А.А., Многоуровневая модель трассировки свичбокса, Известия вузов. ЭЛЕКТРОНИКА №3. 1999. с 65-72

6. Shchemelinin V.M., Danilin А.А., The Switchbox Routing Specificatior Expansion Method, First International Workshop "Multi-Architecture Low Power Design", September 13-14, Moscow, 1999, p. 89-99

7. Щемелинин B.M., Данилин A.A., Трассировка свичбокса методоь расширения спецификаций, Известия вузов. ЭЛЕКТРОНИКА. №6 1999

Подписано в печать

Заказ №232 Тираж 70 экз.

Отпечатано в типографии МИЭТ

Объем 1.1 уч. изд. л.

ВВЕДЕНИЕ.

ГЛАВА 1 МЕТОДЫ ФИЗИЧЕСКОГО ПРОЕКТИРОВАНИЯ БИС.

1.1 ДЕКОМПОЗИЦИЯ.

1.2 ПЛАНИРОВКА И РАЗМЕЩЕНИЕ.

• 1.3 ТРАССИРОВКА.

1.4 УПАКОВКА.

1.5 ЭКСТРАКЦИЯ И ВЕРИФИКАЦИЯ.

1.6 ПРОБЛЕМА СВИЧБОКСА И АЛГОРИТМЫ ЕЕ РЕШЕНИЯ.

1.6.1 ОСТОРОЖНЫЙ ШАГ

1.6.2ЖАДНЫЕ АЛГОРИТМЫ.

1.6.3 ИСПРАВЛЕНИЕ И ПОВТОРНАЯ ТРАССИРОВКА.

1.6.4 ЛОКАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ.

1.6.5 МЕТОД РАЗРЕЗАНИЯ И ПЕРЕТРАССИРОВКИ.

1.6.6 ТЕХНИКА ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ.

1.6.7 ДРУГИЕ ТРАССИРОВЩИКИ СВИЧБОКСА.

ВЫВОДЫ.

ГЛАВА 2 НОВЫЙ ПОДХОД К ПРОБЛЕМЕ СВИЧБОКСА.

2.1 ПОСТАНОВКА ЗАДАЧИ.

2.2 ПРЕДЛАГАЕМЫЙ ПОДХОД.

2.2.1 КЛАСС ТОПОЛОГИЧЕСКИХ ТРАССИРОВОК.

2.2.2 МНОГОУРОВНЕВАЯ МОДЕЛЬ ТРАССИРОВКИ СВИЧБОКСА.

2.2.3 КРИТЕРИИ ПРОЕКТИРОВАНИЯ.

ВЫВОДЫ.

ГЛАВА 3 ФОРМИРОВАНИЕ МОДЕЛЕЙ НА РАЗНЫХ УРОВНЯХ

АБСТРАКЦИИ ОБЪЕКТА.

3.1 ПОСТАНОВКА ЗАДАЧИ.

3.2 ОПЕРАТОРНАЯ МОДЕЛЬ.

3.3 ТОПОЛОГИЧЕСКАЯ МОДЕЛЬ. ВВЕДЕНИЕ

ОРТОГОНАЛЬНЫХ НАПРАВЛЕНИЙ. 3.4 ГЕОМЕТРИЧЕСКАЯ МОДЕЛЬ. ВЛОЖЕНИЕ В

ОРТОГОНАЛЬНУЮ СЕТКУ.

3.5 ОБСУЖДЕНИЕ МНОГОУРОВНЕВОЙ МОДЕЛИ.

3.5.1 МЕРА ПРОСТОТЫ МОДЕЛИ.

3.5.2ГРУППИРОВКА ПАР.

3.5.3ПРАВИЛА УКЛАДКИ.

3.5.4ТРАССИРОВКА КРИТИЧЕСКИХ ЦЕПЕЙ.

3.5.5 ОЦЕНКА СЛОЖНОСТИ ОПЕРАТОРНОГО МЕТОДА ТРАССИРОВКИ СВИЧБОКСА.

ВЫВОДЫ.

ГЛАВА 4 СИСТЕМНЫЕ АСПЕКТЫ ПРОБЛЕМЫ.

4.1 ОПИСАНИЕ ВХОДНЫХ ДАННЫХ.

4.2 РАБОТА С ГРАФИЧЕСКОЙ МОДЕЛЬЮ РЕШЕНИЯ.

4.3 НАСТРОЙКИ И ПРЕДПОЧТЕНИЯ.

4.4 КОМПИЛЯЦИЯ РЕШЕНИЯ.

4.5 СЧИТЫВАНИЕ ИНФОРМАЦИИ О СВИЧБОКСЕ.

4.6 ПОСТРОЕНИЕ ВСЕХ ПАР.

4.7 ОБЩАЯ ИНИЦИАЛИЗАЦИЯ МОДЕЛИ.

4.8 ОПЕРАТОРНАЯ ИНИЦИАЛИЗАЦИЯ МОДЕЛИ.

4.9 ПОСТРОЕНИЕ ОПЕРАТОРОВ.

4.10 РАЗМЕЩЕНИЕ ОПЕРАТОРА В ПРОСТРАНСТВЕ

СВИЧБОКСА.

-44.11 НОВЫЙ КОНСТРУКТОРСКИЙ ЭЛЕМЕНТ.

ВЫВОДЫ.

ГЛАВА 5 РЕЗУЛЬТАТЫ МАШИННЫХ ЭКСПЕРИМЕНТОВ.

5.1 ПРИМЕР ДЕЙЧА.

5.2 УСЛОЖНЕННЫЙ ПРИМЕР ДЕЙЧА.

5.3 ПЕДАГОГИЧЕСКИЙ ПРИМЕР.

5.4 ПРИМЕР С ЕДИНСТВЕННЫМ РЕШЕНИЕМ.

5.5 ПЛОТНЫЙ ПРИМЕР.

5.6 ТРУДНЫЙ ПРИМЕР.

5.7 ВЫВОДЫ.

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

Современная БИС содержит порядка 10-15 миллионов транзисторов на кристалле размером 25x25 мм с минимальным топологическим размером -0.18ц. Конструирование такой сложной системы чрезвычайно трудоемкая и многоплановая задача, которую невозможно решить без автоматизации проектирования. Одним из самых важных этапов проектирования СБИС является этап трассировки. Если представить себе, что каждый вентиль в схеме участвует в среднем в двух трех соединениях и имеет 3 и более контакта, то получается, что на этапе трассировки для такой схемы должно обрабатываться колоссальное количество (порядка 4.5х107) соединений. Учет конфигурации соединения может еще на порядок увеличить размерность задачи. Даже мощности современных вычислительных комплексов для этого недостаточно. Единственным пригодным пока способом решать такую задачу остается иерархический подход, при котором весь кристалл разбивается на блоки, каждый из которых проектируется отдельно путем его разбиения на субблоки. Чаще всего эти блоки имеют прямоугольную форму, но разные размеры. Помимо задачи согласования, возникает задача оптимальной укладки таких блоков с целью минимизации площади кристалла. Однако, это не единственный критерий. Для цифровых БИС важно, чтобы сигнальные цепи и цепи синхронизации попадали в отведенные для них временные рамки, поэтому для уменьшения задержки надо минимизировать длину цепей и количество переходов из слоя в слой. Для аналоговых БИС важно избегать, например, паразитных емкостей, для чего необходимо минимизировать количество теневых сегментов проводников.

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

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

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

Диссертация состоит из введения, пяти глав и заключения.

5.7 ВЫВОДЫ

1. Проведено тестирование разработанного алгоритма на известных классических примерах.

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

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

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

5. Показана возможность применения 5-геометрии (5=4) для получения решения.

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

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

ЗАКЛЮЧЕНИЕ

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

2. Предложен новый метод решения задачи трассировки свичбокса, отличающийся следующими основными чертами:

3. многоуровневость

4. многовариантность

5. многокритериальное^

6. Выделены алгебраический, топологический и геометрический уровни задачи трассировки свичбокса.

7. На алгебраическом уровне введено понятие Х- простейшей трассировки. Обоснован синтез топологии в классе X-простейших трассировок. Показаны возможности ухода от №-полноты задачи трассировки при таком подходе.

8. Доказано, что оценка временной сложности синтеза X-простейшей трассировки свичбокса в наихудшем случае равна 0(п21о^), где п - число задействованных цепями выводов свичбокса.

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

10. Сформулированы критерии оптимизации эскиза на основе предложенных характеристик. Проведена классификация критериев по уровням модели.

11. Предложены и обсуждены варианты трассировки критических цепей.

12. При отсутствии решения задачи трассировки свичбокса дан метод построения расширения свичбокса, в котором оно

- 1Э4 существует. Это полезно для обратной связи на глобальную трассировку в общем цикле синтеза топологии БИС для перепланировки цепей.

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

14. Разработан входной язык исходных данных, позволяющий пользователю формировать любой критерий проектирования.

15. Обоснован выбор структур данных и описаны основные процедуры.

- 155

1. AJK82. K. J. Antreich, F. M. Johannes, F. H. Kirsch. A new aproach for solving the placement problem using force models. Proceedings of the IEEE International Symposium on Circuits and Systems, pages 481-486, 1982.

2. Ake81. S. B. Akers. On the use of the linear assignment algorithm in module placement. Proceedings of 18th ACM/IEEE Design Automation Conference, pages 137-144, 1981.

3. AK90. J. Apte, G. Kedam. Heuristic algorithms for combinedstandard cell and macro block layouts. Proceedings of the 6th MIT. Conference on Advanced Research in VLSI, pages 367-385, 1990.

4. ARML99. Arindam Mukherjee, Ranganathan Sudhakar, Malgorzata Marek-Sadowska, Stephen I. Long, Wave Steering in YADDs: A Novel Non-Iterative Synthesis and Layout Technique, 36th Design Automation Conference, New Orleans, LA, June 21-25, 1999, p. 466

5. BP83. M. Burstein, R. Pelavin. Hierarchical wire routing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems CAD-2 (4) (October 1983). 223-234.

6. Bia89. J.Bianks. Partitioning by probability condensation.

7. Proceeding of Design Automation Conference, pages 758761, 1989.

8. BJ86. P. Bannerjee, M. Jones. A parallel simulated annealing algorithm for standard cell placement on a hypercube computer. Proceedings of the IEEE International Conference on Computer Design, page 34,1986.

9. H. N. Brady. An approach to topological pin assignment. IEEE Transactions on Computer-Aided Design, CAD-3: 250-255, July 1984.

10. M. A. Breuer. A class of min-cut placement algorithms. Proceedings Design Automation Conference, pages 284-290, 1977.

11. G. Chartrand and Lesniak. Graphs and Digraphs. Wadsworth and Brooks/Cole Inc., Monterey, 1986.- ID /

12. C.Cheng, E.Kuh. Module placement based of resistive network optimization. IEEE Transactions on Computer-Aided Design, CAD-3:218-225, July 1984.

13. H. M. Chan, P. Mazumber. A genetic placement for macro cell placement. Technical report, Department jf Electrical Engineering and Computer Science, University of Michigan, 1989.

14. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematic , 1:269-271,1959. H.N.Djidjev. On the problem ofpartitioning planar graphs. SIAM Journal on Algebraic and Discrete Methods, 3(2):229-240, 1982.

15. W. E. Donath, R. J. Norman, В. K. Agrawal, S. E. Bello Sang Yong Han, J. M. Kurtzberg, P. Lowy, R. I. McMillan. Timing driven placement using complete path delays. Procee dings of 27th ACM/IEEE Design Automation Conference, pages 84-89, 1990.

16. W. A. Dees, P. G. Karger. Automated rip-up and reroute techniques. Proceeding of Design Automation Conference, 1982.

17. Edward М. Reingold, Jurg Nivevergelt, Narsingh Deo,

18. Combinatorial algorithms. Theory and practice. Prentice

19. Hall, Inc., Englewood Cliffs, New Jersey 1977.

20. A. E. Dunlop et. al. Chip layout optimization using criticalpath weighting. Proceedings of 21st ACM/IEEE Design

21. Automation Conference, pages 133-136,1984.

22. Y. Ogawa et. al. Efficient placement algorithms optimizingdelay for high-speed eel masterslice Isi's. Proceedings of23rd АСМЛЕЕЕ Design Automation Conference, pages 404410,1986.

23. W. E. Donath et. al. Timing driven placement using complete path delays. Proceedings of 27th ACM/IEEE Design Automation Conference, pages 84-89,1990.- юи

24. B. Eschermann. Hierarchical placement for macrocells with simultaneous routing area allocation. Technical Report Mem. UCB/ERL M88/49, Univ. Calif., Berkeley, 1988. I.R.Ford, D.R.Fulkerson. Flows in Networks. Princeton University Press, 1962.

25. J.Frankle, M.R.Karpp. Circuit placement and cost boundb by eigenvector decomposition. Proceeding of IEEE International Conference on Computer-Aided Design, pages 414-417,1986.

26. C.M. Fiduccia, R.M. Mattheyses. A linear-time heuristics for improving network partitions. Proceedings of the 19th Design Automation Conference, pages 175-181,1982.

27. C. Fowler, G. D. Hachtel, 1. Roybal. New algorithms for hierarchical place and route of custom vlsi. Proceeding of International IEEE Conference on Computer-Aided Design, pages 273-275, 1985.

28. H. J.Groeger. A new approach to structural partitioning of computer logic. Proceeding of Design Automation Conference, pages 378-383,1975.

29. GCW83. I. G. Gopal, D. Coppersmith, C. K. Wong. Optimal wiring of movable terminals. IEEE Transactions on Computers, C-32: 845-858, September 1983.

30. GJ77. M. R. Garey, D. S. Johnson. The rectilinear steiner treeproblem is np-complete. SI AM Jornal Applied Mathematics 32:826-834, 1977.

31. H82. C.P. Hsu. A new two-dimensional routing algorithm. Proc. 19th Design Automation Conference. 1982. 46-50.

32. HC85. Y. I. Hsich, C.C. Chang. A modified detour router. Proc. Int. Conf. Computer-Aided Design. 1985. 301-303.

33. HVW85. J. M. Ho, G. Vijayan and C. K. Wong. A new approach to the rectilinear steiner tree problem. IEEE Transactions on Computer-Aided Design, 9(2): 185-193, February 1985.

34. Han76. M. Hanan. On steiner's problem with rectilinear distance.

35. SIAM Journal of Applied Mathematics, 30(1): 104-114. January 1976.

36. HVW89. J. M. Ho, G. Vijayan and C. K. Wong. Constructing the optimal rectilinear steiner tree derivable from a minimum spanning tree. Proceedings of IEEE International Conference on Computer-Aided Design, pp. 5-8, November 1989.

37. Hwa76a. F. K. Hwang. An o(nlogn) algorithm for rectilinear steiner trees. Journal of the Association for Computing Machinery, 26(1):177-182, April 1976.

38. Hwa76b. F. K. Hwang. On Steiner minimal trees with rectilineardistance. SIAM Jornal of Applied Mathematics, 30(1): 104114, January 1976.

39. Hwa79. F. K. Hwang. An o(nlogn) algorithm for suboptimal rectilinear steiner trees. Transactions on Circuits and Systems, 26(1): 75-77, January 1979.

40. Hal70. K.M.Hall. An r-dimensional quadratic placement algorithm. Management Science, 17:219-229, November 1970.

41. Hit70. R.B.Hitchcock. Partitioning of logic graphs: A theoretical analysis of pin reduction. Proceeding of Design Automation Conference, pages 54-63,1970.

42. Haj88. B. Hajek. Cooling schedules for optimal annealing. Oper. Res. pages 311-329, May 1988.

43. HRSV86. M. D. Huang, F. Romeo, A. Sangiovanni-Vincentelli. Anefficient general cooling schedules for simulated annealing. Proceedings of the IEEE International Conference on Computer-Aided Design, pages 381-384,1986.

44. HK72. M. Hanan, J. M. Kurtzberg. A review of placement andquadratic assignment problems. SIAMRev., 14(2): 324-342, April 1972.

45. HWA78. M. Hanan, P. K. Wolff, B. J. Agule. Some experimentalresults on placement techniques. J. Design Automation and Fault-Tolerant Computing, 2: 145-168, May 1978.

46. HNY87. P. S. Hange, R Nair, E. J. Yoffa. Circuit placement for predictable performance. Proceeding of International Conference on Computer-Aided Design, pages 88-91,1987.

47. Had75. F. Hadlock. Finding a maximum cut of a planar graph inpolynomial time. SIAM Journal of Computing, 4, no.3:221-225, September 1975.

48. Hig69. D. W. Hightower. A solution to the line router problem on ait.continous plane. Proc. 6 Design Automation Workshop, 1969.

49. HAY99. Hsiao-Pin Su, Allen C.-H. Wu, Youn-Long Lin 16.1 A Timing-Driven Soft-Marco Resynthesis Method in Interaction with Chip Floorplanning. 36 Design- iut

50. Automation Conference, New Orleans, LA, June 21-25, 1999, p. 262

51. S.Kirkpatrick, C.D.Gellat, M.R.Vecchi. Optimization by simulated annealing. Science, 220:671-680, May 1983.- iOJ

52. W.Kernigan, S.Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:391307, 1970.

53. C.Kring, A.R.Newton. A cell-replicating approach to minicut-based circuit partitioning. Proceeding of IEEE International Conference on Computer Design, pages 122125, November 1983.

54. B. Krishnamurthy. An improved mincut algorithm for partitioning vlsi networks. IEEE Transactions on Computers, pages 438-446,1984.

55. D. T. Lee, J. M. Smith and J. S. Liebman. An o(nlogn) heuristic algorithm rectilinear steiner tree problem. Engineering Optimization, Vol. 4(4): 179-182, 1980.

56. E.L.Lawler, K.N.Levitt, J.Turner Module clustering to minimaze delay in digital networks. IEEE Transactions on Computers, C-18(l):47-57, January 1969.

57. R. J.Lipton, R.E.Tarjan. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics, 36(2): 177189, 1979.

58. J. Lam, J. Delosme. Performance of a New Annealing Schedule. Proceedings of the 25 Design Automation Conference, pages 306-311, 1988.

59. B. Lokanathan, E. Kinnen. Performance optimized floor planning by graph planarization. Proceedings of 26 ACM/IEEE Design Automation Conference, pages 116-121, 1989.

60. A. Leblond. Caf: A computer-assisted floorplanning tool. Proceedings of the 20th Design Automation Conference, pages 747-753, 1983.

61. C. Y. Lee. An algorithm for path connections and its applications. ERE Transactions on Electronic Computers, 1961.

62. F.F. Moore. The shortest path through a maze. Annals of the Harvard Computation Laboratory. Vol.30. Pt.ll (Harvard Univ. Press. Cambridge. MA. 1959) 185-192.

63. D.P.Mehta. L-shaped corner switching data structures. Proceedings of the Fourth Great Lakes Symposium on VLSI, pages 34-37, March 1994.

64. MBSV91. R.Murgai, R.K.Brayton, A.Sangiovanni- Vincentelli. On clustering for minimum delay/area. Proceeding of IEEE International Conference on Computer-Aided Design, pages 6-9, November 1991.

65. Mil84. G.L.Miller. Finding small simple cycle separator for 2-connected planar graph. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pages 376382,1984.

66. McF83. M.C.McFarlald. Computer-Aided partitioning of behavioral hardware description. Proceeding of Design Automation Conference, pages 472-478,1983.

67. McF86. M.C.McFarlald. Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral description. Proceedings of the 23rd Design Automation Conference, pages 474-480,1986.

68. MRR53. N.Metropolis, A.Rosenbluth, M.Rosenbluth. Equation of state calculations by fast computing machines. Journal of Chemistry and Physics, pages 1087-1092, 1953.

69. MSL89. M. Marek-Sadowska, S. P. Lin. Timing driven placement.

70. Proceeding of International Conference on Computer-Aided Design, pages 94-97,1989.

71. MR78. L. Mory-Rauch. Pin assignment on a printed circuit board.

72. Proceedings of the 15th Design Automation Conference, pages 70-73,1978.

73. MTDL90. K. McCullen, J. Thorvaldson, D. Demaris, P. Lampin. A system for floorplanning with hierarchical placement and routing. Proceedings of European Design Automation Conference, pages 262-265,1990.- IUO

74. S. Mohan, P. Mozumbar. Wolverines: Standard cell placement on a network of workstations. IEEE Transactions on CAD of Integrated Circuits and Systems, 12: 1312-1326, September 1993.

75. K. Mikami, K. Tabuchi. A computer program for optimal routing of printed circuit connectors. IFIPS Proc., H47:1475-1478, 1968.

76. J. Ousterhoust. Corner stitching: A data-structuring technique for vlsi layout tools. IEEE Transactions on Computer-Aided Design, CAD-3, January 1984. T. Ohtsuki. Partitioning, Assignment and Placement. North-Holland, 1986.

77. C. H. Paradimitriou and K. Steigliz. Combinatorial Optimization Algorithms and Complexity. Prentice-Hall, Inc., 1982.

78. F. Preparata and M. I. Shamos. Computational Geometry. An Introductoin. Springer- Verlag, 1985.

79. R. Putatunda, D. Smith, M. Stebinsky, C. Pushak, P. Patent. Vital: Fully automatic placement strategies for very large semicustom designs. International Conference on Computer Design, pages 434-439,1988.

80. PMSK90. M. Pedram, M. Marek-Sadowska, E. S. Kuh. Floorplanning with pin assignment. Proceeding of International Conference on Computer-Aided Design, pages 98-101,1990. Pat81] A. M. Patel. Partitioning for vlsi placement problem.

81. Proceedings of 18th ACM/IEEE Design Automation Conference, pages 137-144,1981. PCT99. Pei-Ning Guo, Chung-Kuan Cheng, Takeshi Yoshimura, An

82. O-Tree Representation of Non-Slicing Floorplan and Itsit.

83. Custom Integrated Circuits. 1987. 629-632. RF83. R.L. Rivest, C.M. Fiduccia. A greedy channel router.

84. RVS84. F.Romeo, A.S.Vincentelli, C.Sechen. Research on simulated annealing at berekeley. Proceeding of IEEE International Conference on Computer Design, pages 652-657,1984.

85. F. Romeo, A. Sangiovanni-Vincentelli. Convergence and finite time behavior of simulated annealing. Proceedings of the 24 Conference on Decision and Control, pages 761 -767, 1985.

86. Щемелинин B.M. Метод трассировки сложных схем. Известия вузов. ЭЛЕКТРОНИКА. №1, 1997, с.66-72 Щемелинин В.М. Методы автоматического синтеза топологии заказных БИС. Докторская диссертация, Москва, МИЭТ, 1991

87. J.R. Stenstrom, R.M. Matteyses. Switch box routing the greedy way. Proc. Int. Conf. Computer-Aided Design. 1985. 307-309.

88. H. Shin, A. Sangiovanni-Vincentelli. Mighty: a rip-up and reroute detailed router. Proc. Int. Conf. Computer-Aided Design. 1986. 2-5.

89. C. Sechen, A. Sangiovanni-Vincentelli. The timber wolf placement and routing package. IEEE Journal of Solid-State Circuits, Sc-20:510-522,1985.

90. K. Shahoobar, P. Mazumber. A genetic approach to standard cell placement. Proceedings of First European Design Automation Conference, March 1990.

91. К. Shahoobar, P. Mazumber. A genetic approach to standard cell placement using meta-genetic parameter optimization. IEEE Trans. Computer-Aided Design, pages 500-511, May1990.

92. S. Sutanthavibul, E. Shragowitz, J. Rosen. An analytical approach to floorplan design and optimization. IEEE Transactions on Computer-Aided Design, 10:761-769, June1991.

93. S. Sutanthavibul, E. Shargowitz, R. Lin. An adaptive timing driven placement for high performance vlsi's. IEEE Transactions on CAD of Integrated Circuits and Systems, 12: 1488-1498, October 1993.tii

94. J. Soukup. Fast maze router. Proceedings of 15 Design Automation Conference, pages 100-102, 1978. T. G. Szymanski. Dogleg channel routing is np-complete. IEEE Transactions on Computer-Aided Design, CAD-4: 3141, January 1985.

95. M. Upton, K. Samii, S. Sugiyama. Integrated placement for mixed macro cell and standard cell designs. Proceedings of 27th ACM/IEEE Design Automation Conference, pages 3235,1990.

96. T. Wang, D. Wong. An optimal algorithm for floorplan area optimization. Proceedings of 27th ACM/IEEE Design Automation Conference, pages 180-186,1990.-1/4—

97. J. Yih, P.Mazumder. A neural network design for circuit partitioning. IEEE Transactions on Computer-Aided Design, pages 1265-1271,1990.

98. Утверждаю» кто^ ООО «Ангстрем РТМ»1. А.С.Бутов 1999г.1. АКТо внедрении результатов диссертационной работы А.А.Данилина "Многокритериальный синтез топологии цифровых и аналоговых БИС на основе операторноймодели свичбокса"

99. Зав. кафедрой ПКИМС профессор, д.т.н.

100. Декан ЭКТ факультета профессор, д.т.н.

101. Уч.секретарь кафедры ПКИМС доцент, к.т.н. }1. Н.Целибеева