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

Существующие алгоритмы компоновки можно условно разделить на следующие классы: алгоритмы, -основанные на методах исследования операций; последовательные алгоритмы; итерационные алгоритмы; смешанные алгоритмы [23, 26, 31].

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

Идея итерационных методов разбиения графов схемы РЭА заключается в выборе случайного раз-

ритмы проектирования. Существуют и другие формальные модели [23, 26, 31].

Покрытие и компоновка схем РЭА

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

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

Исходными данными для решения компоновки РЭА является электрическая схема соединений, полученная на этапе покрытия, набор конструктивных элементов и ограничения.

Сформулируем постановку задачи компоновки схемы как разбиение графа G = (X, U) на куски, не обязательно графы, Gj = = (Xi, Ui), Xi Q X, UiCU,i / = = {1, 2, /}, причем Ui - подмножество всех тех ребер G, которые инцидентны хотя бы одной вершине из Xi- Совокупность кусков В (G) == = {Gj/i /} называется разбиением графа G, если

(уСг 6 В (G)) (Gi =ifc 0 OGiCG).

(YGi,Gf(iB(G))(GiGj>

>Xif]Xj=0).

Uij = Uj f] Ui и - подмножество ребер, попадающих в сечение между кусками Gj, Gj; \ Uij \ = = kij - число реберного соединения этих кусков Число реберного соединения всех кусков графа

К = 0,5 2 llkii-=1 /=1

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

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

а (Xh)

rh {Gi)-r (Gj), если Xhftxf, Гк (G,)-/-fe (Gj), если Xh(:Xj,

где Tfe (Gj) -число ребер, соединяющих вершину Xh с вершинами куска Gj {Xi, ill); Tft {Gj) - число ребер, соединяющих вершину Jt с вершинами куска Gj == {Xj, Uj). Перестановка двух произвольных вершин Xfi Xi и JC; Xj приводит к уменьшению числа соедини тельных ребер в случаях: а) jtft несмежна с Jtj и выполняется неравенство а {Xfi) -f- а {xi) > 0; б) лг смежна xi и справедливо а {х) -f-+ а {xi) > 2rik.

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

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

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

Размещение элементов схем РЭА

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

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

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

- последовательной оптимизации;

- парных перестановок;

- основанные на комбинаторных методах дискретного [26, 36] программирования.

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

1= 1 /= 1

Если выделить из всего множества элементов на плате элементы El и Ej, то суммарная длина связей этих элементов со всеми остальными выразится как

= 2 (tjflij+rjikjl)-2rijkij. i= 1

При парной перестановке элементов Ei и Ej суммарная длина связей их со всеми остальными элементами станет равной

Таким образом, можно вычислить приращение суммарной длины связей элементов £; и Ej со всеми остальными, полученное при их перестановке:

- X (u-r}t){kit-kjt).

t= 1

На основании анализа матрицы приращений производится перемещение элементов на монтажной плате.

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

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

Трассировка межсоединений схемы РЭА

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

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

Алгоритмы парных перестановок зависят от начального размещения элементов на монтажной плоскости. Работа алгоритма осуществляется итеративно. Если rtj - расстояние между элементами, а kij - число связей между ними, то суммарная длина связей между элементами Ei и Ef будет Rij = iijlij длина связей элемента Ej со всеми остальными

N N N