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

егб ой

- / Ц'сК ®

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

СЫРЦОВ ИЛЬЯ АНАТОЛЬЕВИЧ

ОПТИМИЗАЦИЯ ТОПОЛОГИИ СБИС В ИЕРАРХИЧЕСКИХ МОДЕЛЯХ

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

Автореферат

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

Москва, 1999г

г

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

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

доктор технических наук, профессор Щемелинин В.М.

Официальные оппоненты:

доктор технических наук, профессор Широ Г.Э.

кандидат технических наук Горбунов Ю.Д.

Ведущая организация:

ГУП НИИМА «Прогресс».

Защита состоится « »

_г. на заседании

диссертационного совета Д. 053. 02. 01 Московского Государственного института электронной техники (технического университета) (Москва, 103498).

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

'Автореферат разослан «_

Ученый секретарь диссертационного совета к.т.н , проф.

/

АУ/''

Н.В.Воробьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность тэмы

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

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

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

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

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

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

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

1. Анализ существующих методов и алгоритмов автоматического синтеза топологии для определения возможности их адаптации к условиям единой иерархической модели.

2. Разработка эффективных критериев качества и моделей решения задач синтеза.

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

4. Разработка программного обеспечения (ПО), его интеграция в иерархическую САПР и исследование эффективности.

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

В ходе выполнения работы использовались методы общей алгебры,

теория множеств, теория графов, алгоритмы__на__графах,__методы_

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

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

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

2. Использование введенного критерия формы позволяет объективно минимизировать потери площади на этапе построения дерева.

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

4. Разработана методика двумерного сжатия топологии, основанная на моделировании движения объектов под действием гравитационного поля.

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

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

Разработанные методы и алгоритмы оптимизации топологии реализованы в виде ПО и интегрированы в качестве подсистемы в САПР АИСТ (Москва, МИЭТ). В состав подсистемы входят:

- программа рекомпозиции дерева иерархии;

- программа векторной макротрассировки цепей фрагмента иерархии;

- программа векторной трассировки цепей фрагмента;

- программа силового сжатия фрагмента топологии;

- методическое обеспечение по формированию маршрута проектирования.

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

Результаты диссертационной работы применялись:

- при выполнении НИР на тему: «Исследование построения многофункциональных схем на основе параллельных вычислительных сред» (ИОС, г.Москва);

- при создании подсистемы трассировки цепей матричной БИС (ООО «Ангстрем-РТМ», г.Москва).

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

На защиту выносятся следующие положения:

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

2. Векторная модель процессов глобальной и детальной трассировки.

3. Модель сжатия, основанная на моделировании силового поля.

о

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

Структура и объем диссертационной работы

Диссертация содержит введение, пять основных глав с выводами, заключение, список литературы (92 наименования) и приложение. Полный объем работы -170 страниц, в том числе 9 таблиц и 58 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении кратко рассматривается современное положение в области проектирования топологии СБИС УБИС, формулируется цель работы и дается аннотация по главам диссертации.

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

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

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

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

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

Контакты

Субблоки

а)

г,

Рис.1. Блок иерархии (а) и фрагмент дереза иерархии (б)

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

Сведения о проектных операциях Таблица 2.1

Название операции Решаемые задами Объект синтеза Критерий

1. Декомпозиция Построение дерева иерархии Граф схемы, дерево иерархии Связность компонент

2. Макроразмещение Планировха блоков Прямоугольные блоки Минимизация оценки шюшади

3. Макротрассировка Планировка цепей План цепей, списки конт-ов Минимизация оценки длины цепей

4. Трассировка Разводка цепей Трассы цепей в единицах ДРП Минимизация длины цепей

5. Сжатие Уменьшение площади Геометр, описание топологии Минимизация площади

о

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

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

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

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

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

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

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

Метод итерационной декомпозиции дерева иерархии

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

Рис.2. Маршрут оптимизации дерева декомпозиции

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

О'/М) т;м.*гнчс!А областей

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

1) наличие ограничений на размеры кластеров существенно упрощает процесс декомпозиции;

2) ЫР-сложная задача размещения сводится к выбору одного из четырех вариантов;

3) отсутствие свичбоксов и ограничений на размер коммутационного пространства гарантирует 100% трассировку;

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

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

Критерий согласования геометрических форм определяет выбор взаимной ориентации блоков, для которой отклонение коэффициента формы фрагмента (Кф) от идеальной формы (Ки) является наименьшим:

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

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

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

ь 1 1 1 1 1 1 1 ■ 1 1 1 1 V/ ! и

1 . 1

1 Н

Рис.3. Модель бинарного идеального фрагмента

Здесь (V/,/?) и (УИ,Н) - размеры фрагментов И-го и ко уровней

А н

соответственно. Из условий: /! = №, 2* = Я, — = К„ — = Ки следует, что

V №

к, = -Л.

