МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КОМПОНОВКИ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ РАЗРЕЗАНИЕМ ГРАФА ПОСЛЕДОВАТЕЛЬНЫМ МЕТОДОМ

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КОМПОНОВКИ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ РАЗРЕЗАНИЕМ ГРАФА ПОСЛЕДОВАТЕЛЬНЫМ МЕТОДОМ

Шандриков А.С.

Одним из первых этапов проектирования сложных радиоэлектронных средств (РЭС) с многоуровневой конструктивной иерархией является компоновка – распределение элементов i-го иерархического уровня по элементам (i+1)-го уровня. Первый, самый низший уровень конструктивной иерархии, занимают дискретные радиоэлектронные компоненты (РЭК) – резисторы, конденсаторы, диоды и т.п.

Процесс компоновки моделируется разрезанием графа G = (X,U), являющегося математической моделью принципиальной электрической схемы проектируемого РЭС, где X – вершины графа, обозначающие РЭК, U – рёбра графа, обозначающие связи между РЭК в соответствии с принципиальной электрической схемой [1, 2].

Качество компоновки оценивается различными показателями. Самым распространённым показателем является минимум связей между полученными подграфами или коэффициент разрезания – отношение суммарного количества связей между вершинами внутри подграфов (внутренних связей) к суммарному количеству связей между вершинами разных подграфов (внешними связями).

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

В некоторых случаях по другим соображениям определённые РЭК должны находиться в разных узлах.

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

При выполнении компоновки с использованием математической модели в виде графа множество вершин, располагаемых в разных подграфах, в работах [1, 2] определяется как множество запрещённых вершин. Ситуация, когда существует два множества вершин, вершины одного из которых должны располагаться в одном и том же подграфе (множество совместных вершин X_s), а вершины другого – в разных подграфах (множество запрещённых вершин X_z), рассмотрена в [3].

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

Классический последовательный метод разрезания графа предполагает следующие действия. По некоторому критерию выбирается начальная вершина x_i формируемого подграфа, а затем выполняется построение множества Гx_i = {x_i,x_j, …, x_k}, содержащего выбранную начальную вершинуx_i и все смежные ей вершины. Мощность полученного множества |Гx_i| сравнивается с количеством вершин, заданным для формируемого подграфа, и в случае их равенства подграф считается сформированным, а вошедшие в него вершины удаляются из исходного графа. Чаще всего оказывается, что |Гx_i| ≠ n_k, где n_k – количество вершин, заданное для k-го подграфа.

Если |Гx_i| n_k, то необходимо выполнить следующие действия [1, с. 60] и [2, с. 31].

1. Во множестве Гx_iвыбрать вершину x_j, имеющую максимальное количество связей со всеми остальными вершинами множества Гx_iи связанную с вершинами множества X\Гx_i, то есть с вершинами, не вошедшими в множество Гx_i.

2. Построить множество Гx_j.

3. Сформировать объединённое множество Гx_iГx_j­.

4. Проверить выполнение условия |Гx_iГx_j| = n_k и в случае его невыполнения вновь повторить описанные шаги.

Данный подход к выбору вершины x_j ∈ Гx_i является предпосылкой получения неоптимального результата по критерию минимума связей между сформированными подграфами.

Рассмотрим пример, подтверждающий вышеприведенное высказывание. На рис. 1 представлен подграф G₁ = (X₁,U₁) графа G = (X,U), который необходимо дополнить ещё одной вершиной до значения |X₁| = 5. На данный момент подграф G₁ содержит 6 внутренних рёбер и 6 внешних.

Если следовать рекомендациям [1, 2], описанным в действиях 1-3, то в множестве X₁ = {x₁,x₂,x₃,x₄} следует выбрать вершину x₁, имеющую максимальное количество внутренних связей среди вершин с внешними связями, и построить множество Гx₁ = {x₁,x₂,x₄,x₅}. Объединив множества X₁ и Гx₁, получим: X₁Гx₁ = _­{x₁,x₂,x₃,x₄,x₅}.

Мощность полученного множества |X₁Гx₁| = 5 = n₁, следовательно, подграф G₁ = (X₁,U₁) считается сформированным (рис. 2).

Качество полученного результата можно оценить по коэффициенту разрезания: Δ(G) = L/K, где L – количество внутренних рёбер формируемого подграфа; K – количество внешних рёбер.

В рассматриваемом примере Δ(G₁) = 7/9 = 0,78.

После дополнения множества X₁ по методике [1, 2] в формируемый подграф была назначена вершина x₅, в результате чего в подграф G₁ добавилось больше внешних рёбер, чем внутренних.

Оптимальность результата разрезания графа последовательным методом можно существенно повысить, если изменить критерий выбора вершины для дополнения формируемого подграфа недостающим количеством вершин. С этой целью выбор вершины x_j для пополнения формируемого подграфа следует начинать не в самом множестве Гx_i, как предлагается в [1, 2], а в множествеX\Гx_i и использовать для этого числовую характеристику – число связности δ(x_j), которое определяется по формуле [4]:

δ(x_j) = (x_j) – z(x_j) {x_jX\Гx_i, (1)

где (x_j) – количество внешних связей, т.е. количество рёбер, соединяющих вершинуx_jX\Гx_i с вершинами, ранее назначенными в формируемый подграф;

z(x_j) – количество внутренних связей, т.е. количество рёбер, соединяющих вершинуx_j с вершинами множества X\Гx_i.

Из (1) очевидно, что число связности может принимать как положительное так отрицательное значение или быть равным нулю. Отрицательное значение δ(x_j) свидетельствует о том, что приращение внешних связей формируемого подграфа будет больше приращения внутренних связей, а положительное значение δ(x_j) – наоборот, говорит о том, что приращение внешних связей формируемого подграфа будет меньше приращения внутренних связей. Так как для минимизации внешних связей определяющим является второй вариант, то выбор вершины для назначения в формируемый подграф следует осуществлять по критерию

δ(x_j) = max δ(x_j), (2)

Для вершин x₅,x₆, и x₇ их связи с вершинами множества X₁ = {x₁,x₃,x₄} являются внешними, а их связи с вершинами множества X\X₁ (вершины этого множества на рис. 1-2 условно не показаны) – внутренними.

В рассматриваемом примере, представленном на рис. 1, числа связности вершин множества X\X₁: δ(x₅) = 1 – 4 = –3; δ(x₆) = 3 – 2 = 1; δ(x₇) = 2 – 2 = 0.

В процессе формирования подграфа может возникнуть и другая ситуация, когда из формируемого подграфа необходимо удалить лишнюю вершину или несколько вершин, т.е. когда |Гx_i| n_i. В этом случае для удаления рекомендуется выбирать вершину с минимальным количеством внутренних рёбер [1, с. 60] и [2, с. 30]. Если лишних вершин несколько, то удаление производится поочерёдно несколькими шагами, по одной вершине на каждом шаге.

Данный критерий выбора удаляемой вершины также нельзя назвать удачным. Как и в предыдущем случае, из [1, 2] неясно, как поступать, если данному критерию удовлетворяют несколько вершин. Предположим, что из формируемого подграфа G₃ = (X₃,U₃), содержащего 10 внутренних и 6 внешних рёбер, необходимо удалить одну лишнюю вершину (рис. 4).

Минимальное количество внутренних рёбер z(x_i) имеет единственная вершина x₄. Согласно [1, 2], именно эта вершина и должна быть удалена из формируемого подграфа, в результате чего (рис. 5) коэффициент разрезания формируемого подграфа будет равен Δ(G₃) = 8/7 = 1,14.

Если визуально проанализировать рассматриваемую ситуацию, то можно заметить, что удаление из формируемого подграфа G₃ вершины x₁ обеспечит более приемлемый результат разрезания графа за счёт того, что ей инцидентно большее количество внешних рёбер, чем вершине x₄. Очевидно, что и в этом случае следует изменить подход к выбору удаляемой вершины и таким подходом, как и в предыдущем случае, может стать выбор вершины для удаления по числу связности:

δ(x_i) = (x_i) – z(x_i) {x_i | x_i X₃. (3)

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

Поясним данную ситуацию на примере [4].

При разрезании графа на неравные по количеству вершин подграфы необходимо рассмотреть и другие варианты формируемого подграфа, в котором будут находиться, например, четыре вершины и из них выбрать лучший вариант на данной стадии разрезания графа. С этой целью согласно [3] для всех внешних вершин было определено число связности и в соответствии с алгоритмом в формируемый подграф была назначена вершина x₄ (рис. 8).

ε(r) = k – l = min(k – l)

Выводы.

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

2) Для оценки оптимизации критерия качества сформированных подграфов целесообразно использовать минимальную разность между количеством внешних и внутренних рёбер полученного разрезания.

Литература

1. Мелихов, А.Н. Применение графов для проектирования дискретных устройств /А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик – М. : Наука, 1974 – 304 с.

2. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов [и др.]; под ред. К.К. Морозова. – М.: Сов. радио, 1978 – 136 с.

3. Шандриков, А.С.Последовательный метод разрезания графа с минимизацией внешних связей / А.С. Шандриков // Вестник Учреждения образования «Витебский государственный технологический университет» Пятый выпуск / УО «ВГТУ». – Витебск, 2003. С. 94-100.

4. Шандриков, А.С. Минимизация внешних связей в процессе разрезания графа последовательным методом / А.С. Шандриков / VIII Всероссийская научная конференция по математическому моделированию и информационным технологиям : Новосибирск, 27-29 ноября 2007 г. / Ин-т вычислительного моделирования Сибирского отд. Российской Академии наук [Электронный ресурс] – Режим доступа: http://www.nsc.ru/ws/history.php?ru+168+8609.