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

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

РГ5 О Л

I 2 Г-Н ПС]

Щукин Александр Валентинович

Разработка и исследование подсистемы трассировки заказных СБИС

специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата

технических наук

Санкт-Петербург - 2000

Работа выполнена в Санкт-Петербургском Государственном Техническом Университете

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

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

кандидат технических наук, доцент, Первицкий А.Ю.

Ведущая организация - ИНСТИТУТ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ И БАЗ ДАННЫХ МИНИСТЕРСТВА НАЙКИ И ТЕХНОЛОГИИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Защита диссертации состоится "25" мая_2000г. в 16 часов на

заседании диссертационного совета К063.38.07 Санкт-Петербургского Государственного Технического Университета по адресу: 195251, Санкт-Петербург, ул. Политехническая, д. 25, 9 учеб. корпус, ауд. 441

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

Автореферат разослан " "_2000г.

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

Кандидат технических наук Попов С.С

Г

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

2. Провести анализ существующих моделей данных различных алгоритмов трассировки.

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

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

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

6. Провести макетирование основных блоков алгоритма трассировки и сделать оценку эксплутационных характеристик.

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

выносятся:

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

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

3. Разработанный, так называемый Направленный Волновой Алгоритм (НВА) для канальной модели данных, который обеспечивает:

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

— проведение оптимизации по длине пути и числу поворотов (межслойных переходов).

4. Включенный в НВА блок итеративной трассировки, который эвристическим методом изменяет порядок трассировки цепей.

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

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

Научная новизна работы определяется:

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

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

эвристические правила ориентации поиска приемников в канале в зависимости от их расположения относительно текущего анализируемого участка;

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

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

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

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

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

Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения и четырех приложений. Общий объем работы 121 страница машинописного текста, 28 иллюстраций, 7 таблиц. Библиография включает 63 наименования.

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

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

В первой главе «Анализ разновидностей и методов трассировки БИС» описываются стандартные, полузаказные и заказные микросхемы. К стандартным БИС относятся:

• микросхемы широкого применения (микропроцессоры, оперативные запоминающие устройства;

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

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

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

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

1. Метод «стандартных ячеек». Существует набор стандартных ячеек, которые можно расположить на кристалле в виде рядов. У проектировщика имеется свобода в расположении ячеек и соединении их в схему с целью минимизации площади БИС и длины всех проводников.

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

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

1. Группа графо-теоретических подходов.

2. Группа топографических методов.

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

• определение порядка сортировки соединений,

• трассировка,

• распределение соединений по слоям.

Анализируются следующие алгоритмы:

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

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

3. Лучевой алгоритм. Основная идея этого метода состоит в циклическом повторении шагов:

• продвижение в оптимальном направлении;

• выявление препятствий и их обход.

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

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

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

Во второй главе «Подсистема проектирования БИС блочной структуры» рассматривается программный комплекс, в котором применяется разрабатываемый алгоритм разводки цепей. Вводятся понятия: функциональный блок (ФБ), канал и шлюз. Работа программы топологического проектирования начинается с размещения ФБ на рабочем поле кристалла, далее выполняется разбиение свободного для трассировки пространства на каналы, трассировка и распределение соединений по слоям (расслоение).

Для лучшего понимания на рисунке 1 приведены все элементы,

Граница КП

Функциональный блок

Рис. 1 БИС блочной структуры

которым даны термины.

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

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

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

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

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

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

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

• Канал однозначно описывается как совокупность свободных участков магистралей (СУМ) и контактов. Поиска пути организуется посредством анализа СУМ.

• Соприкасающиеся СУМ одного направления, одинаковой длины и единичной толщины объединяются в единый блок, равный по ширине количеству объединяемых свободных отрезков. Таким образом алгоритм оперирует блоками, которые в общем случае могут иметь толщину больше или равную 1. В дальнейшем они

Рис. 2 Свободные участки до объединения

будут именоваться СУМ.

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

V

/ N

V У

Рис. 3 Свободные участки после объединения

На Рис. 2 и Рис. 3 показаны СУМ до и после объединения.

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

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

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

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

• Реализован поиск на графе в глубину, а не в ширину.

• На данном этапе применяется ряд эвристических правил, способствующих более "интеллектуальному" и направленному

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

• В случае захода в тупик реализован алгоритм "отката назад" посредством стека, где находится информация о ранее анализировавшихся участках. При этом восстанавливается информация о текущем состоянии и направлении обхода отрезка.

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

В диссертации дано подробное описание работы алгоритма трассировки.

В четвертой главе «Практическая реализация регулярного алгоритма трассировки» дается описание разработанного комплекса программ на языке С++ в системе Borland С++ с использованием принципов объектно-ориентированного программирования.

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

Далее в данной главе описываются основные шаги процесса разводки

цепи:

1. Инициализация объектов регулярного алгоритма трассировки. Определение источников и приемников.

2. Организация процедуры Ход Вперед.

3. В случае достижения приемника организация процедуры Ход Назад.

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

Описываемые усовершенствования, повышающие эффективность работы подсистемы:

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

• Расщепление "толстых" СУМ, выходящих на контакты.

• Модификация описания канала при разводке определенного участка цепи.

• Экономное кодирование путевой информации.

• Не прямолинейных обход пересекающих СУМ.

• Практическая реализация эвристик для навигации в канале при поиске приемников.

• Установка соприкасающихся отрезков-приемников.

• Введение рамки, ограничивающей область канала при обратном ходе.

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

Глава шестая «Экспериментальные результаты тестирования магистрального регулярного алгоритма» включает в себя показатели эффективности применения разработанных эвристик. Проведенные эксперименты показали:

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

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

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

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

5. Время работы разработанного алгоритма трассировки слабо зависит от размеров канала и расстояния между контактами.

6. Применение «рамок» при обратном ходе уменьшает время обратного хода на порядок.

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

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

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

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

примеры топологии каналов с протрассированными цепями.

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Щукин A.B. Двухэтапная трассировка СБИС: модель данных топологии // Фундаментальные исследования в технических университетах: Материалы научно-технической конференции, г. Санкт- Петербург, 16-17 июня 1997 года.

2. Щукин A.B. Комбинирование алгоритмов трассировки при трассировке цепей заказных СБИС. // Вторая республиканская электронная научная конференция "Современные проблемы информатизации", Москва, Санкт-Петербург, 10-15 февраля 1997 года.

3. Кулаков A.B., Речинский A.B., Щукин A.B., Яшин А.М. Математические основы систем искусственного интеллекта. Учебное пособие. Часть I (Экспертные системы). СПбГТУ, 1998.

ВВЕДЕНИЕ.

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

Глава 1.1 Классы БИС п особенности их проектирования.

Глава 1.2 Анализ основных алгоритмов трассировки сосдннсннй.

Глава 1.3 Пути повышении эффективности трассировки мсжсоедннснин БИС.

ГЛАВА 2 ПОДСИСТЕМА ТОПОЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ БИС БЛОЧНОЙ СТРУКТУРЫ

Глава 2.1 Используемая терминология.*.1.

Глава 2.2 Описание алгоритма трассировки подсистемы топологического проектирования

ГЛАВА 3 РЕГУЛЯРНЫЙ АЛГОРИТМ ЛОКАЛЬНОЙ ТРАССИРОВКИ.

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

Глава 3.2 Принципы разработки регулярного алгоритма трассировки.

Глава 3.3 Описание регулярного алгоритма трассировки.

ГЛАВА 4 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕГУЛЯРНОГО АЛГОРИТМА ТРАССИРОВКИ.

Глава 4.1 Организация интерфейса программы доразводки цепей с подсистемой топологического проектирования заказных БИС.

Глава 4.2 Основные объекты, формируемые в программе разводки цепей.

Глава 4.3 Инициализация объектов регулярного алгоритма трассировки.

Глава 4.4 Особенности реализации процедуры Ход Вперед.

Глава 4.5 Особенности реализации процедуры Ход Назад.

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

Глава 5.1 Использование информации о загруженности канала.

Глава 5.2 Перемещение контактов па шлюзах.

Глава 5.3 Визуализация процесса поиски.

Глава 5.4 Прпмспснпс распределенных вычпслепим для параллельной трассировки нескольких цепей.

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

Глава 6.1 Сравнительный анализ эффективности использования волнового алгоритма н магистрального метода.

Глава 6.2 Эксперименты, показывающие эффективность внесенных усовершенствований в магистральный метод.

Глава 6.3 Пример топологического проектирования заказной БИС блочной структуры.

Современный научно-технический прогресс характеризуется внедрением во все области человеческой деятельности радиоэлектронной аппаратуры. Известно, что 40 % мирового производства занято выпуском такой техники. Основным узлом радиоэлектронной аппаратуры являются большие интегральные схемы (БИС), постоянные запоминающие устройства (ПЗУ), программируемые логические матрицы (ПЛМ), базовые матричные кристаллы (БМК) и т.д. Процессы проектирования и изготовления интегральных схем являются наиболее автоматизированными.

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

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

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

2. Провести анализ существующих моделей данных различных алгоритмов трассировки.

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

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

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

6. Провести макетирование основных блоков алгоритма трассировки и сделать оценку эксплутационных характеристик.

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

• ускорить и повысить качество разработки БИС;

• улучшить эксплуатацию программы проектирования БИС.

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

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

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

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

4. Включенный в НВА блок итеративной трассировки, который эвристическим методом изменяет порядок трассировки цепей.

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

Диссертация является законченной научно-исследовательской работой.

Краткое содержание работы сводится к следующему.

В первой главе «Анализ разновидностей и методов трассировки БИС» описываются стандартные, полузаказные и заказные микросхемы. К стандартным БИС относятся:

• микросхемы широкого применения (микропроцессоры, оперативные запоминающие устройства;

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

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

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

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

1. Метод «стандартных ячеек». Существует набор стандартных ячеек, которые можно расположить на кристалле в виде рядов. У проектировщика имеется свобода в расположении ячеек и соединении их в схему с целью минимизации площади БИС и длины всех проводников.

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

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

1. Группа графо-теоретических подходов.

2. Группа топографических методов.

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

• формирование списка соединений,

• определение порядка сортировки соединений,

• трассировка,

• распределение соединений по слоям.

Анализируются следующие алгоритмы

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

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

3. Лучевой алгоритм. Основная идея этого метода состоит в циклическом повторении шагов:

• продвижение в оптимальном направлении;

• выявление препятствий и их обход.

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

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

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

Во второй главе «Подсистема проектирования БИС блочной структуры» рассматривается программный комплекс, в котором применяется разрабатываемый алгоритм разводки цепей. Вводятся понятия: функциональный блок (ФБ), канал и шлюз. Работа программы топологического проектирования начинается с размещения ФБ на рабочем поле кристалла, далее выполняется разбиение свободного для трассировки пространства на каналы, трассировка и распределение соединений по слоям (расслоение).

Для лучшего понимания на Рисунок 8 приведены все элементы, которым даны термины.

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

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

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

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

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

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

• Канал однозначно описывается как совокупность свободных участков магистралей (СУМ) и контактов. Поиска пути организуется посредством анализа СУМ.

• Соприкасающиеся СУМ одного направления, одинаковой длины и единичной толщины объединяются в единый блок, равный по ширине количеству объединяемых свободных отрезков. Таким образом алгоритм оперирует блоками, которые в общем случае могут иметь толщину больше или равную 1. В дальнейшем они будут именоваться СУМ.

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

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

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

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

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

• Реализован поиск на графе в глубину, а не в ширину.

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

• В случае захода в тупик реализован алгоритм "отката назад" посредством стека, где находится информация о ранее анализировавшихся участках. При этом восстанавливается информация о текущем состоянии и направлении обхода отрезка.

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

В диссертации дано подробное описание работы алгоритма трассировки.

В четвертой главе «Практическая реализация регулярного алгоритма трассировки БИС блочной структуры» дается описание разработанного комплекса программ на языке С++ в системе Borland С++ с использованием принципов объектно-ориентированного программирования.

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

Глава шестая «Экспериментальные результаты тестирования магистрального регулярного алгоритма» включает в себя показатели эффективности применения разработанных эвристик. Проведенные эксперименты показали:

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

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

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

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

5. Время работы разработанного алгоритма трассировки слабо зависит от размеров канала и расстояния между контактами.

6. Применение «рамок» при обратном ходе уменьшает время обратного хода на порядок.

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

ВЫВОДЫ:

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

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

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

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

5. Время работы разработанного алгоритма трассировки слабо зависит от размеров канала и расстояния между контактами.

6. Применение «рамок» при обратном ходе уменьшает время обратного хода на порядок.

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

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

Глава 7 Заключение

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

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

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

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

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

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

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

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

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

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

Глава 8 Экономическое обоснование работы

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

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

Общее количество цепей БИС, неразведенных канальным методом, зависит от различных параметров проектируемой БИС (количество цепей, размеры БИС и т.д.) и от качества выполнения этапов, предшествующих локальной трассировке, т.е. этапов размещения функциональных блоков и глобальной трассировки (результаты автоматического выполнения данных задач могут дорабатываться оператором вручную). Среднее число неразведенных канальным методом цепей для БИС, упоминаемых в экспериментальных результатах, составляет 13-18 штук. Среднее время разводки соединения составляет: вручную - около 4 минут, магистральным методом - около I минуты. Таким образом, экономия времени для одного этапа выполнения локальной трассировки составляет примерно 40-50 минут.

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

К = ** * •

Уменьшение времени проектирования БИС позволяет уменьшить себестоимость проектирования за счет снижения следующих расходов:

• заработная плата производственных рабочих на единицу продукции (заказная БИС);

• затраты на электроэнергию на единицу продукции;

• расходы на содержание и эксплуатацию оборудования (ЭВМ, графопостроитель, принтер) на единицу продукции.

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

Глава 9 Техника безопасности

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

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

II. Защита от вредных излучений. Необходимо обеспечить каждый монитор защитным экраном и соблюдать допустимую дистанцию оператора ЭВМ от монитора.

III. Общие требования к работе с компьютером:

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

B. соблюдение режима работы оператора за компьютером

C. создание максимально комфортного и эргономичного рабочего места оператора.

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

2. Автоматизация проектирования матричных КМОП БИС / A.B. Назаров, A.B. Фомин, H.JI. Дембицкий и др.; Под ред. A.B. Фомина.- М.: Радио и связь, 1991.

3. Автоматизированное проектирование цифровых устройств/ Под ред. С.С. Бадулина. М.: Радио и связь, 1981. 240 с.

4. Аруме А.Э. Автоматизация принятия решений в САПР // Системы автоматизированного проектирования в машиностроении и приборостроении. Рига, 1987.

5. Баталов Б.В., Норенков H.H. Системы автоматизированного проектирования сверхСБИС // Микроэлектроника. 1981. Т.9. Вып. 5. С. 401-412.

6. Бершадский A.M. и др. Некоторые пути повышения эффективности автоматизированных систем конструкторского проектирования // Вопросы радиоэлектроники. Сер. ЭВТ. 1978. Вып. 13. С. 1 11-115.

7. Брейер М. Последние достижения в области автоматизации проектирования и анализа цифровых систем // Автоматизация в проектировании. М.: Мир, 1972. С. 19-48.

8. Быстродействующие матричные БИС и СБИС. Теория и проектирование / Б.Н. Файзулаев, И.И. Шагурин, А.Н. Кармазинский и др.; М.: Радио и связь, 1989.

9. Валиев К.А., Казеннов Б.В., Шавлеев Н.И. и др. Вопросы выбора общей структуры высокопроизводительнойавтоматизированной системы проектирования ИПС // Управляющие системы и машины. 1974. №5.

10. Глориозов Е.Л., Сеорин В.Г., Сыпчук П.П. Введение в автоматизацию схемотехнического проектирования. М.: Советское радио, 1976. 224 с.

11. Гурский Л.И., Степанец В.Я. Проектирование микросхем. -Мн.: Навука i тэхшка, 1991.

12. Гуськов Г.Я., Магрупов Т.М. Алгоритмическое проектирование микроэлектронных вычислительных структур. Ташкент: Фан, 1982. 1 12 с.

13. Деркач В.П., Кияшко Г.Ф., Хачатурян В.Б. и др. К выбору критериев оценки эффективности систем автоматизированного проектирования БИС // Управляющие системы и машины. 1975. №6. С. 103-106.

14. Ильин В.Н. Интеллектуализация САПР // Изв. Вузов. Радиоэлектроника. 1987. Вып. 30. №6. С. 5-13.

15. Карапетян А.М. Автоматизация оптимального конструирования ЭВМ. М.: Советское радио, 1973. 148 с.

16. Кулаков A.B., Речинский A.B., Щукин A.B., Яшин А.М. Математические основы систем искусственного интеллекта. Учебное пособие. Часть I (Экспертные системы). СПбГТУ, 1998.

17. Кузьмин Б.А. Универсальные САПР. Проблемы и решения // Приборы и системы управления. 1979. №1.

18. Магрупов Т.М., Арипджанов М.К. Система автоматизации синтеза микроэлектронных вычислительных структур // Микроминиатюризация устройств вычислительной и аналоговой техники. Сер. 10. Микроэлектронные устройства. Вып. 1(135). М., 1980.

19. Минский М. Фреймы для представления знаний / Пер. с англ. М.: Энергия, 1979. 152 с.

20. Мурога С. Системное проектирование сверхбольших интегральных схем: Пер. с англ. М.: Мир, 1985.

21. Мюллер И. Эвристические методы в инженерных разработках. М.: Радио и связь. 1984. 114 с.

22. Нильсон Н. Искусственный интеллект. Методы поиска решений: Пер. с англ. М.: Мир, 1973.

23. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь. 1985. 376 с.

24. Норенков И.Л., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1983. 272 с.

25. Осуга С. Обработка знаний / Пер. с япон. М.: Мир, 1989. 293с.

26. Петухов Г.А., Смолич Г.Г. Структура САПР на основе базы знаний // Изв. Вузов. Приборостроение. 1986. Вып. 29. №12. С.35-39.

27. Представление и использование знаний / Пер. с англ. под ред. X. Уэно, М. Исидзука. М.: Мир, 1989. 220 с.

28. Проектирование микроэлектронных цифровых устройств/ Под ред. С.А. Майорова. М.: Советское радио, 1977. 272 с.

29. Проектирование СБИС / М. Ватанабэ, К. Асада, К. Кани и др.; Пер. с япон. М. Мир, 1988.

30. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ. М.: Мир, 1980.

31. Селютин В.А. Машинное конструирование электронных устройств. М.: Сов. Радио, 1977.

32. Селютин В.А. Автоматизация проектирования топологии БИС. М.: Радио и связь, 1983.

33. Скоробогатов В.А. О некоторых аспектах автоматизированного проектирования больших интегральных схем // Управляющие системы и машины. 1974. №5.

34. Старое Ф.Г., Фридман Г.Р., Шендерович Ю.И. Вопросы комплексной автоматизации разработки БИС // Электронная промышленность. 1982. №6. С. 79-86.

35. Страуструп Б. Язык программирования С++: Пер. с англ. -М.:Радио и связь, 1991.

36. Стрельников Ю.Н., Алмаметов В.Б., Свиньин A.C. Информационный интерфейс в экспертной конструкторской САПР // Проектирование вычислительных средств: Тез. докл. всесоюзн. науч.-технич. конф., г. Каунас, 6-8- июня 1989 г. Каунас, 1989. - с. 149-150.

37. Табарный В.Г. Автоматизированная система проектирования интегральных схем // Изв. Вузов СССР, Радиотехника. 1973. Т. 14, №6.

38. Теория и методы автоматизации проектирования вычислительных систем / Под ред. Байера. М.: Мир, 1977, 285 с.

39. Фойер М. Автоматизация проектирования СБИС // Труды института инженеров по электронике и радиоэлектронике. Т. 71. №1. С. 8-13.

40. Щукин A.B. Двухэтапная трассировка СБИС: модель данных топологии // Фундаментальные исследования в технических университетах: Материалы научно-технической конференции, г. Санкт- Петербург, 16-17 июня 1997 года.

41. Щукин A.B. Комбинирование алгоритмов трассировки при трассировке цепей заказных СБИС. // Вторая республиканская электронная научная конференция "Современные проблемы информатизации", Москва, Санкт-Петербург, 10-15 февраля 1997 года.

42. Эллис М., Страуструп Б. Справочное руководство по языку программирования С++ с комментариями; Пер. с англ. М.: Мир, 1992.

43. D. Chen and C. Sechen. Mickey: A Macro Cell Global Router, Proc. European Conf. On Design Automation, 1991, pp. 248-252.

44. D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao. On the bounded-skew clock and steiner routing problems. In Proc. of 32nd Design Automation Conf., pages 508-5 13, 1995.

45. D.N. Deutsch. A Dogleg Channel Router, Proc. 13th Design Automation Conference, June 1976, pp. 425-433.

46. J. Burns, A. Casotto, M. Igusa, F. Marron, F. Marron, F. Romeo, A. Sangiovanni-Vincentelli, C. Sechen, H. Shin, G. Srinath, and H. Yaghutiel. Mosaico: An Integrated Macro-Cell Layout System, Proc. of VLSI '87, Vancouver, Canada, August, 1987.

47. J. Cong, A.B. Kahng, C.K. Koh, and C.-W. A. Tsao. Bounded-skew clock and steiner routing under elmore delay. In IEEE Intl. Conf. on CAD, pages 220-223, Nov. 1993.

48. J. Cong, A. Kahng, G. Robins, M. Sarrafszadeh, and C.K. Wong. Probably Good Performance-Driven Global Routing, IEEE Trans, on Computer-Aided Design, Vol. 11, No 6, 1992, pp. 739-75 1.

49. J. Cong and B. Preas. A New Algorithm for Standard Cell Global Routing, Proc. IEEE Intl. Conf. on Computer-Aided Design, !988, pp. 176-179.

50. J.G. Xi, Wayne W.-M. Dai, Useful-Skew Clock Routing With Gate Sizing for Low Power Design. Proceeding of the 33rd Design Automation Conference, 1996.

51. J.K. Chua and Y.C. Lim. Fast Vicinity-Upgrade Algorithm for Rectilinear Steiner Trees, Electronic Letters, Vol. 27. No. 13, June 1991, pp. 1 139-1 140.

52. J. Lillis, Chung-Kuan Cheng, Ting-Ting Y. Lin, Ching-Yen Ho. New Performance Techniques With Explicit Area / Delay Tradeoff and Simultaneous Wire Sizing. Proceeding of the 33rd Design Automation Conference, 1996.

53. J.M. Cohn, D.J. Garrod, R. Rutenbar, and L.R. Carley. Technique for Simultaneous Placement and Routing of Custom Analog Cells in

54. KOAN/ANAGRAM II, Proc. of IEEE Intl. Conf. on Computer-Aided Design, 1991, pp. 394-397.

55. K.D. Boese, A.B. Kahng, G. Robins, High-Performance Routing Trees With Identified Critical Sinks. Proc. ACM/IEEE Design Automation Conf.

56. M. Burstein, and R. Pelavin. Hierarchical Channel Router, Proc. 20th Design Automation Conference, June 1983, pp. 591-597.

57. M. Edahiro. A clustering-based optimization algorithm in zero-skew routings. In Proc. of 30th Design Automation Conf., pages 612616, 1993.

58. R. Brouwer and P. Banerjee, A Parallel Hierarchical Global Router, IEEE Trans, on Computer-Aided Design, Vol. CAD-2, No. 4, pp. 223-234.

59. R. Condamoor and I.G. Tollis. A New Heuristic for Rectilinear Steiner Trees, Proc. IEEE Intl. Symposium on Circuits and Systems, 1990, pp. 1676-1677.

60. R. Dietz, D.A. Mlynski. New Model for Global Routing of Gate-Arrays, Proc. IEEE International Symposium on Circuits and Systems, May 1987, pp. 35-38.

61. R.-S. Tsay. An exact zero-skew clock routing algorithm. IEEE Trans, on CAD, 12(3):242-249, 1993.

62. S. Chopra and E. Rosenberg. Efficient Method for Custom Integrated Circuit Global Routing, Proc. IEEE Custom Integrated Circuits Conference, May 1988, paper 11.3.

63. T.H. Chao, Y.C. Hsu, J.M. Ho, K.D. Boese and A.B. Kahng. Zero skew clock net routing. IEEE Trans, on Circuits and Systems, 39(1 1):799-814, Nov. 1992.