Процедура рекомпозиции дерева декомпозиции может иметь множество реализаций. При этом сложность реализации зависит от степени перестройки предыдущего дерева. Самой сложной для реализации является задача построения -дерева-без-учета-предыдущего.-Самой-простой - попарная — перестановка каких-либо двух вершин в дереве. Сложная реализация требует достаточно больших затрат. Но из-за отсутствия четкого критерия сходимости алгоритма при сильной перестройке дерева не очевидно, что итерационный процесс вообще будет сходиться (т.е. топология может ухудшаться). В главе 3 предложена следующая методика построения дерева. На начальном этапе среди всех элементов дерева определяется тот, для которого достигается значение АК#->тах. Затем для полученного фрагмента проводится попарное сравнение значений лКц. качества стыкуемости с другими фрагментами "ерядок перебора фраг\'енгсш описан ниже.

Сначала выбираются фрагменты, непосредственно связанные с исходным. В приведенном на рис.4а примере ДКф достигает максимального значения для фрагмента 8. Далее происходит поиск вариантов новой стыковки фрагмента 8 с самыми близкими по дереву и соответственно по связности фрагментами. В примере это область I, фрагменты 10, 3, 4. Затем рассматриваются фрагменты области II (фрагменты 7, 10), далее - области III и т.д. Такой выбор последовательности сравниваемых фрагментов позволяет учитывать связность фрагментов в схеме. Если геометрическая стыкуемость достигнута, то нет необходимости дальнейшего перебора.

Рис.4. Пример выбора областей (а) и перестановки элементов в дереве (б)

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

Алгоритм макротрассировки на основе вееторной модели

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

а)

б)

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

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

зависимость [¿~| = гДе расстояние между блоками Ь, и ъг При

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

Для описания алгоритма вводится элементарный объект "проектирования"Обобщенный компонент (/,), который может принимать либо значение блока либо коммутационного канала (с„), либо контакта на оболочке фрагмента (к,). Все исходные компоненты, коммутируемые цепью, объединяются в список £ = {/,}, /е[1,м], где М = Щ - размерность списка, -вектор воздействия компонента на /,, 1, - результирующий вектор цепи для компонента /,.

Для математической формализации операций над векторами и списками

вводятся следующие функиии:

1) /■(/,,/,).- геометрическое расстояние между компонентами / и 1Г

Точками отсчета являются: для блока - центр блока, для канала - центр канала, для фиксированного контакта - координаты центра контакта.

2) - значение нового компонента. Если - блок, то функция возвращает значение канала, смежного точке пересечения луча вектора со стороной блока (рис.ба: ст ). Если /, - канал, то возвращается

ближайший к /, канал, в сторону которого указывает вектор X (рис.56: с» =<?(<?.,£.))■

3) с(к,) - значение канала смежного с контактом к, (рис.5в: с1 = е(*,)).

С Ы

Cl

у

ьИ

А' С п|

d ь ■

Ck

V

■-Cm

\

\

Cm

с,

а) б) в)

Рис.5. Иллюстрация воздействия функций на различные компоненты В описании алгоритма I = {/,}, £•' = {?}, ¿ = обозначают список обрабатываемых, полученных и всех обработанных объектов.

Алгоритм макротрассировки цепи net,. Шаг 1: Сформировать начальный список L = (t,) дляцепиле* . Шаг2: ¿ = 1 , Z'=0, М = Щ ,1=0 . ШЗгЗ: Пока / s М выполнять ш;.ги 3.1 .. 3.6.

Шаг 3.1: Если /, = кт, то ¡' = с(/,), идти на шаг 3.5.

Шаг 3.2: Т,= где = ~тгтЛ ■ Шаг 3.3: /,'=

с

Ь>

Ck

Шаг 3 4: Если /, = то назначить 6„ контакт в точке пересечения границы и луча Ая .

Шаг 3.5: Включить // в ¿', включить /, в Шаг 3.6: < = I + 1.

Шаг 4: Удалить из V повторные элементы.

Шаг 5' Удалить из V элементы, принадлежащие Ь.

Шаг 6: 1 = и .

Шаг 7: Если > 1, идти на шаг 2.

