Файл: opres_2008.doc

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

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

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

Задача размещения

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

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

ОГРАНИЧЕНИЯ: число вершин не должно быть больше числа позиций, (это очевидно).

КРИТЕРИЙ. С критерием всё не так очевидно. Для этой задачи самостоятельного критерия не существует. В данном случае такой критерий опирается на критерий следующего шага трассировки. Удачное размещение (рациональное) существенно улучшает ситуацию при трассировке.

Трассировка

Исходным для этой задачи являются результаты размещения (все вершины расположены на фиксированных позициях).

ОГРАНИЧЕНИЯ: здесь связаны с возможностью и невозможностью проведения трасс (проводников), наличием на поверхности печатных плат (коммутационных полей) запрещённых для прокладки проводников участков поля, возможностью или невозможностью изготовления двусторонних и многослойных печатных плат.

Наиболее распространенные критерии качества трассировки следующие.

КРИТЕРИЙ № 1: минимальная суммарная длина всех проводников.

КРИТЕРИЙ № 2: длина максимального проводника должна быть минимальна.

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

Лекция 5. Алгоритмы решения топологических задач

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

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

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

Рис. 5.1. Примеры представления радиоэлементов на рисунке графа

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

Алгоритм последовательного разбиения

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

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

Рис. 5.2. Разбиение графа  выделяем вершину с максимальной степенью (например, X3).

Выбираем вершины, максимально связанные с уже включёнными в кусок графа G1(1) после первой итерации. Видно, что третья вершина имеет связь с вершинойX₁двумя рёбрами, с вершинойX₂- одним ребром. Следовательно, на второй итерации включаем в подграфG1 вершинуX₁. Включённые в кусокG1(2) вершиныX₃,X₁условно стягиваются в однуX_3,1. Таким образом, образуется кусок графаG1(2) второй итерации. При этом степень полученной вершиныr(X_3,1) равна сумме степеней исходных вершинX₃,X₁без учета числаu₁₂соединительных рёбер между ними:

r(X_3,1) =r(X₃) +r(X₁)2(u₁₂).

В нашем примере r(X_3,1) = 6 + 32·2 = 5.

Находим вершину X₂, максимально связанную с полученной на предыдущем этапе объединённой вершинойX_1,3, включаем ее в подграфG1(3) на третьей итерации, и определяем степень объединенной вершины:

r(X_3,2,1) =r(X₂) +r(X_3,1)2(u_3,1,2) = 5 + 52·2 = 6.

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

Пример решения конкретной задачи

Приведём пример, показывающий, как решать такие задачи с использованием матрицы соединений. Пусть задан граф G, имеющий семь вершин (рис. 5.3). Необходимо разбить его на два куска. В данном случае, очевидно, что граф разбивается на два кускаG1 иG2 в которых, соответственно, три и четыре вершины. Однако при решении реальных топологических задач, это редко бывает очевидным.

Рис. 5.3. Исходный граф для задачи разбиения

Итак, разбиение будем проводить по матрице соединений (рис. 5.4), на которой отобразим рассмотренный алгоритм.

Рис. 5.4. Матрица соединений исходного графа

Выбираем в исходном графе вершину с максимальной степенью: r_max= 5. Максимальной степенью обладают вершиныX₄,X₅,X₇. В идеальном случае следовало бы пройтись по всем трём вариантам, но для простоты решения задачи и её наглядности выбираем одну любую вершину, напримерX₅.

На следующем шаге выбираем вершину, которая максимально связана с уже выбранной. Этот выбор проводим, анализируя строку X₅матрицы. Видно, что вершиныX₆иX₇связаны двумя ребрами с вершинойX₅. При выборе конкретной вершины на этом шаге имеется неопределенность. ПринимаемX₆. Получим первую итерацию куска с вершинамиX₅иX₆. Рёбра внутри куска графа стянуты в объединенную вершину X_5,6, и можно представить новую матрицу соединений (рис. 5.5) и рассчитать степени вершин этой матрицы.