ПОСТАНОВКА ЗАДАЧИ И КЛАССИФИКАЦИЯ АЛГОРИТМОВ ТРАССИРОВКИ
ПОСТАНОВКА ЗАДАЧИ. КЛАССИФИКАЦИЯ МЕТОДОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ КОНСТРУКТИВНЫХ УЗЛОВ РЭС
РАЗМЕЩЕНИЯ МОДУЛЕЙ РЭС В МОНТАЖНОМ ПРОСТРАНСТВЕ
АЛГОРИТМЫ И МОДЕЛИ
Высокая плотность размещения элементов РЭС создает большие трудности при реализации соединений между ними. В этой связи задача размещения элементов на плоскости определяет быстроту и качество трассировки. Оптимальное размещение элементов обеспечивает повышение надежности ЭВА, уменьшение размеров конструктивных единиц, минимизацию взаимных наводок, задержек сигналов, уменьшение общей длины соединений и т. п.
Формально задача размещения заключается в определении оптимального варианта расположения элементов на плоскости в соответствии с введенным критерием, например с минимальной взвешенной длиной соединений.
В общем виде задача размещения может быть сформулирована следующим образом: в монтажном пространстве задана область, которая разбивается на множество позиций (посадочных мест), число которых должно быть не меньше числаразмещаемых элементов. Очевидно, что каждый элемент может занимать не более одного посадочного места, расстояние между которыми описывается симметричной матрицей расстояний . Имеющееся множество элементов Х={х1, х2,..., хп}, связанных между собой множеством электрических цепей E={e1, e2,..., eп}t, , необходимо таким образом отобразить на множестве Р, чтобы обеспечивался экстремум целевой функции качества размещения.
Исходными данными при решении задачи размещения являются прямоугольная конструкция (ячейка, кристалл, панель), число элементов, которое получено в результате компоновки, т. е. разбиения графа схемы на части, и граф схемы соединений элементов или его матричный (списковый) эквивалент. На прямоугольную конструкцию накладывается декартова система координат с осями s и t, определяющая граф Gr, представляющий собой координатную решетку. Расстояние di,jмежду узлами i и j этого графа описывается выражением (1.4).
Задача размещения сводится теперь к отображению заданного графа схемы G = (X, U) в решетку Grтаким образом, чтобы вершины множества X размещались в узлах решетки и, например, суммарная длина или суммарное число пересечении были наименьшими для возможных способов отождествления вершин графа и узлов решетки. В выражениях (3.1) и (3.2) сi,j— вес ребра иi,j(число кратных ребер между вершинами хi, хj), р(иi,j) — число пересечений ребра ui,j.
Использование САПР и их подсистем (подсистемы размещения в частности) в процессе проектирования конструктивных узлов ЭВА повышает эффективность проектирования.
Классификация ЭВА осуществляется по таким признакам, как, например, назначение, принцип работы, условия эксплуатации, масштаб выпуска, применение и т. д. Однако с точки зрения задачи размещения приведенные признаки классификации слабо приемлемы, и в этой связи используется классификация ЭВА, позволяющая определить множество решаемых задач. Как отмечалось выше, ЭВА всегда имеет иерархию конструктивных узлов: конструктивно неделимый узел (электрорадиоэлемент, интегральная микросхема); типовой элемент замены (ТЭЗ); панель-блок; рама; шкаф: стойка.
Если множество всех объектов проектированияразбито на N подмножеств:
причем элементы каждого подмножества Yiобразуют классы аппаратуры данного (/-го) уровня ЭВА, то множество решаемых задач определяется как
где yij—j-й класс аппаратуры /-го иерархического уровня.
В настоящее время основными объектами проектирования на этапе конструкторского проектирования ЭВА являются печатные платы (двух- и многослойные), реализуемые в виде ТЭЗ и ИМС.
Выделены следующие классы ИМС: на основе типовых функциональных ячеек и блоков; на основе базового кристалла (матричные ИМС); МДП, проектируемые на компонентном уровне; гибридно-пленочные и биполярные с одним сло-ем коммутации. Типовые элементы замены реализуются, как правило, на платах с печатным монтажом. Различают одно-, двух- и многослойные печатные платы (со сквозной металлизацией переходных отверстий либо открытыми контактными площадками).
Рассмотрим основные характеристики указанных выше объектов проектирования.
1. Принцип построения ЭВА (аналоговая, цифровая и аналого-цифровая). Выделение этого признака обусловлено различием требований к проектируемому объекту (т. е. различием критериев оптимизации для задачи размещения) и возможных конструкторско-технологических ограничений. Так, при проектировании цифровой аппаратуры необходимо обеспечение максимального быстродействия; для аналоговой аппаратуры важно обеспечение заданного теплового режима и т. п. Кроме того, принцип построения ЭВА определяет, как правило, такую характеристику, как регулярность геометрии элементов объекта проектирования и технологию изготовления.
2. Регулярность структуры объекта проектирования. Регулярность структуры объекта определяется геометрией на элементном уровне данного объекта. Так, проектирование топологии ИМС различает два подхода: на базе типовых ячеек и на компонентном уровне. В первом случае обеспечивается регулярность топологии объекта, во втором же, как правило, структура объекта нерегулярна. Для линейных ИМС, реализуемых на основе гибридно-пленочной технологии, структура объекта обладает сильным разнообразием, причем задача осложняется наличием всего одного слоя коммутации. При проектировании печатных плат регулярность структуры объекта может характеризоваться тремя уровнями: структура регулярна; структура слабо нерегулярна (элементы кратны по одному из размеров, либо число разногабаритных элементов не превышает 10—20% от общего числа элементов); структура существенно нерегулярна.
Геометрия разногабаритных элементов, как показывает анализ компонентной базы объектов проектирования, может быть отнесена к одной из трех групп (прямоугольники кратных размеров, прямоугольники произвольных размеров, многоугольники произвольных размеров). Цифровая аппаратура, реализуемая на печатных платах, имеет, как правило, регулярную структуру. Отметим, что проектирование объектов на компонентном уровне, характеризующееся сильной нерегулярностью структуры, обеспечивает наивысшую плотность монтажа и лучшие схемотехнические характеристики объекта; однако возможности автоматизации процесса решения задачи размещения затруднены.
3. Сложность объекта. Под сложностью объекта проектирования уровня i будем понимать число компонентов уровня (i—1), его образующих. Можно выделить следующие объекты:
а) очень высокой сложности (число компонентов более 106);
б) высокой сложности (число компонентов от 103 до 106);
в) средней сложности (число компонентов от 102 до 103);
г) малой сложности (число компонентов менее 102). Сложность объекта проектирования в значительной степени
влияет на процесс решения задачи размещения. Уже для ИМС третьей степени интеграции (число компонентов до 104) в состав методов размещения необходимо включать декомпозиционные процедуры. Проектируемые в настоящее время объекты с печатным монтажем относятся к объектам малой и средней сложности.
4. Технологичность объекта проектирования. Данная характеристика объекта проектирования отражает способ формирования коммутирующего слоя. Технологичность объекта как типовая характеристика определяет параметры оптимизации варианта размещения.
Как известно, основной задачей в САПР ЭВА на этапе конструкторского проектирования является объединение конструктивных узлов предшествующего уровня. В качестве
базового функционального узла для подсистемы размещения выбирают в основном ИМС на основе базового кристалла и объекты с печатным монтажем (двухслойные печатные платы). Аналогичными характеристиками обладают (относительно степени регулярности структуры объекта) ИМС ячеечного типа и МДП ИМС. В соответствии с изложенными выше принципами классификация объектов проектирования иллюстрируется рис. 3.1.
Отметим, что при разработке методов размещения необходимо ориентироваться на нерегулярную структуру, так как к этому случаю возможно сведение других вариантов структуры ОП. С другой стороны, с целью упрощения затрат на разработку и функционирование систем и подсистем САПР ОП необходимо обратить внимание на разработку систем автоматизированного проектирования унифицированных (с регулярной или слабо нерегулярной структурой) объектов.
Классификацию алгоритмов размещения конструктивных элементов можно проводить исходя из различных признаков:
1. По постановке задачи. Рассматриваемая задача может быть сформулирована как задача линейного, нелинейного, динамического, стохастического программирования или как задача условной минимизации.
2. По структуре построения алгоритма. Такой подход позволяет выполнять синтез конкретного варианта алгоритма и осуществлять его структурный анализ (пользуясь типовыми признаками).
3. По принципу решения задачи размещения.
Третий признак позволяет выделить две основные группы методов решения задачи размещения:
непрерывно-дискретные;
дискретные.
При использовании непрерывно-дискретных методов оптимизации задача размещения решается в два этапа: на первом определяют координаты местоположения центров элементов, при которых целевая функция имеет экстремальное значение; на втором полученные координаты «округляются» до фиксированных целочисленных значений координатной сетки, нанесенной на поверхность коммутационного поля (КП).
В дискретных методах оптимизации модель КП представляют в виде множества фиксированных координат позиций. Задача размещения сводится к сравнению различных вариантов закрепления элементов в этих позициях и выбору того из них, который обеспечивает экстремальное значение целевой функции. Классификация алгоритмов размещения показана на рис. 3.2.
Обилие методов решения задачи размещения элементов объясняется желанием их разработчиков создать наиболее благоприятные условия для выполнения следующих этапов автоматизированного проектирования, и в частности этапа трассировки.
Проведем анализ классификации алгоритмов размещения. Одним из основных параметров, характеризующих процесс решения задачи размещения, является метод решения. Существующие методы решения задачи размещения могут быть классифицированы по следующим признакам:
по принципу реализации — конструктивные, т. е. создающие размещение, и итерационные, т. е. улучшающие качество полученного ранее размещения;
по структуре построения метода размещения — на основе суммы конструктивно-математических признаков метода (назначение метода, порядок ввода компонентов в процесс решения, сущность метода математической оптимизации целевой функции и др.);
по постановке задачи (она может быть сформулирована как, например, задача линейного или квадратичного назначения, как задача коммивояжера и т. п).
Общим недостатком существующих классификаций методов размещения (см. рис. 3.2) является их слабая информативность относительно возникающих практических задач — ни одна из классификаций не учитывает таких характеристик, как сложность объекта проектирования, структура объекта. С этой точки зрения необходима классификация, позволяющая рассматривать методы размещения не только с позиции принципа реализации, но и разрешающая проблему структурного синтеза способа размещения на основе типовых признаков ОП. В качестве типовых характеристик объекта выбираются структура ОП и его сложность. Рассмотрим классификации ОП.
Структура объекта:
а) регулярной структуры;
б) нерегулярной структуры (элементы имеют форму прямоугольников кратных размеров либо число разногабаритных элементов не превышает 10% от общего числа элементов);
в) существенно нерегулярной структуры (элементы имеют форму прямоугольников произвольных размеров либо многоугольников произвольной формы).
Сложность объекта:
а) объекты высокой сложности (число элементов более 103);
б) объекты средней сложности (число элементов до 103);
в) малой сложности (число элементов менее 102).
На основе данной характеристики объекта выделяются следующие классы методов размещения:
конструктивные (последовательные);
итерационные;
реализующие математические или физические аналоги задачи размещения;
декомпозиционные;
поисковые.
Рассмотрим указанные методы размещения. Различают конструктивные методы с первоначальным размещением (КМПР) и без него. Конструктивные методы с первоначальным размещением заключаются в следующем. Первоначально задается или выбирается по определенным правилам подмножество (так называемое ядро) размещенных элементов. Далее анализируется подмножество неразмещенных элементов. Из этого подмножества выбирается один элемент, соответствующий наилучшему размещению (по заданному критерию). Затем процесс повторяется итерационно до полного размещения всех элементов. После размещения элементов на посадочные места они более не перемещаются. В конструктивных методах без первоначального размещения ядро выбирается на основе различных эвристических приемов. Конструктивные методы очень просты, требуют небольших затрат машинного времени, находят широкое практическое применение. При большом числе элементов ВС А имеет вид О(п)...О(п2).
Итерационные алгоритмы размещения производят обработку ММ схемы, размещенной на плоскости в итеративном (итерационном) режиме. Суть таких алгоритмов в следующем. Выбирается некоторое подмножество элементов, которые необходимо переместить для оптимизации выбранного критерия. Для этого подмножества определяются соответствующие кандидаты для переразмещения. Процесс перестановок проводится итеративно, пока происходит оптимизация критерия размещения. В отличие от конструктивных алгоритмов итерационные более точные, всегда
обеспечивают получение локального минимума, но менее быстродействующие. В итерационных алгоритмах ВСА лежит в пределах О(п2)... 0{п3).
Классическим методом размещения, реализующим физические аналоги задачи размещения, является метод релаксации (или силового размещения).
Представителем методов размещения, реализующих математические аналоги задачи размещения, является стратегия метода ветвей и границ, описанная в гл. 1. Суть методов релаксации заключается в следующем. Размещаемые элементы считаются как бы соединенными между собой связями, подобными пружинам, которые притягивают элементы друг к другу. На основе закона Гука определяют взаимную силу притяжения каждой пары элементов xtи здесь k — коэффициент
упругости, задаваемый весами peбep cijMM КС, задаваемой графом; dij — вектор расстояний между элементами хi хj
Известно, что общая сила притяжения, действующая на каждый элемент КС, будет равна сумме сил. котопые действуют со стороны всех пар элементов
Тогда на каждый элемент xiбудет действовать суммарный вектор силы
При разрешенном свободном перемещении всех элементов в выбранной модели оптимальное состояние всех элементов будет тогда, когда модель будет иметь минимальное напряжение. В случае разрешенного движения только одного элемента КС xtустойчивое размещение возникнет при попадании хiв целевую точку ц(хi), где сумма воздействующих на него сил равна нулю. Расстояние до ц(Хi) определяют по формуле
а координаты целевой точки в декартовой системе sot
Известно, что точка (si, ti) представляет собой центр тяжести масс хi, если элемент хi, КС рассматривать как массу, вес которой равен весу ребра, соединяющего элементы хiи хj. Методы релаксации позволяют изменять размещение за счет последовательного изменения напряжения на отдельных элементах. Основной недостаток — поиск новой точки ц(хi), если это место занято другим элементом, который по тем или иным причинам не может быть перемещен. Для таких методов ВСА колеблется в пределах О(п2)... О(п4).
Декомпозиционные методы заключаются в последовательном, параллельном, параллельно-последовательном (последовательно-параллельном) разбиении математической модели КС и модели монтажного пространства.
Поисковые методы размещения для получения эффективного решения используют иерархические приемы с разбиением исходной задачи на ряд подзадач и решения каждой из них перебором на дереве решений. Выделение этой группы методов размещения обусловлено тем, что задача оптимального размещения часто сводится к перебору вариантов, часто близкому к полному, что для электронных узлов ЭВА высокой степени интеграции неприемлемо. Поисковые методы позволяют заменить полный перебор вариантов перебором с отсечениями неэффективных решений, обеспечивая при этом высокую точность решения.
4. По принципу структурной общности в пределах каждой группы выделяются подгруппы. Наиболее применимы следующие четырнадцать подгрупп методов:
Приведем краткую характеристику методов. Методы размещения по связности относятся к последовательным методам. Здесь вводится r-шаговый процесс принятия решений. При этом на каждом шаге выбирается один из неразмещенных элементов и помещается в одну из свободных позиций. Последующий выбор элементов основан на анализе связности оставшихся с размещенными. Структура дальнейшей стратегии основана на заданных правилах выбора очередного элемента (например, максимальным образом связанного с размещенными) и позиции для его установки. Временная сложность алгоритмов равна О(ап).
Методы связывания пар относятся к группе последовательных алгоритмов. Процесс начинается с выбора в качестве начальной пары элементов, которые имеют, например, наибольшую сумму
общих связей (ребер ММ, цепей КС). Далее происходит последовательное подсоединение элементов с выполнением первоначально введенного правила до полного размещения всех элементов. Временная сложность алгоритма равна O(а„).
Методы расширения ядра относятся к последовательным алгоритмам. Здесь для каждого неразмещенного элемента определяется среднее суммарное число ожидаемых связей с размещенными элементами на основе анализа покрывающих деревьев. Для размещения выбирается элемент с наибольшим значением и располагается во взвешенном центре тяжести групп уже размещенных элементов. Далее процесс продолжается итеративно. Временная сложность алгоритма равна
Матричные методы размещения относятся к конструктивным алгоритмам. Выбор элемента и позиции для него на r-м шаге выполняется по специальной матрице размещениякаждый элемент которой bijсоответствует «цене назначения» элемента хiв позицию pj при условии, что к—1 элементов уже размещены. Структура алгоритма основана на различных способах определения «цен назначений» и методиках выбора. Временная сложность алгоритма равна
Методы обратного размещения относятся к последовательным алгоритмам. Осуществляют предварительную оценку каждого из размещаемых элементов х1, х2 ... хnи каждой свободной позиции р1, р2, ..., рп. Далее производится упорядочивание элементов по возрастанию или убыванию введенных характерис-тик, и затем все элементы размещаются одновременно. Временная сложность алгоритма равна О(аn).
Для размещения методом разбиения используются как последовательные, так и итерационные алгоритмы (см. гл. 2). Например, можно применять итерационные алгоритмы разбиения КС на линейки с размещением их на монтажной плоскости с минимизацией суммарного числа связей между линейками. Причем для улучшения качества алгоритма размещения разбиение можно выполнять на горизонтальные и вертикальные линейки и в общем случае на области произвольной конфигурации. Временная сложность алгоритма равна
Методы парных перестановок относятся к классу итерационных алгоритмов и являются простейшими в этом классе. Исходные данные — это начальное размещение или результат предыдущей итерации. Первоначально выбираются два элемента и производится пробный обмен их местами. Если при этом происходит оптимизация критерия (например, уменьшение суммарной длины соединений), то производится обмен. Далее выбирается новая пара элементов, и процесс продолжается, пока не будет применено введенное правило остановки. Временная сложность алгоритма равна О(a2). Методы групповых перестановок относятся к итерационным алгоритмам. Одним из них является метод Штейнберга. В нем выбираются подмножества максимально несвязанных элементов. В течение каждой итерации производятся пробные перестановки. Если, например, суммарная длина не уменьшается, то процесс заканчивается. Временная сложность алгоритма равна
Методы релаксации могут использовать как последовательные, так и итерационные алгоритмы. Отметим, что на практике чаще применяют итерационные методы релаксации.
Методы случайного поиска основаны на использовании метода Монте-Карло (статистических испытаний) и относятся к итерационным алгоритмам. На основе датчика случайных чисел выполняют генерацию случайных расположений элементов в позиции плоскости с запоминанием лучшего результата (в смысле заданного критерия оптимизации). Процесс продолжается, пока не будет пересмотрено заданное число вариантов. Наилучший результат считают результатом решения задачи.
Идея методов направленного поиска описана выше.
Методы последовательного сдвига относятся к классу итерационных алгоритмов, только оптимальное положение элемента определяют не перебором приращения целевой функции, а аналитически. Например, выполняется последовательный сдвиг каждого из элементов в положение, где сила, действующая на него со стороны других элементов, минимальна. Временная сложность алгоритма составляет ).
Иерархические методы являются комбинацией поисковых методов и методов разбиения. Временная сложность алгоритма равна
Параллельно-последовательные методы заключаются в параллельном разбиении КС на линейки с последовательным оптимизационным процессом размещения элементов внутри линеек. Временная сложность алгоритма равна
В пределах подгруппы каждый метод может иметь одну или несколько модификаций (способов), его реализующих.
3.2. МОДЕЛЬ ЗАДАЧИ РАЗМЕЩЕНИЯ. ВЫБОР ЦЕЛЕВОЙ ФУНКЦИИ
Целевая функция; метрические, топологические, надежностные критерии качества; канал; трасса; дерево целей; оценка минимальной длины ребер графа
Принцип принятия решения в задаче размещения элементов можно охарактеризовать следующими параметрами (рис. 3.3): модель представления входной информации; математическая модель коммутационной схемы объекта проектирования; критерий или показатель качества решения; алгоритм вычислений.
Пусть монтажное поле представляет собой прямоугольную область Z, разбитую на прямоугольные части zt. Назовем каждую из таких частей зоной размещения группы (блока) элементов. Разбиение осуществляется исходя из геометрии элементов, образующих блоки, размеров зон размещения и монтажно-коммутационного поля и предполагает выполнение следующих условий:
можно сформулировать следующим образом. Требуется распределить элементы из множества X по зонам размещения так, чтобы
где S, si,-— площади области размещения хi-го элемента соответственно.
Затем нужно определить координаты положения каждого элемента внутри зоны размещения при выполнении следующих условий:
где F* — обобщенный показатель качества размещения; F1— показатель качества размещения по метрическим (электрическим) характеристикам; F2— показатель качества размещения по топологическим характеристикам.
Предложенная постановка задачи приемлема как в поле фиксированных, так и нефиксированных позиций. Так, при размещении одногабаритных элементов размер зоны размещения задается равным (или в соответствии) размерам элементов, а число зон размещения зависит от числа элементов и размеров области размещения. Такая постановка задачи размещения отражает идеологию блочно-иерархического подхода к решению задачи размещения, не исключая при этом возможности использования других методов и подходов.
Что касается показателя качества размещения, то необходимо отметить, с одной стороны, важность как метрических, так и топологических характеристик размещения и, с другой стороны, отсутствие адекватных критериев выбора положения элемента. Подробнее вопрос разработки критерия размещения будет рассмотрен ниже. Здесь же отметим, что в качестве метрической характеристики может быть выбрана суммарная длина связей между размещенными
элементами, т. е.
где li — относительная длина i-й связи, определяемая одним из способов через координаты связываемых ею элементов.
Критерии качества размещения
Отметим, что если размещение в предложенной постановке ориентировано на канальную трассировку, то важной становится характеристика распределения трасс по каналам. Тогда необходимо выбирать критерий, максимизирующий пропускную способность канала:
где—пропускная способность и число пересечений
трассамиj-ro сечения i-го канала соответственно.
Необходимо отметить, что при определении топологических характеристик большую роль играет выбор используемой при решении задачи размещения математической модели КС объекта проектирования (см. гл. 1). Классификация критериев качества по характеру оптимизируемых показателей и процессу оптимизации показана на рис. 3.4.
Частные критерии качества подразделяются на: метрические, топологические и надежностные.
Первые оптимизируют, как правило, длину проводников,
вторые — взаимное расположение элементов соединений,
третьи — надежностные характеристики (тепловую и электромагнитную совместимость и т. п.).
К метрическим критериям относят суммарную длину связей, число соединений, длина которых больше заданной, и т. п.
Топологические критерии становятся первостепенными при проектировании однослойных печатных плат, некоторых ИМС и служат для оптимизации таких параметров, как число пересечений трасс, конфигурация трасс, число соединений между модулями в соседних позициях и т. п. При размещении нерегулярных структур основным критерием является максимальное заполнение монтажного поля элементами (плотность упаковки) при ограничении на их взаимное расположение. Этот критерий важен при проектировании БИС и СБИС.
Задача размещения относится к задачам многоцелевой оптимизации, и важной проблемой является установление единого критерия качества, обеспечивающего оптимальность конструкции по многим параметрам. Известны следующие методы многоцелевой оптимизации.
1. Использование единого функционала. Различают аддитивный и мультипликативный единые функционалы, определяемые по формулам
где ki(н)— значение частного i-го критерия оптимизации (индекс «(н)» — нормированный); лямбдаt— коэффициент значимости (приоритета) /-го частного критерия. При размещении схем критерии некоторым образом противоречивы и оптимизация по одному из них может привести к ухудшению другого критерия. Для совместного учета приведенных критериев рассмотрим обобщающий критерий размещения элементов схем:
где L(G), P(G), Э(G) — управляемые переменные, зависящие от числа элементов, связей, расположения элементов относительно друг друга на плоскости и т. д. Это выражение приводит к задаче оптимизации, решение которой, не являясь оптимальным для L(G), P(G) или Э(G), оказывается приемлемым для Q(G) в целом. Оптимальность Q (G) говорит, например, о том, что дальнейшее уменьшение L(G) невозможно без увеличения P(G) или Э(G) и наоборот. Так как построение алгоритмов по обобщенной оценке затруднительно, объединим заданные критерии в один, т. е. построим аддитивную функцию
Величина лябда i"I={1, 2, ..., l}, характеризует важность одного критерия по сравнению с другими. Данный подход осложняется тем, что весовые коэффициенты обычно выбираются на основании опыта конструкторов и технологов.
2. Выбор основного показателя, основанный на принципе последовательной субоптимизации результатов на каждом из этапов поиска решения. При использовании этого метода необходимо определять важность показателей качества.
3. Параллельная оптимизация по нескольким показателям. Сущность метода состоит в оценке различных вариантов размещения одновременно по всем оптимизируемым параметрам.
Перечисленные методы сводят многокритериальную задачу к однокритериальной, вычислительные методы решения которой хорошо развиты.
Задача размещения может быть отнесена к классу задач, где многокритериальность обусловлена множеством оптимизируемых показателей качества, имеющих различные физическую природу и размерность.
В группе метрических критериев можно выделить критерий суммарной длины связей; это критерий, как показано в [3, 4, 6], интегрально учитывает (с определенной степенью) остальные метрические критерии.
Рассмотрим более подробно топологические критерии, способствующие выполнению трассировки на полученном варианте размещения элементов. Основным фактором, определяющим качество трассировки для ОП с числом слоев больше 2, где могут быть реализованы трассы, является степень (коэффициент) загруженности областей монтажного поля, отведенных под проведение трасс, В случае регуляризованной структуры размещения элементов эти области носят название каналов. Необходимо отметить, что без проведения непосредственно трассировки оценка загруженности каналов затруднена и следует использовать вероятностный подход при вычислении указанных оценок. Ниже предлагается показатель качества размещения, основанный на оценке равномерности загруженности как отдельного канала, так и их совокупности. Рассмотрение будем вести при следующих допущениях и предположениях.
1. Оценка производится по числу трасс, пересекающих каждое сечение каждого канала.
2. Сечения представляют собой отрезки, образованные при пересечении каналов (вертикальных и горизонтальных).
3. Трасса может быть реализована в площади прямоугольника, построенного на концах этой цепи.
4. Трасса может пересекать любое сечение в пределах описанного прямоугольника не более одного раза.
Рассмотрим теперь модель монтажного поля с заданным вариантом размещения (рис. 3.5). Здесь заштрихованы зоны размещения элементов; штриховыми линиями показаны сечения вертикальных каналов. Не теряя общности рассуждений, рассмотрим способ оценки загруженности вертикальных каналов (он автоматически распространим и на горизонтальные каналы).
где sfip, tip, si^, ti^—абсциссы и ординаты правого верхнего и левого нижнего контактов соответственно; аi,-— указатель ориентации элемента et.
Тогда число вертикальных каналов Kв* = (q— 1). Если граничная зона используется как канал, то
При этом условии ширина канала (вертикального)
Считая каналы одинаковыми по ширине, определяем начальную пропускную способность канала:
Величина Woпоказывает максимальное реализуемое (конструктивно) число трасс, которые могут пересечь любое сечение каждого
где WijT=kT— число трасс, пересекающих j-e сечение /-го канала; Pij— вероятность распределения трасс в j-e сечение /-го канала:
где g—число слоев, в которых могут быть проведены соединения; — число сечений каналов, попадающих в площадь зоны
реализации цепи l; qijl— сечения, пересекаемые трассой l; Pijl— вероятность пересечения трассой l 7-го сечения /-го канала;
Pijt—суммарная плотность вероятности прохождения трасс через j-e сечение /-го канала.
В последнее время начато использование вероятностных и прогнозирующих методов оценки качества размещения, позволяющих априори оценить качество последующего этапа — трассировки межсоединений, т. е. определить процент автоматически неразводимых соединений, что является основным (а иногда и единственным) показателем работы всей САПР. В некоторых случаях вероятность получения «хорошей» трассировки связывают с оценкой плотности равномерности распределения цепей на монтажно-коммутационном поле. Недостатком данного подхода является учет всего одного показателя качества, на основе которого осуществляется прогнозирование.
Для прогнозирования сложных ситуаций используют метод, основанный на декомпозиции проблемы и оценке вероятности простых событий на уровне, позволяющем провести эту оценку. Рассмотрим применение указанного подхода к прогнозированию возможностей трассировки после получения некоторого варианта размещения. Очевидно, что прогнозируемое событие — «хорошая» трассировка — зависит от наиболее полного выполнения некоторой совокупности частных показателей качества размещения. Рассмотрим выполнение требований, поставленных некоторым i-м частным критерием размещения. Если Kmax(Kmin)— максимальное (минимальное) значение оптимальной оценки данного критерия, то под степенью приближения к оптимальной оценке будем понимать величину
где К1r— реальная оценка по критерию, i для данного варианта размещения.
Степень приближения обобщающих групповых критериев — метрического (Км) и топологического (КT) — можно определить, используя мультипликативную свертку по степеням приближения частных критериев. При этом считаем, что важность (приоритет) частных критериев в группе одинакова. Тогда
Необходимо отметить, что условия, в которых будет проходить трассировка, определяются в основном топологией полученного варианта размещения, в то время как метрические характеристики влияют в большей степени на работоспособность схемы. Тогда оценку возможностей трассировки для данного варианта размещения можно провести, используя величину
где а — коэффициент значимости группы метрических критериев.
Приведенные рассуждения могут быть проиллюстрированы деревом целей (рис. 3.6). Корень дерева («нулевой» уровень) соответствует окончательной оценке возможностей трассировки. Уровень I дерева соответствует выполнению обобщающих групповых метрического и топологического критериев, а уровень II показывает степень выполнения частных критериев оптимизации размещения. Дальнейшее построение дерева необходимо, если на уровне II невозможно получить оценку степени приближения к оптимальной. Разбиение производится по соответствующей ветви дерева целей до уровня п, удобного для оценки. Очевидно, что чем ближе значение Отрк единице, тем лучшую трассировку можно получить. Достоинство предложенного метода прогнозирования возможностей трассировки, основанного на использовании дерева целей, состоит в том, что его реализация позволяет оценить качество размещения, прогнозируя возможности трассировки без ее проведения, и учесть при этом большинство выдвигаемых при проектировании на этапе размещения требований.
Известны методы определения оптимальных оценок по следующим показателям качества размещения:
а) метрическим (суммарная длина связей; длина самой длинной связи; площадь монтажного поля, необходимая для размещения элементов и др.);
б) топологическим (число цепей простой конфигурации; число соединений между элементами, находящимися в соседних позициях; число пересечений соединений; число межслойных переходов и др.).
Интерес представляют случаи, когда минимальная оценка по некоторому показателю качества стремится к нулю. Тогда в качестве минимальной оценки можно выбирать единицу измерения по данному показателю качества размещения.
канала. Если через сечение j канала i проведено к трасс, то его текущая пропускная способность WijT = kT. Под остаточной пропускной способностью канала Wij0 в сечении будем понимать величину
При реализации основных алгоритмов в общем случае могут получаться локальные минимумы. Поэтому представляют интерес оценки суммарной длины и числа пересечений для ММ КС с данными числами вершин и ребер.
Приведем оценку минимальной суммарной длины ребер графа. Пусть дан произвольный граф G = (X, U), причем |Х| = п, |U|=m и задана решетка Grс шагом, равным единице, число узлов которой больше или равно т. Тогда ребра графа G будут иметь вес 1, 2, ..., N (N—вес наиболее длинного ребра графа).
Вес любого ребра однозначно определяется матрицей геометрии. Если Grимеет размерыВведем понятие стандартного графа графа G = {X. U), отображенного в решетку. Граф имеет . Основная идея нахождения нижней оценки суммарной длины ребер произвольного графа заключается в следующем. Сначала подсчитываем число вершин и оебер графа G. Далее в решетке строится стандартный граф имеющий такое же число вершин и ребер, как и граф G. построение ведется последовательным наслоением в решетку сначала всех ребер графа GA, вес которых равен единице. Если число единичных ребер графа GA равно или больше числа ребер графа G, то процесс построения заканчивается. В противном случае последовательно добавляем ребра с весом 2, 3 и т. д. до тех пор, пока общее число ребер графа GA не станет равным числу ребер графаG. Подсчитав суммарную длину ребер GA, равную
где Сi; — число ребер с весом i, получим оценку минимальной суммарной длины для графа G и для любых графов с таким же числом вершин и ребер, аналогичным образом отображенных в заданную решетку. Граф CA в общем случае не изоморфен графу G. Из приведенных рассуждений справедлива следующая теорема.
Теорема 3.1. Минимальная суммарная длина всех произвольных графов с п вершинами и т ребрами не может быть меньше суммарной длины ребер соответствующего стандартного графа GA.
Доказательство теоремы следует из построения стандартного графа.
3.3. РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ НА ОСНОВЕ ПОИСКА МЕДИАНЫ ГРАФА
Разногабаритный элемент; площадь монтажного поля; линейка; бинарный поиск; медиана графа
Как показал анализ применяемых в настоящее время в САПР методов размещения, перспективными направлениями повышения эффективности использования математического обеспечения при решении задачи размещения являются следующие.
1. Формирование структуры процесса размещения на основе блочно-иерархического подхода.
2. Использование для исследования математических моделей объектов проектирования поисковых методов отыскания решения по заданному критерию.
3. Универсализация применяемого алгоритма размещения. Это предполагает наличие развитого аппарата управления формированием алгоритма решения, а также разработку необходимого минимального набора модулей для формирования алгоритмов, направленных на проектирование различных объектов.
В соответствии с принятой идеологией блочно-иерархического подхода структура процесса решения задачи размещения будет иметь вид, показанный на рис. 3.7, и включает в себя следующие основные операции:
формирование групп элементов (в дальнейшем будем называть эти группы блоками);
размещение блоков на монтажном поле;
размещение элементов каждого блока.
Очевидно, что на каждой из операций целесообразно (а иногда и необходимо) использование своего показателя качества решения. Кроме того, требования могут различаться в зависимости от конструктивно-технологических особенностей объекта проектирования.
Рассмотрим подробно выполнение основных операций.
1. Формирование блоков на множестве одногабаритных элементов.
При решении задачи формирования блоков необходимо определить состав блоков, схему соединений внутри блока и схему межблочных соединений. При этом задача формирования блоков сводится к задаче разбиения ММ КС. Отметим особенности процесса разбиения, возникающие при формировании блоков. Очевидно, что цель разбиения (формирование блоков) должна учитывать требования и условия выполнения последующих этапов проектирования—размещения элементов и трассировки соединений. Для этого можно использовать алгоритмы, описанные в гл. 2.
С точки зрения размещения необходимо элементы, имеющие связи с разъемами, располагать вблизи них; тогда на задачу разбиения графа, моделирующего схему, можно наложить ограничения. Множество элементов X', имеющих связи с разъемами, подлежит фиксированному разбиению (т. е. элементы этого множества образуют блок, расположенный в непосредственной близости от разъема и параллельно ему). Назовем элементы xteX' внешними. Тогда процесс разбиения на блоки будет основан на выделении и первоначальном закреплении внешних элементов в блоки.
С точки зрения трассировки приведенный выше критерий минимума межблочных соединений не всегда эффективен вследствие возможной перегрузки отдельных каналов. В этой связи интерес представляют критерии, выравнивающие мощности межблочных связей:
где |Xi| — мощность i-го блока; k'ij, kij0—число внутренних и внешних связей /-го блока соответственно.
Структурная схема процесса формирования блоков на множестве одногабаритных элементов будет иметь вид, показанный на рис. 3.8.
2. Формирование блоков на множестве разногабаритных элементов.
При разбиении КС на блоки, компонентами которой являются разногабаритные элементы, возникает ряд ограничений на использование приведенной выше схемы формирования блоков, обусловленных как самим фактором разброса геометрических размеров, так и количественной оценкой разброса. В том случае, когда элементы одинаковы (или близки по одному из размеров, например по ширине), задача формирования блоков сводится к:
а) отысканию размеров блока;
б) распределению элементов в блоки при соблюдении условия, что сумма размеров (т. е. длин) элементов в блоке не превысит длины блока.
Ширину блока можно определить исходя из следующих соображений. Пусть монтажное поле имеет форму прямоугольника с размерами АхВ, а множество элементов
где аi-—одинаковый для всех элементов размер; аi = аj=а; bi—второй размер каждого i-го элемента.
Тогда площадь монтажного поля, занятую непосредственно блоками, можно определить как
где SБ—площадь монтажного поля, занятая блоками; ST-площадь монтажного поля, отводимого под каналы для трассировки соединений и запретные технологические области.
С другой стороны, площадь, занимаемая блоками, если p(не=)п,
где—ширина блока, одинаковая для всех блоков; bt—длина
/-го элемента; —длина блока. Тогда
где as — коэффициент, и необходимо строгое выполнение условия аб>=a, где а— наибольший размер.
Невыполнение последнего условия требует расширения размеров монтажного поля либо перекомпоновки схемы узла, подлежащего проектированию. Если же это условие выполняется, то процедура, применяемая в этом случае для формирования блоков, аналогична процедуре, используемой при формировании блоков на множестве одногабаритных элементов, т. е.
где bj — размер ранее распределенного в блок Хjэлемента хj. Структурная схема процесса формирования блоков показана на рис. 3.9.
Более сложные проблемы возникают при формировании блоков на множестве разногабаритных элементов кратных размеров. Задача при этом состоит в следующем.
1. Выделение минимального числа типоразмеров, такое, что любой типоразмер обладает коэффициентом кратности по отношению к меньшему (основному) типоразмеру; выделенный набор типоразмеров позволяет «покрыть» любой из элементов схемы.
2. Определение ширины блока. Задача эта затруднена вследствие возможности получения блоков разной ширины. При принятии за ширину блока одного из размеров максимального типоразмера коэффициент использования площади монтажного поля резко падает, однако при ориентации на канальную структуру монтажного поля этот подход представляется единственно возможным.
3. Формирование блоков по типоразмерам. Выделение типоразмеров, набором которых покрывается заданная схема, является сложно разрешимой задачей, так как стандартизация корпусов микросхем определяет зависимость их размеров от числа выводов (по длине) и характеризуется сильным разбросом параметров по ширине. При этом под длиной корпуса понимается сторона корпуса, по которой расположены выводы элемента. Обычно выделяют четыре основных типоразмера для элементов: 1-й для 14- и 16-выводных интегральных схем и дискретных элементов (электрохимические конденсаторы, резисторы, транзисторы и т. д.); 2-й и 3-й — для интегральных схем, имеющих 24 вывода, дискретных элементов и их групп (эти типоразмеры по отношению к первому имеют коэффициент кратности 2 и отличаются ориентацией, т. е. расположением выводов); 4-й — для интегральных микросхем, имеющих 48 выводов, крупногабаритных дискретных элементов (этот типоразмер по отношению к первому имеет коэффициент кратности 4). На рис. 3.10 показаны типоразмеры разногабаритных элементов (РГЭ). В случае использования описанных типоразмеров ширина блока определяется по габаритам четвертого типоразмера, а монтажное поле формируется по габаритам первого типоразмера (рис. 3.11). На первом этапе формирования блоков
происходит выбор внешних элементов и расчет ширины блока. Затем осуществляется анализ свободной зоны блока в пределах используемого на данном шаге наибольшего типоразмера. Из множества элементов-кандидатов в данный блок выбирается элемент на основе критерия К1или К2. Занятые позиции блока в дальнейшем рассмотрении не участвуют. Анализ показывает, что применение такого метода формирования блоков (рис. 3.12) коэффициент использования площади as>=0,7. Отметим, что задача формирования блоков на множестве РГЭ кратных размеров в значительной степени определяется числом возможных типоразмеров элементов.
Рассмотренные выше способы формирования блоков относятся к формированию горизонтальных блоков. Процедуру эту можно применить и для формирования вертикальных блоков на множестве одногабаритных элементов; для разногабаритных элементов эта процедура неприменима. Результатом работы на данном этапе являются состав и структура горизонтальных блоков, число связей внутри блока и между блоками. Исходной информацией для данного этапа являются матрица цепей, размер монтажного поля и элементов, список фиксированных в заданных блоках элементов.
Временную сложность алгоритма формирования блоков оценивают величиной О (n)... O(тп), где п — число элементов, из множества которых формируются блоки; т — число блоков.
Исходной информацией при решении задачи размещения блоков на монтажном поле является (как указано выше) результат работы на этапе формирования блоков, а также характеристики связности элементов (т. е. матрица цепей).
Рассматривая каждый блок как метрическую точку, моделируемую вершиной мультиграфа GM = (X, U), где X—множество блоков; U—множество связей между блоками, и учитывая, что геометрические размеры блоков находятся в соответствии с размерами монтажного поля, можно заметить, что задача размещения блоков практически полностью совпадает с задачей
размещения элементов в линейке позиций. Реализация задачи размещения элементов в линейке выглядит следующим образом.
1°. На основании структуры и состава блоков формируется матрица взвешенных покрывающих деревьев схемы (матрица связности, где цепи заменены покрывающими деревьями).
2°. Выбирается элемент, имеющий максимальное число связей, и устанавливается как начальный (или корневой) элемент.
3°. Выбирается элемент, имеющий максимальное число связей с выделенными элементами. Если таких элементов (кроме начального) нет, элемент присоединяется к корневому справа (или слева). В случае, если присутствуют выделенные элементы, определяется число связей с элементами справа и слева от корневого. Элемент фиксируется с той стороны списка выделенных элементов (относительно корневого), где число связей наибольшее.
4°. Если все элементы фиксированы в списке выделенных, то переход к 5°, в противном случае — к 3°.
5°. На основании списка фиксации элементов производится их последовательное, начиная с левого, закрепление в позициях линейки.
6°. На основании распределения блоков на монтажном поле формируется матрица первоначального размещения.
Структура процедуры формирования списка фиксации элементов и размещения блоков графа (рис. 3.13) на монтажном поле согласно алгоритму показана на рис. 3.14, 3.15.
При формировании списка фиксации применена схема бинарного поиска, базирующаяся на процедуре лексикографического упорядочения. Отметим, что бинарный поиск предусматривает выделение от одной вершины дерева поиска i-го уровня не более двух вершин (|+ 1)-го уровня; под лексикографическим упорядочиванием понимается способ исследования (построения) бинарного дерева, а именно: пойти в симметричном порядке левое (относительно корня) поддерево; посетить корень; пройти в симметричном порядке правое поддерево. Сложность процедуры размещения блоков оценивается величиной O(mlog(m)), где т— число блоков.
Этап линейного размещения элементов в зоне блока — т. е. определение координат элемента на монтажном поле — является важным при реализации блочно-иерархического подхода, и существуют различные подходы к решению этой проблемы. Часто местоположение групп и отдельных элементов определяется с использованием процедуры сканирующей области. При этом на каждой итерации осуществляется перекрытие некоторой области монтажного поля, содержащей заданное число посадочных мест. Область сканирования перемещается по исследуемой плоскости монтажного поля в соответствии с заданным законом перемещения. Однако точность метода зависит от размерности области сканирования, применяемой метрики и стратегии сканирования. Часто сформированные блоки (вертикальные и горизонтальные) переставляются: сначала вертикальные, затем горизонтальные; процедура перестановки повторяется несколько раз попеременно для вертикальных и горизонтальных блоков. Рассмотрим алгоритм, реализующий этап линейного размещения элементов, основанный на выделении обобщенной медианы графа, моделирующего КС.
Пусть КС моделируется графом G = (X, U), причем цепи схемы заменены покрывающими деревьями. Если известна матрица расстояний между вершинами графа, то под медианой графа понимают вершину xteX, такую, что
d(xt, Xj) — элемент матрицы расстояний D графа G; cij— элемент матрицы связности графа G. При этом вершину jдля
которой, называют прикрепленной к вер-
шине х,.
Рассмотрим в качестве модели монтажно-коммутационного поля граф Gr(ортогональную решетку). Отметим также, что элементы, входящие в блок ХiеХ, размещаются на одной линейке решетки графа Gr. Будем считать, что часть элементов уже размещена в пределах принадлежности сформированному блоку. Неразмещенные элементы могут быть фиксированы в свободных позициях блока, которому они принадлежат.
Таким образом, в соответствии с приведенными определениями р-позиция представляет собой подмножество позиций, при помещении в любую из которых элемента xi,- суммарная длина связей полученного частичного размещения увеличивается на величину
где Рkm— подмножество медианных позиций (р-позиция); Рт— подмножество немедианных позиций; Рm* подмножество позиций, принадлежность любой из которых к одному из первых двух подмножеств пока не определена.
Нижняя граница стоимости решения для некоторого найденного частичного решения может быть найдена следующим способом:
где d1— меньшее из расстояний от позиции в блоке т, в которую помещен размещаемый элемент, до позиций с ранее размещенными элементами; d2— сумма расстояний от позиций блока т до позиций с ранее размещенными элементами; п — число вершин моделирующего графа (позиций блока т), которые могут стать медианными.
Опишем алгоритм формирования К-позиции:
1. Задается мощность K-позиции и определяется мощность множества немедианных позиций. Последняя равна мощности множества занятых ранее позиций.
2°. Элементы исследуемого блока «снимаются» со своих позиций в зоне блока (это не касается базовых элементов). Очередность элементов-кандидатов на размещение определяется по убыванию локальной степени вершин моделирующего графа, характеризующих число связей элемента-кандидата с ранее размещенными элементами.
3°. С помощью приведенных выше формул определяется нижняя граница стоимости решения для выбранного элемента.
4°. Исследуются поочередно свободные позиции. При этом оценивается длина связей размещаемого элемента с размещенными.
5°. Каждая последующая вершина (позиция), имеющая оценку длины связей, сравнивается с предыдущей исследованной вершиной и в зависимости от результата сравнения оценок заносится либо в множество медианных вершин (позиций), либо в множество оставшихся вершин (позиций).
6°. Если все позиции просмотрены, происходит переформирование множеств Р', Рkm, Рm-, Рm*Найденные позиции заносятся в состав K-позиции. Если мощность K-позиции меньше заданной, то переход к 3°.
7°. Если K-позиция сформирована для очередного элемента и есть неисследованные элементы, то переход к 2°.
8°. Если для всех элементов блока определены K-позиции, то конец работы алгоритма.
Пример реализации процедуры поиска медианных позиций при размещении элементов показан на рис. 3.16—3.19. На рис. 3.16 и 3.17 показаны КС и граф, моделирующий схему. На рис. 3.18 приведен фрагмент монтажного поля. Элементы схемы помещены в блоки; элементы xlx2, ..., х5размещены в позициях блока тх\ элемент х6, для которого необходимо отыскать множество медианных позиций (/^-позицию), подлежит размещению в зоне блока т2пока свободной от размещенных элементов. Выделенные ранее для формирования
Тогда размещение любого элемента xtв позицию обеспечивает в конечном итоге минимум суммарной длинысвязей. Поиск p-позиции сводится к решению задач целочисленного программирования. Можно для решения этой задачи использовать дерево направленного бинарного поиска. Процедура поиска в этом случае сводится к исследованию множества свободных позиций Р"тв блоке т. Множество свободных позиций разбивается на три подмножества:
блоков внешние элементы (на рисунке заштрихованы) не рассматриваются. На рис. 3.19 показано дерево поиска решения. Результат работы алгоритма — определение Аппозиции для элемента х6:
Приведенный алгоритм поиска K-позиции имеет ВСА, оцениваемую как О(п)... ...О(п2).
Если размещение не учитывает топологических условий, мощность K-позиции равна единице. В противном случае осуществляется исследование возможных мест установки элемента, принадлежащих найденной K-позиции, по заданному топологическому критерию и элемент помещается в наилучшую с точки зрения данного критерия позицию. Необходимо отметить, что каждый элемент (речь идет об элементах, имеющих двухрядное расположение выводов) исследуется при двух возможных ориентациях его на монтажном поле.
Приведем теперь комплексный алгоритм размещения элементов ЭВА на монтажном поле на основе использования поисковых процедур, принимая во внимание общую структуру и идеологию блочного подхода и описание отдельных этапов. Логическая схема алгоритма имеет вид
где Ао, Ак— операторы начала и конца алгоритма соответственно; А1—оператор поиска и распределения внешних элементов; А2— оператор формирования блоков: A2 = A2lv(A22vA23); A2l, А22, А23— операторы формирования блоков для одногабаритных и разногабаритных элементов первой и второй групп геометрии соответственно; А3— оператор размещения блоков; А4— оператор
установки ориентации элементов; А5— оператор формирования ^-позиции для очередного размещаемого элемента; А6— оператор выбора места окончательной установки элемента по топологическому критерию; А7— оператор прогнозирования трассировки по результатам размещения элементов; А8— оператор формирования и вывода конструкторской документации по варианту размещения; Pi—условие проверки условия размещения блоков; если все блоки размещены, то переход к АА; р2— условие проверки элемента в различных ориентациях. Если все ориентации проверены (р2=1) то переход к А6; р3— условие проверки просмотра всех элементов блока. Если все элементы блока размещены, то переход к р4; р4— условие проверки просмотра блоков. Если все блоки просмотрены (т. е. все элементы схемы размещены), то переход к А7, в противном случае — к А4.
Алгоритм размещения позволяет обрабатывать объекты, структура которых представлена одногабаритными и разногабаритными элементами, и ориентирован на канальную трассировку.
3.4. АЛГОРИТМ РАЗМЕЩЕНИЯ ГРАФА СХЕМЫ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ
Подстановка; стандартный граф; фиксация вершин; фрагмент цепи; перестановка групп вершин; факторизация графа
Рассмотрим алгоритм линейного размещения конструктивных элементов на плоскости с минимизацией суммарной длины соединений, в основу которого положен метод ветвей и границ. Пусть задан граф Gr, в котором число столбцов равно числу вершин размещаемого графа КС G = (X, U), а число строк равно единице. Задача состоит в отображении вершин графа в ячейки графа решетки Grс оптимизацией критерия суммарной длины ребер, т. е. в нахождении подстановки, где 1, 2, ..., п — номер позиций решетки; xi(i=l, 2, ..., п) — вершины размещаемого графа. Видно, что таких подстановок п\.
Для эффективного решения задачи линейного размещения методом ветвей и границ необходимо: а) выбрать метод нахождения нижней границы суммарной длины ребер графа; б) определить метод ветвления дерева решений, позволяющий отсекать ветви, содержащие заведомо непригодные решения. Для определения нижней границы суммарной длины L(G) ребер графа G воспользуемся понятием стандартного графа GA.
Для разбиения множества решений Q на подмножества, т. е. ветвления дерева решений, будем фиксировать некоторые вершины в определенных позициях решетки. Если, например, зафиксировать
тика существующих методов размещения, которая позволит студентам выбирать и самостоятельно разрабатывать конкретные алгоритмы.
Рассмотрены модель задачи размещения и выбор целевой функции. Описаны конкретные алгоритмы размещения элементов на основе поиска медиан графа, линейного размещения методом ветвей и границ, размещения с совместной оптимизацией монтажно-коммутационных и тепловых характеристик.
В настоящее время для решения задач проектирования СБИС необходимы конструктивные алгоритмы с ВСА О(п). Перспективной является разработка различного рода поисковых процедур. Важнейшая проблема — совместная оптимизация при размещении и компоновке, а также размещение по многоцелевому критерию.
Основная цель раздела — познакомить с конкретными алгоритмами размещения, а также научить строить любые математические модели размещения и на их основе разрабатывать поисковые, точные, итерационные и другие алгоритмы размещения элементов КС ЭВА.
Задача размещения элементов коммутационных схем сводится к отображению математической модели в координатную решетку.
АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ СОЕДИНЕНИЙ МОДУЛЕЙ РЭС
Трассировка соединений является, как правило, заключительным этапом конструкторского проектирования РЭС и состоит в определении линий, соединяющих эквипотенциальные контакты элементов, и компонентов, составляющих проектируемое устройство.
Задача трассировки — одна из наиболее трудоемких в общей проблеме автоматизации проектирования РЭС. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачи применяются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка — наисложнейшая задача выбора из огромного числа вариантов оптимального решения.
Одновременная оптимизация всех соединений при трассировке за счет перебора всех вариантов в настоящее время невозможна. Поэтому разрабатываются в основном локально оптимальные методы трассировки, когда трасса оптимальна лишь на данном шаге при наличии ранее проведенных соединений.
Основная задача трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости (плате, ТЭЗ, кристалле и т. п.), чтобы реализовать заданные электрические соединения с учетом заранее заданных ограничений. Основными являются ограничения на ширину проводников и минимальные расстояния между ними.
Исходной информацией для решения задачи трассировки соединений обычно являются список цепей, параметры конструкции элементов и коммутационного поля, а также данные по размещению элементов.
Критериями трассировки могут быть процент реализованных соединений, суммарная длина проводников, число пересечений проводников, число монтажных слоев, число межслойных переходов, равномерность распределения проводников, минимальная область трассировки и т. д. Часто эти критерии являются взаимоисключающими, поэтому оценка качества трассировки ведется по доминирующему критерию при выполнении ограничений по другим критериям либо применяют аддитивную или мультипликативную форму оценочной
функции, например следующего вида: F = Σ λį fi, где F—аддитивный критерий;
λį весовой коэффициент; fi— частный критерий; р — число частных критериев.
Задача трассировки всегда имеет топологический и метрический аспекты. Топологический аспект связан с выбором допустимого пространственного расположения отдельных фрагментов соединений без фиксации их конкретного месторасположения при ограничениях на число пересечений и слоев и т. п. Метрический аспект предполагает учет конструктивных размеров элементов,
соединений и коммутационного поля, а также метрических ограничений на трассировку.
В известных алгоритмических методах решения задачи трассировки метрический аспект присутствует всегда, а топологический— в большей или меньшей степени. Все существующие методы трассировки можно подразделить на две большие группы: последовательные и параллельные.
В последовательных методах трассы проводят одну за другой последовательно, при этом проведение какой-либо трассы а на (i— 1)-м шаге может затруднить проведение трассы bна i-м шаге, так как является препятствием для проведения трассы b. Следовательно, особенно актуальным для последовательных алгоритмов трассировки является предварительное ранжирование (упорядочение) соединений до трассировки.
Существуют различные стратегии упорядочения, основанные, в частности, на длине соединений, степени охвата соединением других соединений и др. Однако объективных оценок эффективности таких методик в настоящее время нет, поэтому наиболее разумными представляются использование нескольких вариантов очередности и выбор из них наилучшего.
Задачу трассировки можно условно представить в виде четырех последовательно выполняемых этапов:
определение перечня соединений;
размещение по слоям;
определение порядка соединений;
трассировка проводников.
На первом этапе формируется точный список, указывающий, какие соединения (цепи или фрагменты цепей схемы) должны быть проведены.
На втором этапе предпринимается попытка точно решить, где каждое соединение может располагаться.
На третьем этапе определяется порядок соединений для каждого слоя,
т. е. указывается, когда каждый проводник, помещенный в этот слой, будет проведен.
На четвертом этапе дается ответ, каким образом должно быть проведено каждое соединение.
Рассмотрим указанные этапы подробнее.
Исходная информация для первого этапа — это перечень соединений контактов каждого элемента с контактами других элементов. Одиночные контактные соединения записываются непосредственно в перечень соединений (матрицу цепей или список). Трудность при реализации возникает тогда, когда один контакт необходимо соединить с несколькими контактами. Для решения этого вопроса используют алгоритмы построения кратчайших покрывающих деревьев Прима или Штейнера. На этом этапе ЭВМ не производит соединений, она только решает, какие проводники должны быть оттрассированы.
При определении перечня соединений необходимо также решать вопросы распределения контактов элементов по контактам разъема. Часто на практике пытаются исключить пересечение при проведении прямых линий между контактами элементов и соответствующими им контактами разъема. При трассировке многие элементы имеют логически эквивалентные контакты. Поэтому для упрощения трассировки просматривают проводники, подходящие к таким контактам, и при необходимости заменяют их друг на друга. Правило при замене проводников обычно заключается в исключении пересечений прямых линий.
На втором этапе решается задача размещения проводников по слоям. Она сводится к построению плоской укладки графа коммутационной схемы (КС). Окончательный вариант размещения по слоям можно улучшить, если проанализировать каждый проводник.
На третьем этапе производится исследование каждого слоя с целью точного определения момента, когда можно будет трассировать каждый проводник, другими словами — определить порядок обработки проводников в каждом слое. Для двух проводников существует правило выбора: если контакт В появляется в прямоугольнике А, т. е. в прямоугольнике, имеющем в противоположных углах контакты проводника, то проводник В надо трассировать первым. К сожалению, не всегда это правило применимо. Сформулируем общее эвристическое правило Айкерса о порядке трассировки проводников. Проводники трассируются в порядке приоритетных номеров. Приоритетный номер проводника V равен числу контактов в прямоугольнике W. На практике обычно короткие горизонтальные и вертикальные отрезки проводников трассируются первыми, далее трассируются окружающие их почти вертикальные и горизонтальные проводники. В заключение трассируются длинные соединения, которые по отношению к другим чаще располагаются с внешней стороны.
Обычно проблему размещения соединений по слоям рассматривают как задачу раскраски специального графа. Далее производится исследование каждого слоя с целью определения порядка обработки соединений внутри каждого слоя. После того как все соединения распределены по слоям и определен порядок их обработки, решается задача трассировки фрагментов всех цепей, что и выполняется на четвертом этапе.
Четвертый этап трассировки является основным, наиболее трудоемким, определяющим эффективность и качество всей задачи трассировки. На рис. 4.1 приведена классификация алгоритмов трассировки этого этапа.
К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число модификаций волнового алгоритма, предложенного Ли еще в 1961 г., однако все они сохраняют его основной недостаток: большие объемы вычислений и памяти ЭВМ. Временная сложность волнового алгоритма составляет O(MN), где N—число клеток ДРП; М — число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом клеток не более 105, при этом время трассировки составляет несколько часов работы ЭВМ. Число неразведенных трасс обычно не превышает 10%.
Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свободными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритмы обычно обеспечивают разводку около 80% соединений.
Эвристические алгоритмы трассировки эффективны, как правило, только на начальных стадиях трассировки, когда на плоскости мало преград. Основная идея состоит в генерации самых длинных незанятых отрезков в направлении цели с эвристическими приемами обхода препятствий.
В параллельных алгоритмах трассировки в начале определяется допустимое взаимное расположение трасс, которое оптимизируется по выбранному критерию, и лишь потом трассы фиксируются на коммутационном поле.
Канальные алгоритмы основаны на возможности в некоторых случаях регулярного разбиения коммутируемого поля (КП) на каналы и трассировки внутри каналов вертикальными и горизонтальными отрезками. Алгоритмы работают быстро, однако для них актуальна проблема качества получаемых решений. Отметим, что канальным алгоритмом свойствен иерархический подход к трассировке, когда исходная задача декомпозируется на несколько подзадач. При этом на каждом иерархическом уровне в зависимости от его специфики целесообразно применение различных методов трассировки.
В алгоритмах гибкой трассировки на первом этапе строятся модели топологии для трасс цепей на дискретном топологическом рабочем поле (ДТРП) (без жесткой фиксации), а на втором этапе — модели геометрии, которые метрически точно определяют конфигурацию и месторасположение каждой трассы на КП.
В графотеоретических методах используют графовые модели элементов и компонентов схем, на основе которых синтезируется топологический эскиз проектируемого устройства. На следующем этапе решается задача метризации топологического эскиза.
Рассмотрим модели КП для указанных алгоритмов трассировки. Для волновых и лабиринтных методов используется ДРП следующего вида.
Пусть задана прямоугольная система координат SOT (рис. 4.2) на КП и выбраны единицы измерения hsи htсоответственно вдоль осей OS к ОТ. Проведем через точки осей с координатами ahsи aht, где а=1, 2, ..., прямые, параллельные осям координат. Тогда плоскость КП может быть разбита на элементарные прямоугольные ячейки размером hsxht, а прямые разбиения образуют координатную сетку с шагом hsпо оси OS и шагом htпо оси ОТ. Совокупность элементарных ячеек, на которые разбивается КП, называется ДРП. Значения hsи htвыбираются в зависимости от площади КП, допустимой плотности расположения выводов элементов и проводников.
Модель КП для канальных и эвристических алгоритмов, так же как и в предыдущем случае, разбивается на прямоугольные области, называемые каналами, но в отличие от предыдущей модели разбиение определяется расположением выводов элементов. Если элементы однотипны и размещены на плоскости регулярно, то разбиение на каналы также будет регулярным, в противном случае — нерегулярным (рис. 4.3, a, б).
Длина стороны любого канала, параллельной преимущественному направлению трасс на слое, называется длиной этого канала, а длина другой стороны — его шириной. Число трасс, которые могут пересечь боковую границу канала, называется пропускной способностью канала.
Регулярное разбиение КП на прямоугольники не вызывает затруднений. Нерегулярное разбиение несколько сложнее. Желательно, чтобы прямоугольников разбиения было как можно меньше, так как при этом уменьшается время трассировки, а также размеры таблиц для представления данных.
Для описания топологии трасс в методах гибкой трассировки строится ДТРП. Ее можно представить в виде графа Gr = (Xr, Ur), где Хrсоответствует контактам элементов, характерным точкам края платы, внешним контактам, запрещенным зонам; Ur— линиям, соединяющим элементы х Î Хr.
Вообще, дискретами могут быть грани любой конфигурации. При этом ненасыщенные трассами грани могут сжиматься, а те, через которые проходит большое число трасс,— растягиваться.
Приведем математическую формулировку задачи трассировки электрических соединений. Исходными данными являются коммутационная схема (КС), конструкция плоскости, результаты размещения элементов. Будем считать, что все трассы прокладываются в одном слое; КС определяют подмножества непересекающихся множеств контактов координаты которых заданы. Контакты каждого подмножества Срi = Срв КС объединены электрическим соединением, т. е. цепью (см. 1.5). Необходимо соединить контакты цепей таким образом, чтобы фрагменты различных цепей не пересекались и располагались друг от друга на расстоянии не меньше заданного. Математической моделью конструкции является регулярная координатная сетка (граф Gr), соответствующая ДРП. Отметим, что размеры ячеек ДРП обычно определяют площадью, заданной для трассировки плоскости, ограничениями на плотность расположения контактов и соединений. Пусть ячейки ДРП имеют форму квадратов и через каждую ячейку может проходить только одно соединение, где Х3— множество запрещенных для проведения трасс ячеек ДРП. Каждой ячейке ДРП будет соответствовать вершина Тогда любую цепь lt КС можно представить в виде ориентированного дерева (граф КС) с корнем в произвольно выбранной вершине хк(рис. 4.4).
Тогда дерево Тk. можно рассматривать как объединение простых путей (хк, iПричем каждый путь (хк, скr) состоит из дуг Uij = (Xi, Xj), которые соответствуют прохождению трассы из ячейки хi, в соседнюю ячейку Хj
Вводят булевы переменные
Длина цепи будет выражаться числом покрываемых ячеек, т. е. вершин Gr, и определяться как Lk = ΣΣykij + 1,
где— множество ячеек, соседних с i и принадлежащих Xt\ Х3;
пк= |Т|-1 — число вершин дерева.
На основе вышеизложенного критерий трассировки записывают так:
Для каждого пути (хк, скr) обычно задаются следующие ограничения:
из вершины хквыходит только одно ребро, принадлежащее пути;
в каждую вершину хкне должны заходить никакие ребра;
в вершины скrзаходит единственное ребро из пути (хк, ск,r);
в вершинах ск,rнет выходящих ребер;
в любой вершине не должно быть обрыва пути
Для учета требования непересечения различных трасс вводят ограничения
Минимизация критерия L с учетом рассмотренных ограничений может представлять собой ЗЦП, решение которой (см. гл. 1) будет определять трассировку соединений. Заметим, что из-за громоздкости и длительности решения в практических задачах в основном используют эвристические алгоритмы трассировки с минимизацией описанного критерия или его модификаций.
4.2. ТРАССИРОВКА ПРОВОДНЫХ СОЕДИНЕНИЙ
В зависимости от конструктивной реализации связей выделяют трассировку проводных соединений, трассировку печатных соединений, трассировку межсоединений на кристалле БИС. Здесь рассмотрим вопросы трассировки проводных соединений, а также одностороннего, двустороннего и многослойного монтажа на печатных платах.
Среди всех конструктивно-технологических реализаций связей проводной монтаж с точки зрения практического решения задачи трассировки наиболее прост. Объясняется это тем, что проводники изолированы друг от друга и не стоит задачи об ограничениях на пересечения. Поэтому основным критерием трассировки проводных соединений является суммарная длина соединений.
Для проводного монтажа задача трассировки сводится к построению на вершинах графа дерева с минимальной суммарной длиной ребер, при этом вершины графа моделируют соединяемые контакты, а ребра — межсоединения. Единственное ограничение накладывается на максимальную локальную степень вершины, так как технологически целесообразно подсоединять к одному контакту не более определенного конечного числа соединений. Задача построения минимального дерева формулируется следующим образом. Пусть Р = {p1,р2, ..., рп}- множество точек плоскости, соответствующих выводам произвольной цепи. Рассмотрим полный граф Кп=(Х, U), вершины которого хiеХ соответствуют выводам цепи, а ребра ujе U с приписанным к ним весомхарактеризуют соединения между парами выводов. Значениеможет представлять линейную комбинацию нескольких характеристик соединениягде ц,-— весовые коэффициенты; ds— некоторая характеристика соединения иj
Теперь исходная задача сводится к определению в графе G дерева, включающего все вершины хеХ и имеющего минимальный суммарный вес ребер, т. е. КПД (см. 1.2). Решение задачи дано в работах Краскала, Добермана, Уйэнбергера и Прима [3, 4, 6, 12, 22, 38, 44, 59, 65, 70].
Под расстоянием между вершинами графа будем понимать значение мю(Uj), приписанное соответственно ребрам графа. Расстоянием от вершины до изолированного фрагмента будем считать минимум расстояний от отдельных вершин до фрагмента. Алгоритм Прима построения кратчайшего покрывающего дерева или цепи с п выводами может быть описан теперь следующим образом.
1°. Для произвольного вывода цепи найти ближайший и провести соединение.
2°. На каждом последующем шаге 1=2, 3, ..., п из множества неподсоединенных выводов выбрать тот, который находится ближе остальных (в указанном выше смысле) к группе уже связанных выводов, и подсоединить его к этой группе по кратчайшему пути.
Рассмотрим пример. Пусть необходимо соединить цепью эквипотенциальные контакты, обозначенные цифрой 1 на рис. 4.5, а. Для этого примера по шагам рассмотрено решение задачи построения КПД с помощью алгоритма Прима на рис. 4.5,б—д.
Построенное по алгоритму Прима КПД обладает тем свойством, что степень любой вершины не превышает 6. Как правило, при разработке монтажных
схем проводных соединений вводится ограничение на максимальное число соединений, подходящих к одному выводу. Если \<6, то необходимо использовать специальные алгоритмы построения КПД. Для решения такой задачи часто используются алгоритмы, основанные на методе ветвей и границ, однако при анализе большого числа цепей предпочтение отдают эвристическим алгоритмам.
Например, рассмотрим модифицированный алгоритм Прима. Всякая изолированная вершина соединяется с ближайшей, не соединенной с X другими вершинами; всякий изолированный фрагмент соединяется кратчайшим ребром с ближайшей вершиной, не соединенной с X другими вершинами.
В некоторых случаях помимо ограничения на степени вершин задаются начальная и конечная точки цепи. Это имеет место, например, при разработке монтажных схем для высокочастотных цепей, когда необходимо в определенной последовательности связать источник сигнала и несколько нагрузок. Иногда задача сводится к построению кратчайшего пути между двумя заданными выводами, проходящего через все остальные выводы цепи. Данная задача родственна задаче о маршруте коммивояжера, а следуя терминологии теории графов,— это задача построения кратчайшей гамильтоновой цепи между заданными начальной и конечной вершинами.
Рассмотрим алгоритм, дающий приближенное решение этой задачи. Основой алгоритма являются (п — 1)-й шаговый процесс выбора кратчайших ребер в полном графе Кn проверки каждого ребра на выполнение ограничений задачи и составление из выбранных ребер пути, соединяющего заданные точки.
Приведем пример. Пусть задано расположение точек, подлежащих соединению на плате (рис. 4.6,а). Составим упорядоченную по возрастанию длин последовательность ребер полного графа Кn: (1*—3), (1* — 2), (2* — 3), (4—5), (3-4), (3 — 5), (1*—4), (2* —5), (2* —4), (1* — 5). Отметим, что 1* и 2* —соответственно начальная и конечная точки пути.
Очередное ребро i = 1, 2, ..., п-1 выбирается по порядку из этой последовательности при выполнении следующих условий:
1. Ребро не соединяет заданные конечную и начальную точки (1* и 2*).
2. При включении ребра в путь степень вершин, соединяемых этим ребром, не превышает заданной (лямбда = 1 для начальной и конечной точек и Х=2 для остальных точек).
3. Ребро не образует цикла с ребрами, уже включенными в путь.
4. При включении в путь любого ребра (кроме (n-l)-ro) начальная и конечная точки остаются несвязанными.
Условия 1 — 3 непосредственно вытекают из ограничений задачи. Условие 4 препятствует образованию тупиковых ситуаций, когда дальнейшее формирование пути становится невозможным— все подсоединенные точки, кроме начальной и конечной, имеют степень лямбда = 2. Пошаговый процесс формирования пути изображен на рис. 4.6, а — д. Среднее изменение длин монтажных соединений для данного алгоритма по сравнению с оптимальным решением составляет порядка 5%.
Задача построения КПД усложняется, если при соединении множества вершин (контактов цепи) разрешается использование дополнительных точек соединения. В общем виде данная задача формируется так: для заданных xt, x2,..., хпточек плоскости построить КПД с п'>=п вершинами — и называется задачей Штейнера (ЗШ). Обычно решение ЗШ рассматривают в областях прямоугольной конфигурации. Известно, что для п <= 5 известно решение ЗШ, в общем же случае известны условия, которым должны удовлетворять деревья Штейнера (ДШ) и эвристические алгоритмы. Дополнительные точки, вводимые при построении КПД, называют точками Штейнера (ТШ).
Приведем ряд лемм, полученных Фридманом и Меноном, дающих необходимые условия существования и построения ДШ [65 ].
Лемма 4.1.Для п вершин, которые должны быть соединены между собой, всегда можно построить ДШ, в котором каждая ТШ gtсоединена по крайней мере с тремя другими.
Лемма 4.2.Для множества вершин {х1, х2, х3}, которые должны быть соединены, координаты ТШ g, минимизирующей
будут Scp, Тсри справедливо выражение
где Scp, Тср— средние значения St(i = 1, 2, 3) и ti (j=1, 2, 3); P(х1, х2, х3)— длина периметра прямоугольника, построенного на вершинах xl x2, х3; d(g, пi) — прямоугольное расстояние между g и ni.
На рис. 4.7 показан пример, иллюстрирующий условия леммы 4.2 при построении ДШ, соединяющего вершины xt, x2, х3. Точка Штейнера g имеет координаты Sg=3, tg = 5.
Лемма 4.3.Дано ДШ, состоящее из хi,- точек плоскости. Пусть ТШ g соединена только с тремя вершинами xt, x2, х3. Тогда g находится внутри прямоугольника, построенного на точках xi, x2, х3, и ТШ единственна.
Следствие4.1. Для заданного множества вершин xt, x2, х3 ДШ содержит одну ТШ g с координатами (Scp, Tcp), если она не совпадает ни с одной из вершин х2 x2, х3 и суммарная длина ребер ДШ равна
Лемма4.4. Дано ДШ на множестве X={xt, x2, ..., х„}, а ТШ этого дерева образуют множество g = {glt g2, ..., gk} Если gxс g и gEпринадлежит I то gxсодержит элемент g1k, соединенный не менее чем с двумя вершинами из I, в противном случае g1пусто. Здесь I—множество точек пересечения линий координатной сетки.
На основе приведенных лемм сформулирована известная теорема. ■
Теорема 4.1.Дано ДШ на множестве вершин Х = {х1, х2, ..., х„} с множеством ТШ g = {g1 g2, ..., gk} Тогда для этого множества существует такое другое ДШ с множеством ТШ g', что
Из рассмотрения теоремы следует метод определения ДШ на основе полного перебора в качестве ТШ всех возможных подмножеств точек /. Очевидно, что такой метод применим только при построении ДШ для небольшого числа ТШ. В этой связи разрабатываются эвристические процедуры построения квазиминимальных ДШ.