Шаг 8: Если [¿| - 1, /, включить в £.

Шаг 9. По списку I построить план цепи и назначить контакты на стороны каналов.

Шаг 10: Конец.

На начальном этапе формируются списки X, ¿' = 0 , 1 = 0 . Далее из списка л выбирается первый элемент /,, для которого вычисляются вектор Т{ и /,' = р(/,,/,). Если /, - блок, в нем назначается внутренний контакт (при планировке цепей внутри данного блока, данный контакт станет внешним контактом на границе фрагмента). После этого /, добавляется в V, I. Аналогичные расчеты выполняются для остальных, элементов I. Поскольку элементы г не повторяются и не присутствуют в £, тоссостав V остается неизменным. На следующих итерациях выполняются аналогичные расчеты, после чего на основе Е стрсится план цепи.

Временная сложность алгоритма составляет 0{п т), где п - общее число элементов кристалла, т - общее числа цепей кристалла, при использовании данного алгоритма в большинстве случаев задача детальной трассировки существенно упрощается, что снижает время трассировки кристалла.

Алгоритм детальной трассировки на основе векторной модели

Для описания векторной модели и алгоритма вводится понятие терминала. В процессе трассировки происходит последовательное формирование множества сегментов трасс. Терминалом к-го порядка г'*'

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

порядка соответствуют точки в коммутационном поле, смежные контактам цепей.

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

терминалов данной цепи определяемая вектором /¡*> (вектором

движения). Вектор движения определяется как сумма векторов воздействия всех терминалов ¡'?т] (т* у) на = > ■ На основе вектора движения

формируется вектор элементарного перемещения д/^^/!*'). Тогда итерационное уравнение приобретает вид: = + •

от* у

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

<К4А>) накладываются следующие ограничения:

1) элементарное перемещение возможно лишь в направлениях, параллельных осям координат;

2) |л4к)|-1 - сдвиг терминала возможен только на одну позицию в ДРП,

что позволяет более точно отслеживать уже сформированную структуру топологии;

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

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

приоритеты выбора направлений элементарных перемещений в зависимости от направления вектора Наиболее приоритетным является направление,

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

Y' Ъ

-Ш--

Лк)/ Ч '

JI

IV

Рис.6. Выбор направления перемещения

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

существует, то терминал будет расположен в той же позиции, что и t\

№ V •

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

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

функциональная зависимость 1,411 1

гЩр/'Л

Алгоритм состоит из трех частей. На первом этапе происходит формирование множества терминалов нулевого -^порядка. Исходными данными для этого служит список контактов цепей. На втором этапе происходит формированию списка терминалов (к+1) порядка. При помощи двух вложенных циклов для всех терминалов к-го порядка вычисляются вектора двоения и при помощи оператора^? строятся вектора перемещений.

На третьем этапе происходит сравнивание полученных терминалов с уже существующими в данном фрагменте на предмет совпадения их координат и номера слоя. Если какие-либо два терминала одной цепи, порожденные различными контактами (условие: т) оказываются в одной точке, то новый терминал удаляется из списка и дальше не рассматривается. Это означает, что прокладка соответствующей ветви цепи завершена. Итерационный процесс продолжается до тех пор, пока во множестве порожденных терминалов не останется ни одного элемента (условие: |г(*+1)| = о).

Алгоритм векторной трассировки

Шаг 1: Построить Г(0) ={/!0)}.

Шаг 2: к=0.

Шаг 3: Для всех /е/Г.Л/щ/, ]е[1,ЫТ] выполнять 4*+,) = + <Р( НО ■

т* у

Шаг 4: Если 4*+,) =Цер .Ы^й. ¡.тер ,ЫтЫхп, 1ф,к+1]), то удалить /(*+1) из

Шаг 5: Если |т<*+1)|=о, то Конец.

Шаг 6: к=к+1.

Шаг 7: Идти на шаг 3.

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

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

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

Силовой алгоритм сжатия

За основу модели выбрана гравитационная сила притяжения

р - о-А. .1. Значение масс может быть использовано, например, как фактор

г2 И

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

то выражение можно упростить до Р = Сила притяжения дискрета к

< / й

определенному блоку В равна векторной сумме всех элементарных сил

между данным дискретом и каждой точкой блока: или

проекциях на оси координат: -——'-5-. Р=У.У.--г>

-------------. .. ' " [(х-д^чО'-л)^__* )2

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

В работе предложен достаточно простой и эффективный способ

снижения вычислительных затрат в процессе вычисления векторов сил. В

качестве радиус-вектора т выбран вектор между "данным дискретом и

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

снижается вследствие того, что каждый дискрет проводника перемещается

только на одну позицию в ортогональных направлениях. Длина вектора

г

значения не имеет, поэтому в качестве направления перемещения выбирается ближайший к текущему вектор из множества {7,-7,],-]}, где 7,] -единичные вектора осей координат. В случае, если цепь связана с несколькими субблоками внутри фрагмента, результирующая сила, действующая на дискрет проводника равна векторной сумме сил, действующих со стороны всех блоков, коммутируемых данной цепью. Очевидно, что для многоконцевых цепей погрешность будет увеличиваться. Однако, статистические данные показывают, что в реальных схемах доля двух- и трехконцевых цепей составляет примерно 75% от их общего количества, а при иерархическом проектировании внутри фрагмента она поднимается до 95%.

В основу алгоритма сжатия положены следующие принципы:

- в качестве объекта сжатия выступает иерархически описанный фрагмент топологии прямоугольной формы;

