Содержание к диссертации
Введение
Глава 1 Анализ разновидностей и методов трассировки БИС 13
Глава 1.1 Классы БИС и особенности их проектирования 13
Глава 1.2 Анализ основных алгоритмов трассировки соединений 22
Глава 1.3 Пути повышения эффективности трассировки межсоединений БИС 37
Глава 2 Подсистема топологического проектирования бис блочной структуры 40
Глава 2.1 Используемая терминология 40
Глава 2.2 Описание алгоритма трассировки подсистемы топологического проектирования 43
Глава 3 Регулярный алгоритм локальной трассировки 47
Глава 3.1 Постановка задачи 47
Глава 3.2 Принципы разработки регулярного алгоритма трассировки 48
Глава 3.3 Описание регулярного алгоритма трассировки 53
Глава 4 Практическая реализация регулярного алгоритма трассировки 73
Глава 4.1 Организация интерфейса программы доразводкн цепей с подсистемой топологического проектирования заказных БИС 73
Глава 4.2 Основные объекты, формируемые в программе разводки цепей .75
Глава 4.3 Инициализация объектов регулярного алгоритма трассировки. 79
Глава 4.4 Особенности реализации процедуры Ход Вперед 85
Глава 4.5 Особенности реализации процедуры Ход Назад 89
Глава 5 Пути повышения эффективности работы регулярного магистрального алгоритма 93
Глава 5.1 Использование информации о загруженности канала 93
Глава 5.2 Перемещение контактов на шлюзах 94
Глава 5.3 Визуализация процесса поиска 95
Глава 5.4 Применение распределенных вычислений для параллельной трассировки нескольких цепей 96
Глава 6 Экспериментальные результаты тестирования магистрального регулярного алгоритма 97
Глава 6.1 Сравнительный анализ эффсктпвностп использования волнового алгоритма и магистрального метода 97
Глава 6.2 Эксперименты, показывающие эффективность внесенных усовершенствований в магистральный метод 100
Глава 6.3 Пример топологического проектирования заказной БИС блочной структуры 107
Заключение 111
Экономическое обоснование работы 113
Техника безопасности 115
Список литературы 116
- Анализ основных алгоритмов трассировки соединений
- Описание алгоритма трассировки подсистемы топологического проектирования
- Принципы разработки регулярного алгоритма трассировки
- Основные объекты, формируемые в программе разводки цепей
Введение к работе
Современный научно-технический прогресс характеризуется внедрением во все области человеческой деятельности радиоэлектронной аппаратуры. Известно, что 40 % мирового производства занято выпуском такой техники. Основным узлом радиоэлектронной аппаратуры являются большие интегральные схемы (БИС), постоянные запоминающие устройства (ПЗУ), программируемые логические матрицы (ПЛМ), базовые матричные кристаллы (БМК) и т.д. Процессы проектирования и изготовления интегральных схем являются наиболее автоматизированными.
За период нескольких десятилетий установился процесс проектирования микросхем, ставший традиционным. Считается, что процесс проектирования включает этапы схемотехнического, логического и топологического проектирования. На стадии топологического проектирования решается задача трассировки цепей соединения всех полупроводниковых элементов. Если учесть, что количество элементов достигает миллионов, то станет ясным, масштаб этой проблемы. Она решается путем создания множества алгоритмов трассировки, которые учитывают ту или иную специфику схемы, а также увеличения сроков проектирования до нескольких месяцев, соблюдая тщательность проектирования. Поэтому разработка алгоритмов, которые хотя бы на несколько процентов ускоряют или качественно улучшают решение задачи трассировки, является актуальной.
Таким образом, целью работы является разработка и исследование новых методов трассировки интегральных схем. Для реализации такой цели необходимо решить следующие научные задачи:
1. Провести анализ существующих алгоритмов трассировки, определить их эффективность в зависимости от специфики задачи.
Провести анализ существующих моделей данных различных алгоритмов трассировки.
Разработать принципы построения алгоритма трассировки, который будет иметь лучшие эксплутационные характеристики по сравнению с существующими классическими алгоритмами.
Разработать алгоритм трассировки, который после реализации будет иметь эксплутационные характеристики более лучшие чем классические алгоритмы.
Разработать модель представления данных в канале трассировки, учитывая специфику предлагаемого алгоритма разводки цепей.
Провести макетирование основных блоков алгоритма трассировки и сделать оценку эксплутационных характеристик.
Практическая ценность результатов работы позволит: ускорить и повысить качество разработки БИС; улучшить эксплуатацию программы проектирования БИС. В результате проделанной работы на защиту выносятся:
Результаты анализа существующих алгоритмов трассировки, оценка их эффективности в зависимости от вида применения БИС в электронной вычислительной аппаратуре.
Разработанная модель представления объектов в канале, базирующаяся на моделях классических волнового и канального алгоритмов, и учитывающая особенности конструктива кристалла и разрабатываемого алгоритма.
Разработанный, так называемый Направленный Волновой Алгоритм (НВА) для канальной модели данных, который обеспечивает: — нахождение пути, если его построение возможно, — проведение оптимизации по длине пути и числу поворотов (межслойных переходов).
Включенный в НВА блок итеративной трассировки, который эвристическим методом изменяет порядок трассировки цепей.
Результаты макетирования основных блоков и оценка эксплутационных характеристик данного алгоритма.
Диссертация является законченной научно-исследовательской работой.
Краткое содержание работы сводится к следующему.
В первой главе «Анализ разновидностей и методов трассировки БИС» описываются стандартные, полузаказные и заказные микросхемы. К стандартным БИС относятся: микросхемы широкого применения (микропроцессоры, оперативные запоминающие устройства; микросхемы программируемые перед эксплуатацией (программируемые логические матрицы, постоянные запоминающие устройства).
Стандартные БИС характеризуются регулярностью структуры, простой конфигурацией соединений на уровне дискретных элементов, поэтому в этом случае задача трассировки не является актуальной.
Полузаказные БИС характеризуются тем, что имеют общие части в своей структуре, которые проектируются заранее (стандартные модули). Затем данные модули дорабатываются в соответствии с применением. К этим БИС относятся постоянные запоминающие устройства, программируемые логические матрицы и базовые матричные кристаллы (совокупность базовых элементов, из которых проектировщик может создать нужную схему). Задача трассировки полузаказных БИС требует раскрытия противоречия между числом базовых элементов и оставшейся площадью для трассировки, а также числом контактных площадок для внешних выводов.
Заказные БИС определяются полностью заказчиком и следовательно, каждая разновидность микросхемы такого типа требует полного цикла проектирования. Существует несколько методов проектирования.
Метод «стандартных ячеек». Существует набор стандартных ячеек, которые можно расположить на кристалле в виде рядов. У проектировщика имеется свобода в расположении ячеек и соединении их в схему с целью минимизации площади БИС и длины всех проводников.
Метод «блочного типа». Проектирование производится «сверху - вниз». Каждый уровень блоков определяется проектировщиком различных размеров. В отличие от предыдущего метода, где соблюдается регулярность в размещении ячеек, здесь ячейки могут находиться на произвольных местах.
Проведенный анализ основных алгоритмов трассировки соединений позволяет различить два подхода.
Группа графо-теоретических подходов.
Группа топографических методов.
Т.к. группа графо-теоретических подходов не пригодна для проектирования БИС большой интеграции, то все внимание уделено топографическим методам, которые состоят из следующих этапов: формирование списка соединений, определение порядка сортировки соединений, трассировка, распределение соединений по слоям. Анализируются следующие алгоритмы
Волновой алгоритм. Коммутационное поле разбивается на блоки, в которых обозначаются ячейки. От источника до приемника поэтапно волнообразно распространяется числовой фронт. Направление распространения задается определенными критериями. По достижении цели строится путь.
Магистральный метод. Коммутационное поле представляется совокупностью горизонтальных и вертикальных магистралей. Поиск пути от заданного источника до приемника проводится посредством переходов с одной магистрали на другую. Направление определяется эвристически с целью уменьшения числа перебора.
3. Лучевой алгоритм. Основная идея этого метода состоит в циклическом повторении шагов: продвижение в оптимальном направлении; выявление препятствий и их обход.
Канальный метод. Основным элементов является канал, как замкнутое, прямоугольной формы пространство. Трассировка проводится в два этапа. На первом этапе определяются каналы по которым будут проходить цепи. На втором этапе разводятся все цепи, направленные через те или иные каналы.
Итерационные алгоритмы трассировки и алгоритмы, использующие деформацию трасс соединений Основой их являются рассмотренные ранее алгоритмы, но несколько модернизированные. Их особенность заключается в том, что каждая трасса строится путем итерационного применения определенного алгоритма. Каждый новый шаг прокладывает очередной участок учитывая влияние других разводимых цепей.
В этой главе проводится анализ преимуществ и недостатков всех рассмотренных методов. Констатируется, что в большинстве методов существуют эвристические правила, уменьшающие перебор вариантов. Делается вывод о том, что создание улучшенного алгоритма возможно путем комплексного применения всех методов.
Во второй главе «Подсистема проектирования БИС блочной структуры» рассматривается программный комплекс, в котором применяется разрабатываемый алгоритм разводки цепей. Вводятся понятия: функциональный блок (ФБ), канал и шлюз. Работа программы топологического проектирования начинается с размещения ФБ на рабочем поле кристалла, далее выполняется разбиение свободного для трассировки пространства на каналы, трассировка и распределение соединений по слоям (расслоение).
Для лучшего понимания на Рисунок 8 приведены все элементы, которым даны термины.
На этапе размещения ФБ располагаются на кристалле таким образом, чтобы уменьшить общую длину трассируемых позже цепей. Трассировка соединений осуществляется на первом этапе как глобальная, а затем локальная. Алгоритм глобальной трассировки определяет маршрут прохождения очередной цепи через каналы, затем закрепляются точки пересечения цепью границы канала на шлюзе. Локальная трассировка осуществляет во всех каналах перебор всех цепей и определение их конкретного размещения в канале. Основной алгоритм локальной трассировки использует параллельное разведение цепей. Но так как при этом используется эвристический алгоритм, данный метод не гарантирует полной прокладки цепей, даже если путь для проводников существует. Повысить процент разводимых цепей возможно за счет дополнительного использования других методов трассировки, а точнее их эвристик. Такая попытка сделана в данной работе. Основным требованием к разрабатываемому алгоритму, являющемуся конечной целью данной работы, является гарантированная трассировка всех цепей, если путь, при данной конфигурации уже проложенных соединений, существует. При этом все цепи должны строится с возможно меньшим числом поворотов и возможно меньшей длиной. Такой алгоритм будем называть регулярным.
Анализ основных алгоритмов трассировки соединений
Алгоритмические методы трассировки печатных (пленочных) межсоединений могут быть разделены на две основные группы [33]. Первая группа основана на графо-теоретическом подходе к решению задачи трассировки. Графо-теоретические методы трассировки предполагают построение графовой модели схемы, анализ ее планарности, раскраску графа и т. д. Окончательная фаза работ состоит в построении эскиза топологии схемы при рациональном распределении функций между проектировщиком и ЭВМ. Использование данного класса методов для топологического проектирования современных БИС большой интеграции нереально по причине недостаточной эффективности данных методов для решения задач большой размерности [1], [33]. Ко второй группе относятся так называемые топографические методы, в которых приоритет отдается метрическому аспекту задачи, т.е. после разводки соединения формируется информация, определяющая месторасположение проводников на конструктиве. Топографический метод трассировки в общем случае содержит следующие основные этапы: 1. Формирование списка соединений; 2. Распределение соединений по слоям; 3. Определение порядка прокладки соединений; 4. Собственно трассировка отдельных соединений. В данной работе анализируются непосредственно алгоритмы трассировки межсоединений. В литературе описано достаточное количество алгоритмов трассировки, а также их многочисленные модификации.
Некоторые алгоритмы были разработаны еще для проектирования печатных плат, другие - уже для БИС. Ниже приводятся описания основных классов алгоритмов, их достоинства и недостатки. Ячейка (дискрет) - минимальная площадь на коммутационном поле используемая алгоритмом при трассировке цепей. Ячейка может иметь разные формы, чаще используются квадратные дискреты. Размер грани ячейки равняется минимальной толщине проводника. Дискретное Рабочее Поле - область предназначенная для трассировки и логически разбитая на дискреты. Количество дискрет (o/V - по вертикали, 3\[в. по горизонтали) может быть вычислено: где г - длина области для трассировки, її - длина дискрета, в - ширина области для трассировки, І6 - ширина дискрета. Источник - контакт или участок уже проложенной цепи, от которых алгоритм ищет путь. Приемник - контакт или участок уже проложенной цепи которые нужно соединить с источниками и другими приемниками. Основой многочисленных вариантов алгоритмов из этого класса является волновой алгоритм, опубликованный К. Ли. В литературе он подробно описан в [1], [34]. Перед работой алгоритма происходит построение дискретного рабочего поля (ДРП) на основе информации об области трассировки.
При выполнении данной процедуры для каждого дискрета заводится некоторая структура данных, содержащая в себе информацию о физическом состоянии и логическом состоянии ячейки. Физическое состояние определяет, является ли данная ячейка свободной для прокладки проводников любой ориентации, свободной для прокладки проводников только определенной ориентации (например, горизонтальной или вертикальной) или занятой ячейкой. Данный способ кодирования характерен для конструктивов с двумя слоями. Если количество слоев больше, то необходимо модифицировать описание физического состояния дискрета. Логическое состояние определяется при работе алгоритма поиска пути и зависит от самого алгоритма. Таким образом, объем памяти, необходимой для ДРП определяется по формуле: После построения ДРП определяются источники и приемники. Далее происходит поиск пути от источника до приемника.
От источника моделируется распространение числовой волны, заключающееся в продвижении фронта от источника (см. Рисунок 2). Фронтом числовой волны называется множество дискрет, равноудаленных от источника. Очередной фронт образуется из тех ячеек, которые доступны от ячеек предыдущего фронта, но не были достигнуты волной ранее, и по которым возможна прокладка проводника в определенном направлении. Ячейка, принадлежащая k-ому фронту, характеризуется волновым числом к. Процесс прямого хода волны заканчивается по достижении приемника, либо если в очередной фронт невозможно включить ни одного дискрета. В последнем случае источник не может быть соединен с приемником. Если приемник достигнут, то начинается обратный ход, в результате которого формируются отрезки разводимой цепи. На обратном ходе происходит переход от ячейки с волновым числом т, к ячейке с волновым числом т-\, до достижения источника. Достоинства волнового алгоритма (ВА): 1. Если путь существует, то В А найдет его. Это гарантируется просмотром, в поисках приемника, всех достижимых от источника дискрет. 2. В ВА возможно применение как параллельной, так и последовательной оптимизации по ряду параметров, причем организация оптимизации не требует значительных затрат при программировании. При параллельной оптимизации для каждой анализируемой ячейки вычисляется вес по ряду параметров (расстояние от источника, расстояние до занятой области и т. д.). В очередной фронт волны включаются только ячейки с минимальным (максимальным) весом. При последовательной оптимизации все параметры, по которым идет оптимизация, упорядочены по важности. Например, критерий F1 - число пересечений с уже проведенными соединениями; F2 - длина пути и т. д. Из всех ячеек в очередном фронте выбираются наилучшие по критерию F1, из них наилучшие по критерию F2 и т. д. Полученные дискреты образуют новый фронт волны. Таким образом, ВА из всего множества допустимых соединений определяет соединение оптимальное по заданным критериям. В классическом алгоритме ЛИ происходит оптимизация по длине пути. Волновое число, которым помечается приемник в конце поиска, указывает длину самого короткого маршрута. Недостатки ВА: 1. Одним из основных недостатков ВА является большое количество требуемой памяти. Основная емкость памяти определяется выражением: 0 аЛ-?Л Ь, где 3V - количество ячеек ДРП; а - количество бит информации необходимое для того, чтобы охарактеризовать состояние дискрета; Ъ1 -количество дискрет, образующих фронт волны; b количество бит информации, необходимых для задания положения дискрета. Таким образом, количество требуемой памяти сильно зависит от размеров коммутационного поля. 2. В процессе поиска пути алгоритму необходимо обработать все ячейки ДРП, лежащие на расстоянии, равном или меньшем расстоянию от источника до приемника, т. е. попавших во фронт волны. Количество таких ячеек сильно зависит от степени загруженности коммутационного поля занятыми областями, от расстояния от источника до приемника, от местоположения источника. Поэтому, при значительных размерах поля трассировки процесс построения цепи ВА требует значительного времени.
Описание алгоритма трассировки подсистемы топологического проектирования
Трассировка соединений осуществляется канальным методом в два этапа: вначале глобальная, а затем локальная трассировка.
Алгоритм глобальной трассировки (далее глобальный трассировщик), используя координаты контактов очередной цепи, определяет ее маршрут прохождения через каналы. В общем случае контакты цепи могут принадлежать разным ФБ. При этом учитываются размеры каналов и их текущая загруженность другими цепями. При переходе цепи из одного канала в другой за цепью закрепляется точка шлюза, через которую она будет проходить. Некоторые цепи глобальный трассировщик делит на секции. Соответственно, множество контактов цепи в канале разделяется по принадлежности к определенной секции.
После глобальной трассировки выполняется локальная трассировка для каждого канала, в результате которой определяется конкретное расположение разводимых цепей. Ограничение пространства трассировки одним каналом значительно уменьшает объем необходимой памяти ЭВМ и упрощает процесс разводки цепей.
Алгоритму локальной трассировки передается описание контактов локальной цепи в канале. Контактом цепи в канале может быть контакт ФБ, внешний контакт схемы или точка шлюза, закрепленная за цепью.
При трассировке цепей в каналах используется подход комбинирования алгоритмов разводки. На первом этапе локальная трассировка цепей в канале осуществляется канальным методом. Вначале, канальный алгоритм, учитывая количество контактов цепи и их расположение на гранях канала, разбивает цепь на базовые участки (БУ). Каждый БУ принадлежит определенному классу БУ bt из множества J8. Каждому классу БУ соответствует определенная конфигурация (прототип) соединения и заданная схема его разводки (например, горизонтальный и вертикальный участки, соединяющие два контакта), используя которую канальный трассировщик пытается развести данный БУ. На Рисунок 10 изображена цепь, имеющая в канале 4 контакта, которая была протрассирована путем разводки трех БУ. Цифрами обозначена принадлежность отрезков определенному БУ.
Описанный метод позволяет проводить трассировку каждого БУ достаточно быстро, так как пространство возможных решений ограничивается множеством соединений, подобных заданной в классе Ь{ конфигурации.
Канальный трассировщик использует принцип параллельной трассировки, позволяющий учитывать взаимовлияние различных цепей. Расположение отрезков трассируемой цепи на первом этапе жестко не фиксируется, что позволяет делать их перемещение в некоторой области, если определенная цепь препятствует разводке другой цепи.
Использование описанного канального метода позволяет за приемлемое время разводить значительное количество цепей заказных БИС высокой интеграции, при этом большинство разводимых цепей имеют минимальное число поворотов и достигаются хорошие результаты по общей длине соединений.
Но, как любой эвристический алгоритм, данный метод не гарантирует того, что цепь, для которой существует путь, будет разведена. Действительно, если возможная трасса цепи не входит ни в один из классов БУ из множества 6, то данный алгоритм не найдет путь.
Повысить процент разводимых цепей возможно за счет использования упоминаемой в главе 1.3 тактики использования различных методов трассировки. Таким образом, в локальный трассировщик необходимо включить регулярный алгоритм, предназначенный для доразводки цепей в определенном канале. Основное количество цепей трассируется с высокой скоростью канальным методом, после чего неразведенные цепи обрабатывает алгоритм доразводки, гарантирующий построение соединения, если путь для его прокладки существует, при определенном положении разведенных ранее цепей.
Разработке и исследованию вышеупомянутого алгоритма доразводки соединений посвящена данная работа. Выводы: 1. Предложенная система топологического проектирования предназначена для трассировки цепей БИС блочной структуры. Применяется метод декомпозиции коммутационного поля на каналы, в которых и осуществляется разводка цепей. 2. Контактами цепи могут являться выводы на ФБ, гранях канала или точки на шлюзах. Цепь может состоят из нескольких секций. 3. Трассировка цепей в системе выполняется путем совместного использования трех алгоритмов. Первый, глобальный трассировщик, определяет принадлежность цепей определенным каналам, устанавливает их маршрут. Второй, эвристический, предназначен для быстрой локальной разводки большинства цепей. Третий, регулярный, используется для доразводки цепей, оставшихся после работы первого алгоритма.
Принципы разработки регулярного алгоритма трассировки
Первоначально для разрабатываемого алгоритма трассировки была выбрана дискретная модель представления пространства трассировки, аналогичная описываемой ранее. Проведя анализ алгоритмов трассировки для дальнейшего исследования был выбран волновой алгоритм. Действительно, одним из основных, наиболее часто описываемых в литературе алгоритмов трассировки, работающем на данной модели, является волновой алгоритм. В [31] его также называют алгоритмом трассировки лабиринта. Общая схема организации процесса трассировки разработанного алгоритма соответствовала классическому алгоритму ЛИ. Процесс поиска пути был выбран с применением последовательной оптимизации по следующим критериям: 1. минимальное число пересечений с другими цепями, 2. минимальная длина пути, 3. минимальное число поворотов разводимой цепи. Ячейки дискретного поля кодировались методом путевых координат. Внесено несколько усовершенствований для повышения эффективности алгоритма.
Программная реализация волнового алгоритма выполняла основную задачу, т.е. находила путь, если он существовал, при заданной конфигурации разведенных соединений. Получаемые соединения были оптимальны по указанным выше критериям.
Но при практической эксплуатации волнового алгоритма временные затраты на обработку цепей и требуемый объем памяти оказались недопустимо велики.
Дискретная модель представления канала и поиск на ней оказались малоэффективными для решаемой задачи из-за высокой размерности пространства состояний, в котором ведется поиск.
Поэтому принято решение о переходе к магистральной модели представления поля трассировки и разработке соответствующего алгоритма.
В чем преимущество данной модели перед дискретной? За счет перехода от дискрета к участку магистрали значительно уменьшается количество элементов, с помощью которых представлено состояние канала. Следствием этого является уменьшение памяти, необходимой для хранения модели поля трассировки, а также уменьшение пространства состояний на котором организуется перебор с целью получения решения. В отличие от алгоритмов, работающих на дискретной модели, уменьшается зависимость времени обработки цепи от размеров поля трассировки, расстояния между источником и приемниками, степени заполненности рабочего поля отрезками ранее разведенных соединений.
В следующем пункте подробно описывается модель канала, используемая разрабатываемым алгоритмом.
Разрабатываемый алгоритм предполагается использовать совместно с канальным методом в локальном трассировщике. Вся информация об области трассировки содержится в модели канала, сформированной в процессе работы канального метода. Дадим более подробное описание данной модели канала.
В соответствии с алгоритмом разбиения общего пространства, предназначенного для трассировки, на каналы левая и правая грани любого канала могут граничить либо с функциональным блоком, либо выходить на границу КП. Таким образом, шлюз может располагаться только на верхней или нижней грани канала, как показано на Рисунок 8.
В модели канала, используемой канальным трассировщиком, присутствуют описания всех шлюзов канала, всех функциональных блоков, граничащих с данным каналом, размеры канала и координаты его расположения на КП. Непосредственно при трассировке цепей канал представляется как совокупность горизонтальных и вертикальных магистралей. В описании каждой магистрали предусмотрено описание двух контактов, соответствующих данной магистрали и лежащих на грани канала. Ширина магистрали соответствует минимальной толщине соединения. Количество горизонтальных (вертикальных) магистралей равняется длине (ширине) канала, разделенной на минимальную толщину соединения.
Разведенные цепи в канале представляются как совокупность горизонтальных и вертикальных отрезков и множества контактов.
Описание каждого отрезка цепи содержится в модели канала и соответствует определенной магистрали, на которой находится отрезок, или нескольким магистралям, если отрезок не единичной толщины.
Описание каждой цепи, проходящей через данный канал, содержит описание ее контактов в канале (смотри определение контакта в канале) и разведенных участков цепи. Контакты цепи могут быть разделены на секции.
Также в модели канала присутствует информация о занятых для трассировки участках на верхней и нижней горизонтальных магистралях, соответствующих граням функциональных блоков и горизонтальным отрезкам цепей в соседних каналах, соприкасающихся с общим для двух каналов шлюзом.
В отличие от канального трассировщика в разрабатываемом алгоритме было принято описание канала на основе данных освободных участках магистралей. Под свободным участком магистрали (СУМ) понимается отрезок, по которому разрешается проведение разводимой цепи, т.е. разводимая цепь не будет соприкасаться с другими соединениями и будет удовлетворять ограничениям, которые определяются конструкторской реализацией. Таким образом, для разрабатываемого алгоритма канал представляется множеством СУМ, на котором будет происходить поиск соединения. Очевидно, что конфигурация СУМ в канале для различных разводимых цепей будет различна.
Помимо множества СУМ, в модели канала необходимо описание контактов разводимой цепи.
Дальнейшему развитию модели канала послужило наблюдение того факта, что некоторое количество СУМ, лежащих на соседних магистралях, имеют одинаковые координаты левого и правого конца. Таким образом, некоторый прямоугольник, полностью свободный для трассировки, раздробляется на участки единичной толщины. Введенные усовершенствования заключаются в объединении свободных отрезков одинаковой длины, лежащих на соседних магистралях, в единый блок.
Основные объекты, формируемые в программе разводки цепей
Модель канала, необходимая для работы регулярного алгоритма трассировки, базируется на множестве СУМ данного канала. Модификация классов MEMKAN и BUFER позволила использовать их для хранения и манипулирования описаниями СУМ. В данные классы были добавлены некоторые функции и изменена структура описания участка UBUF. Основной механизм работы данных классов остался прежним. Таким образом, в программе конструируются объекты fmav, fmag класса MEMKAN и fbof класса BUFER, которые аналогичны объектам cmav, cmag, cbuf, но работают с СУМ. Создаются объекты fmav, fmag, fbof для определенного канала по описанию множества ЗУМ. Признаки контактов-приемников разводимой секции помечаются на соответствующей магистрали объектов fmav, fmag. Также в описании канала содержатся участки, соответствующие ранее разведенным отрезкам текущей секции разводимой цепи. Совместное описание СУМ и ЗУМ, принадлежащих разводимой цепи, которые могут быть либо источниками, либо приемниками, в одних объектах удобно для работы функций поиска и обратного хода. Для описания СУМ в регулярном алгоритме трассировки структура UBUF, используемая в классах MEMKAN и BUFER замещается структурой FPART, представленной в табл. 2. Каждое описание участка в виде данной структуры идентифицируется программой его смещением (2 байта) в буфере fbuf. Поля kl, k2, N_MAG, S, NAP характеризуют размеры участка, его положение в канале. Как было показано ранее в процессе поиска приемников формируется дерево поиска, содержащее вершины-участки, которые проанализировал алгоритм трассировки.
В практической реализации функции поиска пути связывает СУМ в цепочки участков с помощью указателя SMAG, который для каждого элемента цепочки указывает на его родительский участок. Если участок не анализировался функцией поиска, то это поле содержит константу END. Участок, проанализированный процедурой поиска полностью, характеризуется полем ANL, которое в описании таких участков содержит 1 (иначе 0). Значение 1 означает, что у данного участка проанализированы все соприкасающиеся СУМ. Поле LOG показывает принадлежность участка к одной из четырех категорий: LOG=0 - свободный участок магистрали; LOG=l - участок-источник; LOG=2 - участок-приемник; LOG=3 СУМ, который был помечен контактом-источником. Т.к. для контакта не может быть определен указатель на его описание, то для СУМ, которые в цепочке участков имеют родительскую вершину - контакт, не может быть заполнено поле SMAC. Такие СУМ характеризуются полем LOG=3. Для формирования множества СУМ и работы с ним программа использует следующие функции (помимо функций, упоминаемых в предыдущем разделе): Функции-члены класса MEMKAN: POI - поиск свободного места на заданной магистрали, используется для формирования СУМ; SET_PIN, GET_PIN, DEL_PIN - занесение, получение и удаление признака контакта на определенной магистрали; ALL_MODI - модификация участка магистрали; GET_COR - дать текущий участок магистрали. Функции-члены класса BUFER: GET_SMG, GET_SMV - дать смещение в буфере текущего горизонтального (вертикального) участка; SET_SMG, SET_SMV - установить горизонтальный (вертикальный) участок по смещению; GET_PART - дать описание участка по его смещению.
Для получения информации о занятых областях на первой и последней горизонтальных магистралях, которые соответствуют выходящим на грань канала функциональным блокам и горизонтальным участкам в соседних каналах, соприкасающихся с общим шлюзом, используются функции класса MEMKAN для 0 и hkan+1 магистрали, где hkan- высота канала. В программе доразводки цепей создан класс RLIST, объект которого является стеком типа FILO (First Input - Last Output). При создании данного объекта в памяти создается буфер с размером, задаваемым в конструкторе. При занесении и получении элемента стека работа происходит с данным буфером. Функции, выделяющие и возвращающие участок оперативной памяти при работе с объектом класса RLIST, вызываются лишь в конструкторе и деструкторе, что ускоряет процесс занесения и извлечения элементов стека. В программе создаются следующие объекты данного класса: стек FRONT, предназначенный для хранения текущей цепочки участков, по которой идет поиск; стек DONE содержит отрезки, разведенные регулярным алгоритмом трассировки; другие вспомогательные объекты. В программе создан класс SLIST, объект которого является списком. Элементы данного списка связаны указателями от первого элемента к последнему. Объекты данного класса LSO, LDE является соответственно списком источников и списком приемников. Основные функции-члены данного класса: PUT - занести элемент в список; GIVE - дать текущий элемент списка; DEL - удалить текущий элемент; CROSS - найти пересекающий или соприкасающийся элемент в списке; CNT2P - найти отрезок, подходящий к данному контакту.