- каждый блок является источником гравитационного поля, проводники считаются эластичными (сжимаемы, разжимаемы, изгибаемы) и перемещаются под воздействием поля;

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

\ и направлен в сторону радиус-вектора г;

г

- радиус-вектор г определен как вектор между данным дискретом проводника и ближайшей к нему точкой блока;

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

Силовой алгоритм сжатия выполняется в три этапа. На первом этапе происходит итерационное перемещение проводников под действием сил притяжения. Здесь проводники меняют свою конфигурацию, "прижимаются" к блокам. Второй этап - непосредственно сжатие фрагмента - выполняется алгоритмом удаления путей деформации. На третьем этапе выполняется удаления петель и полупетель.

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

Фрагмент топологии описан в виде трехмерного массива: Fgn^x,y,lay], \<,1ау<,1аут„,гце Х^.у^ - размеры фрагмента, 1аут-количество коммутационных слоев. Каждый элемент массива содержит информацию о соответствующем поле фрагмента.

Силовой алгоритм сжатия фрагмента топологии. Шаг 1: x = \,y=\,lay=\, Move List = 0.

Шаг 2: Для всех xe[l,xnMJ,>6[l,.y««],flary выполнять шаги 2.1 .. 2.9.

Шаг 2.1: Если Fgn^x,y,lay) не проводник, то идти на шаг 2. Шаг 2.2: Net присвоить имя цепи Fgnix,y,lay}. Шаг 2.3: F = 0.

Шаг 2.4: Для всех Ь, аВ выполнять

Если цепь Net не связана с 6,, то идти на шаг 2.4,

иначе F = F+-V-rт. гдэ г, = г(х,у,ЬЛ.

1 Ы

Шаг 2.5: D = Round(F).

Шаг 2.6: Если Fgrr[x + /),,>' + Dy, lay] - занят другой цепью, то идти на шаг 2. Шаг 2.7: Если Fgr/i[x,y,lqy]-межслойный переход, то идти на шаг 2. Шаг 2.8: Добавить перемещение с параметрами x,y,lay,DITMoveList. Шаг 2.9: Идти на шаг 2. Шаг 3: MoveUst = Correct (MoveUst)

Шаг 4: Выполнить перемещения в соответствии с MoveUst. Шаг 5: Выполнить дотрассировку разорванных связей. Шаг 6: Удалить элементарные петли., 1

Шаг 7: Если площадь уменьшилась, то идти на шаг 1. Шаг 8. Выполнить сжатие фрагмента. Шаг Э Выполнить удаление петель и полупетель.

Переменная Net содержит имя цепи, которой принадлежит текущий дискрет Fgn{x,y,lay}. Список MoveList содержит данные обо всех возможных элементарных перемещениях на текущей итерации. Под переменной-параметром lay' подразумевается номер слоя, с которым коммутируется текущий слой lay межслойным переходом. Функция Round{P) возвращает ближайший к F единичный вектор ортогонального направления, соответственно, вектор D может принимать одно из четырех значений: 7,-7,]-]. Операция Correct(MoveList) необходима для устранения из списка некорректных перемещений. К ним относятся перемещения двух различных дискрет в общую новую позицию.

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

В четвертой главе рассмотрены вопросы организации базы данных (БД) САПР, изложены системные аспекты проблемы оптимизации, показано развитие предложенного метода в программном виде на примере САПР АИСТ. Выполнен сравнительный анализ различных моделей представления объекта на этапе детального синтеза.

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

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

При прокладке цепей трассировщик сам определяет точное положение контактов на стороне, а макротрассировка сводится к определению соответствия контакт - сторона на ядрах. Контакт на оболочке является "плавающим", но жестко привязанным к определенной стороне. Возможные варианты распределения цепей показаны на рис.7 и рис.8.Рис.7. Варианты распределения контактов двухконцевых цепей

ы

.Ж.*.

Ьз

б)

1кз

в) Г)

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

Для двухконцевой цепи типа -"ядро-ядро" (рис.та) - вектора _ цепей _ направлены друг к другу, соответственно, контакты размещаются на смежных сторонах ядер. Для двухконцевой цепи типа "ядро-оболочка" возможны две ситуации: контакт на оболочке лежит на стороне прилегающей к ядру (рис.4.76), тогда контакт назначается смежной стороне ядра; контакт на оболочке перекрыт другим ядром, здесь контакт м^ет быть назначен на любую сторону ядра кроме противоположной (рис.7в). Можно устранить потери введением транзитной цепи в другое ядро (рис.7г).

b,ki

bib2

: Si

b2

Рис.8. Назначение контактов трехконцевой цепи

Для трехконцевой цепи (рис.8) вектор направления цепи для ядра ь, формируется как сумма векторов воздействия ядра Ь, и стороны л4 (для плавающего контакта вектор направлен ортогонально стороне). Если размеры

N2 I_I 2 ^г h

= — • РА =-. Ча = -=г = — ■ Условие, при котором луч

w I I h fcjl w

jüj] пересекает нижнюю сторону блока fi,: -tgaz^, откуда ~ —

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

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

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

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

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

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

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

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

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

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

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

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

6. На основе силовой модели разработана метод! на двумерного сжатия топологии СБИС. В рамках иерархической модели топологии СБИС разработан алгоритм силового сжатия фрагмента.

7. Выполнена реализация предложенных методов и алгоритмов в виде программного обеспечения (ПО). Проведена интеграция разработанного

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

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

По материалам диссертации опубликованы следующие работы: . Сырцов И.А. Алгоритм оптимизации топологии СБИС методом плотной, компрессии// Тез.докл научно-техническая конференция студентов и аспирантов.- М., МИЭТ,-1996,- с.40. . Сырцов И.А., Щемелинин В.М. Оптимизация топологии СБИС с использованием иерархических моделей// Известия вузов. Электроника,-1997,- № 6,- с.63-70. . Сырцов И.А. Оптимизация топологии СБИС в иерархических системах путем перестройки дерева декомпозиции// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов,- М., МИЭТ,-1998,- с.69. •. Сырцов И.А. Иерархический синтез топологии заказных СБИС// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов.- М., МИЭТ,- 1999.- с.108. ¡. Сырцов И.А., Загидуллин М;Р. Векторная модель макротрассировки сигнальных цепей в иерархических системах проектирования топологии СБИС// Известия вузов. Электроника -1999,- ЫаЗ, с.73-80. >. Сырцов И.А. Алгоритм сжатия топологии СБИС на основе силовой модели// Известия вузов. Электроника.- 1999.- №6.

!одлисзно в печать Iакэз №231 Тираж 70

)тпъчатано а типографии МИЭТ

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

ВВЕДЕНИЕ

ГЛАВА 1. СОВРЕМЕННИКЕ МЕТОДЫ И АЛГОРИТМЫ

ТОПОЛОГИЧЕСКОГО СИНТЕЗА

1.1. ДЕКОМПОЗИЦИЯ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ

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

1.3. МАКРОТРАССИРОВКА ЦЕПЕЙ СБИС

1.4. ДЕТАЛЬНАЯ ТРАССИРОВКА ЦЕПЕЙ СБИС

1.5. СЖАТИЕ ТОПОЛОГИИ СБИС 31 ВЫВОДЫ

ГЛАВА 2. МЕТОДОЛОГИЯ ИЕРА^ЙЙЕС^ОШ СИНТЕЗА

ТОПОЛОГИИ СБИС'

2.1. ГЛОБАЛЬНЫЕ ПРОБЛЕМЫ ТОПОЛОГИЧЕСКОГО СИНТЕЗА

2.2. МЕТОДОЛОГИЯ ИСПОЛЬЗОВАНИЯ ОБЩЕЙ ИЕРАРХИЧЕСКОЙ МОДЕЛИ

2.3. ДЕКОМПОЗИЦИЯ И ОПЕРАЦИИ МАКРОСИНТЕЗА КРИСТАЛЛА

2.4. ОПЕРАЦИИ ДЕТАЛЬНОГО СИНТЕЗА КРИСТАЛЛА 57 ВЫВОДЫ

ГЛАВА 3. МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ

ИЕРАРХИЧЕСКОГО ПРОЕКТИРОВАНИЯ

3.1. МЕТОД ИТЕРАЦИОННОЙ РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ

3.2. АЛГОРИТМ МАКРОТРАССИРОВКИ НА ОСНОВЕ ВЕКТОРНОЙ МОДЕЛИ

3.3. ВЕКТОРНЫЙ МЕТОД ДЕТАЛЬНОЙ ТРАССИРОВКИ

3.4. СИЛОВОЙ АЛГОРИТМ СЖАТИЯ 91 ВЫВОДЫ

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ

АЛГОРИТМОВ ОПТИМИЗАЦИИ

4.1. ОРГАНИЗАЦИЯ БАЗЫ ДАННЫХ В ИЕРАРХИЧЕСКОЙ САПР

4.2. РЕАЛИЗАЦИЯ АЛГОРИТМА РЕКОМПОЗИЦИИ ДЕРЕВА ИЕРАРХИИ

4.3. АДАПТАЦИЯ АЛГОРИТМА ВЕКТОРНОЙ МАКРОТРАССИРОВКИ К САПР С БИНАРНЫМ ДЕРЕВОМ ИЕРАРХИИ

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

ВЫВОДЫ

ГЛАВА 5. ПРОЕКТИРОВАНИЕ ТОПОЛОГИИ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР

5.1. СТРУКТУРНАЯ СХЕМА СВЯЗЕЙ МЕЖДУ ПРОЦЕДУРАМИ

В СИСТЕМЕ ПРОЕКТИРОВАНИЯ АИСТ

5.2. НАСТРОЙКА ПАРАМЕТРОВ МАРШРУТА ПРОЕКТИРОВАНИЯ

5.3 ПРОЕКТИРОВАНИЕ ПЕЧАТНЫХ ПЛАТ С ИСПОЛЬЗОВАНИЕМ ИЕРАРХИЧЕСКОЙ САПР 150 ВЫВОДЫ 155 ЗАКЛЮЧЕНИЕ 156 СПИСОК ЛИТЕРАТУРЫ 159 ПРИЛОЖЕНИЯ

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

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

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

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

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

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

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

Работа состоит из четырех глав, введения и заключения.

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

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

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

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

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

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

ВЫВОДЫ

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

5. Предложен алгоритм макротрассировки цепей, основанный на использовании векторной модели. Временная сложность алгоритма составляет 0(Ые1т-Ыпе1), где Ые1т - общее число элементов кристалла, Ыпе( - общее числа цепей кристалла. Показано, что алгоритм векторной макротрассировки, адаптированный к системе с бинарным деревом иерархии, сводится к выбору оптимального решения среди ограниченного набора эвристик. Это приводит к снижению временной сложности задачи до 0(п), где /7-число цепей.

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

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

8. Выполнена реализация предложенных методов и алгоритмов (рекомпозиции, макротрассировки, детальной трассировки и сжатия) в виде программного обеспечения (ПО) на языке программирования Borland С++. Проведена интеграция разработанного ПО в систему проектирования АИСТ. Основным результатом применения данного ПО в маршруте проектирования САПР АИСТ, стало существенное улучшение на выходе основных параметров топологии (площадь, общая длина соединений, число межслойных переходов).

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

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

1. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств// Львов: Вища школа,-1981, с.167.

2. Селютин В.А. Машинное конструирование электронных устройств// М., Сов.радио, 1976.

3. W.Kernigan, S.Lin. An efficient heuristic procedure for partitioning graph// Bell System Technical Journal.- 49:391-307,1970.

4. C.M.Fiducca, R.M.Mattheyses. A linear-time heuristics for improving network partitons// Proceeding of the 19th Design Automation Conference.-pp.175-181,1982.

5. A.Chatterjee, R.Hartley. A new simultaneous circuit partitioning and chip placement approach based on simulated annealing// Proceeding of Design Automation Conference.- pp.36-39, 1990.

6. Y.G. Saab, V. Rao. Stochastic evolution: A fast effective heuristic for some generic layout problems// Proceedings of Design Automation Conference.-pp.36-31,1990.

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

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

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

10. M.A.Breuer. A class of min-cut placement algorithms// Proc. 14th Design Automation Conference.- pp. 284-290, June 1977.

11. M.A.Breuer, J. C. Lien. A methodology for the design of hierarchically testable and maintainable digital systems// Proc. 8th Digital Avionics Systems Conference (DASC).- pp. 40-47, San Jose, CA, 1988.

12. T.C.Lee. A bounded 2d contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules// Proceedings of the 30th Design Automation Conference.- pp.525-530, June 1993.

13. M. R. Garey and D. S. Johnson. The rectilinear steiner tree problem is np-complete// SIAM Journal Applied Mathematics.- 32: 826-834., 1977.

14. C. Chiang, M. Sarrafzadeh and С. K. Wong. A powerfull global routing: Based on steiner min-max trees// Proceedings of IEEE International Conference on Computer-Aided Design.- pp. 2-5, November 1989.

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

16. C. Sechen. Chip-planning, placement and global routing of macro/custom cell integrated circuits using simulated annealing// Proceedings of 25th ACM/IEEE Design Automation Conference.- pp.73-80,1988.

17. Прим P.K. Кратчайшие связывающие сети и некотороые обобщения: пер. с англ.//Кибернетический сборник.- М,- 1974.- вып.2., с95-107.

18. J. В. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem// Proceedings of the American Mathematical Society.-7(1): 48-50,1956.

19. E. W. Dijkstra. A note on two problems in connexion with graphs// Numerische Mathematic.-1:269-271,1959.

20. M. Marek-Sadowska, S. P. Lin. Timing driven placement// Proceeding of International Conference on Computer-Aided Design.- pp.94-97,1989.

21. T.Villa, T.Kam, R.K.Brayton, and A.Sangiovanni-Vincentelli. Synthesis of FSMs: Logic Optimization, Kluwer Academic Publishers// Boston/Dordrecht/London.- 1997.

22. C.Y. Lee. An algorithm for path connections and its application// IRE Trans. Electronic Computers.- EC-10, pp.346-365,1961.

23. M. Marek-Sadowska. Switchbox routing: a retrospective// INTEGRATION the VLSI Jornal.- Vol.13.- pp.39-65,1992.

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

25. M. Marek-Sadowska. Two-dimensional router for double layer layout// Proc. 22th Design Automation Conference.- pp.266-272,1985.

26. R. Joobbani. WEAVER: An application of knowledge based expert systemws to detailed routing of VLSI circuits// Research Report. CMUCAD.- pp.85-56, June 1985.

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

28. J.P. Cohoon, P.L. Heck. BEAVER: A computational geometry based tool for switch box routing// IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems.- CAD-7 (6), June 1988.- pp.684-697.

29. Широ Г.Э., Алгоритм трассировки, использующий деформацию ранее построенных проводников. В кн.: Вычислительная техника. Каунас, 1976, т.8. с. 136-139.

30. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных схем// М.- Радио и связь, 1985.

31. A.A.Malik. An efficient algorithm for constraint graph for compaction// Proc. if IEEE. International Conference on Computer-Aided Design.- pp.130-133,1987.

32. H.Shin, A.L.Sangivanni-Vincentelli and C.H.Sequin. Two-dimensional compaction by "zone-refining"// Proc. of 23rd Design Automation Conference.-pp. 115-122,1986.

33. M.Shlag, Y.Z.Liao, C.K.Wong. An algorithm for optimal two-dimensional compactionof VLSI layouts//Integration.- Vol.1.- pp.179-209,1983.

34. J.Williams. Sticks graphical compiler for high-level LSI design// Proc. of AFIPS.- pp.289-265, 1978.

35. M.A.Breuer, K.Anshul. A Methodology for custom VLSI layout // IEEE Trans. On circuits and systems.- 1983,- Vol.1.- CAS-30,№6.- pp.358-364.

36. Сырцов И.А., Щемелинин B.M. Оптимизация топологии СБИС с использованием иерархических моделей// Известия вузов. Электроника.- 1997.- № 6,- с.63-70.

37. Гинзбург Б.Д. Алгоритм размещения модулей на плате// Обмен опытом в радиопромышленности,-1972.-№4, с.31-33.

38. Марченко A.M., Щемелинин В.М. О классе алгоритмов плотной укладки фрагментов БИС// Автоматизация проектирования в радиоэлектронике и вычислительной технике.- М.- МДНТП.- 1987.-с.150-155.

39. 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).-pp.185-193, February 1985.

40. Сырцов И.А., Загидуллин M.P. Векторная модель макротрассировки сигнальных цепей в иерархических системах проектирования топологии СБИС// Известия вузов. Электроника.- 1999,- №3, с.73-80.

41. Марченко A.M., Щемелиннн В.М. Алгоритм декомпозиции функционально-завершенных фрагментов БИС// Электронная техника. Серия 3. Микроэлектроника.- вып.1(121).- 1987.- с.56-61.

42. К. J. Antreich, F. М. Johannes, F. Н. Kirsch. A new aproach for solving the placement problem using force models// Proceedings of the IEEE International Symposium on Circuits and Systems.- pp.481-486, 1982.

43. N. R. Quinn, M. A. Breuer. A force directed component placement procedure for printed circuit boards// IEEE Trans. Circuits and Systems.- pp.377-388, June 1979.

44. Сырцов И.А. Алгоритм сжатия топологии СБИС на основе силовой модели// Известия вузов. Электроника.- 1999.- №6.

45. Казеннов Г.Г., Марченко А.М., Щемелинин В.М. АИСТ подсистема автоматического иерархического синтеза топологии заказных БИС // Электронная промышленность. - 1988. - №10. - С.49 - 50.

46. Казеннов Г.Г., Марченко A.M., Щемелинин В.М. Автоматический синтез топологии заказных БИС// Электронная техника. Серия 3. Микроэлектроника.- вып.2(131).- 1989.- с.39-41.

47. Сырцов И.А. Алгоритм оптимизации топологии СБИС методом плотной, компрессии// Тез.докл научно-техническая конференция студентов и аспирантов,- М., МИЭТ.- 1996.- с.40.

48. Сырцов И.А. Оптимизация топологии СБИС в иерархических системах путем перестройки дерева декомпозиции// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов.- М., МИЭТ,- 1998,- с.69.

49. Сырцов И.А. Иерархический синтез топологии заказных СБИС// Тез.докл. Всероссийская межвузовская научно-техническая конференция студентов и аспирантов.- М., МИЭТ.- 1999.- с. 108.

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

51. A.Mukherjee, R.Sudhakar, M.Marek-Sadowska, S.I.Long/ A Novel NonfVt1.erative Synthesis and Layout Technique// 36 Design Automation Conference// New Orleans, LA.- June 21-25,1999.- p.466.

52. J.Bianks. Partitioning by probability condensation// Proceeding of Design Automation Conference// pp.758-761, 1989.

53. T. Cormen, C.E. Leiserson and R. Rivest. Introduction to Algorithms. McGraw Hill, 1990.

54. G. Chartrand and Lesniak. Graphs and Digraphs. Wadsworth and Brooks/Cole Inc., Monterey, 1986.

55. J.Cullum, W.Donath, P.Wolfe. The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices// Mathematical Programming Study, 3:35-55,1975.

56. J. P. Cohoon, W. Paris. Genetic placement// Proceedings of the IEEE International Conference on Computer-Aided Design.- pp 422-425, 1986.

57. H. Chan, P. Mazumber, K. Shahookar. Macro-cell and module placement by genetic adaptive search with bitmap represented chromosome// Integration: the VLSI Journal.- 12(1): 49-77, November 1991.

58. J. Cong. Pin assignment with global routing// Proceedings of International Conference on Computer-Aided Design.- pp.302-305,1989.

59. W. W. Dai, B. Eschermann, E. Kuh, M. Pedram. Hierarchical placement and floorplanning in bear// IEEE Transactions on Computer-Aided Design. -8:1335-1349, Dec. 1989.

60. W. E. Donath, R. J. Norman, B. 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.

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

62. Edward M. Reingold, Jurg Nivevergelt, Narsingh Deo, Combinatorial algorithms. Theory and practice// Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1977.

63. Y. Ogawa et. al. Efficient placement algorithms optimizing delay for highspeed eel masterslice Isi's// Proceedings of 23rd ACM/IEEE Design Automation Conference.- pages 404-410,1986.

64. 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.

65. M.K.Goldberg, M.Burstein. Heuristic improvement technique for bisection of vlsi networks// Proceeding of IEEE International Conference on Computer Design.- pages 652-657,1983.

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

67. R.B.Hitchcock. Partitioning of logic graphs: A theoretical analysis of pin reduction// Proceeding of Design Automation Conference.- p.54-63, 1970.

68. M. Hanan, J. M. Kurtzberg. A review of placement and quadratic assignment problems// SIAMRev.- 14(2): 324-342, April 1972.

69. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time// SIAM Journal of Computing.- 4, no.3:221-225, September 1975.

70. R.Kling, P.Bannerjee. Esp: Placement by simulated evolution// IEEE Transactions on Computer-Aided Design.- 8(3):245-256,1989.

71. W.K. Luk. A greedy switch box router// VLSI Document VI58,- Carnegie Mellon University. May 1984.

72. Y.L. Lin, Y.C. Hsu, F.S. Tsay. A detailed router based on simulated evolution//Proc. Int. Conf. Computer-Aided Design.- 1988. 38-41.

73. F.F. Moore. The shortest path through a maze// Annals of the Harvard Computation Laboratory.- Vol.30. Pt.ll.- pp.185-192.

74. 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.

75. 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.

76. 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.

77. T. Ohtsuki. Partitioning, Assignment and Placement//North-Holland, 1986.

78. С. H. Paradimitriou and K. Steigliz. Combinatorial Optimization -Algorithms and Complexity// Prentice-Hall, Inc., 1982.

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

80. N. R. Quinn, M. A. Breuer. A force directed component placement procedure for printed circuit boards// IEEE Trans. Circuits and Systems.- pp.377-388, June 1979.

81. R.B. Rukc. A gridless switch box router. Proc. Int. Conf. On Custom Integrated Circuits. 1987,- pp.629-632.

82. Щемелинин B.M. Метод трассировки сложных схем// Известия вузов. ЭЛЕКТРОНИКА. №1,1997, с.66-72.

83. Naveed Shervani. Algorithms for VLSI Physical Design Automation. Second Edition, Kluwer Academic Publishers, Boston/ Dordrecht /London, 1995.

84. M. Sarrafzadeh and С. K. Wong. Hierarchical steiner tree construction in uniform orientations// Research report, Dept. Of Electrical Engineering and Computer Science, Northwestern University, 1990.167

85. A. Shanbhad, S. Danda, N. Sherwani. Floorplanning for mixed macro block and standard cell designs// Fourth Great Lakes Symposium on VLSI, pages 80-85,1994.

86. 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.

87. T. G. Szymanski. Dogleg channel routing is np-complete// IEEE Transactions on Computer-Aided Design, CAD-4: 31-41, January 1985.

88. V. Shchemelinin, A. Danilin, The Switchbox Routing Specification Expansion Method// First International Workshop.- Multi-Architecture Low Power Design, Sept 1999, Moscow, p.89.

89. Y.Wei, C.Cheng. Towards efficient hierarchical designs by ratio cut partitioning// Proceeding of IEEE International Conference on Computer Design.- pages 298-301, November 1989.

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

91. Зав. кафедрой ПКИМС профессор, д.т.н.1. М.А.Королев Г.Г.Казеннов

92. Уч.секретарь кафедры ПКИМС >".■ .доцент, к.т.н. рян&^о "В.Н.Целибеева