Материал: Lab 2 Z Рбд-31

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждения высшего образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Радиотехнический факультет Кафедра «Проектирование и технология электронных средств»

Дисциплина: «Математическое обеспечение САПР»

Лабораторная работа №2:

«ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА КОМПОНОВКИ

СХЕМ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ»

Работу выполнил: Проверил: Студент группы Рбд-31 профессор Зарипов Т.Р. Мактас М.Я.

Ульяновск 2021

Цель работы - исследовать эффективность последовательного метода компоновки конструктивных элементов и узлов РЭС в узлы высшего уровня; усвоить особенности алгоритмизации и программирования задачи компоновки конструктивных элементов на ПЭВМ; приобрести навыки построения математических моделей объектов конструирования, реализации и исследования их при решении задачи компоновки в САПР.

Общие сведения о задаче компоновки.

В настоящее время в радиоэлектронике принят функционально-узловой метод проектирования. Он предусматривает расчленение радиоэлектронных средств (РЭС) на отдельные конструктивно законченные единицы (модули) различных уровней (рангов). Это могут быть отдельные платы – типовые элементы замены (ТЭЗы), функциональные узлы, субблоки, блоки, панели, пульты, стойки. В связи с этим при разработке конструкций РЭС проектировщик неизбежно сталкивается с задачей распределения элементов схемы низшего уровня по коммутационным пространствам модулей данного уровня иерархии. При ее решении основным критерием оптимальности компоновки модулей является минимизация числа межмодульных связей, что необходимо для повышения надежности схем (за счет уменьшения числа разъемных соединений), уменьшения влияния наводок и времени задержки сигнала в цепях (вследствие минимизации суммарной длины соединений), упрощения конструкции и повышения технологичности разрабатываемого устройства.

Математическая формулировка задачи.

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

Дан мультиграф G(X, U). Требуется разбить его на отдельные куски , ... так, чтобы число ребер, соединяющих эти куски было минимальным. Это означает, что надо минимизировать функцию:

, где . (2.1)

При разбиении графа на куски задаются следующие ограничения:

(2.2) (2.3) (2.4) (2.5),

где -множество ребер, соединяющих куски и .

Другими словами, совокупность кусков разбиения графа является разбиением графа G, если любой кусок из этой совокупности не пустой

(2.6)

и для любых двух кусков P(G) пересечение множества вершин - пустое множество (2.3), а пересечение множества ребер (2.4) может быть не пустым. Кроме этого, объединение всех кусков (2.5) должно в точности равняться графу G.

В выражении (2.4) множество определяет подмножество ребер , попадающих в разрез ( сечение ) между кусками и графа G.

Конструктивными ограничениями в задачах компоновки являются: а) максимально допустимое количество вершин t в куске

(2.7)

б) число кусков разрезания графа

K=l/t (2.8),

где l - количество вершин в исходном графе.

в) максимальное число внешних связей каждого отдельного куска графа

(2.9).

Физический смысл ограничений (2.2) – (2.9) следующий. Условия (2.2) – (2.4) означают, что не может быть двух узлов, содержащих один и тот же элемент, вместе с тем электрические цепи, соединяющие отдельные узлы существуют. Условие (2.5) – суммарное число элементов, входящих в отдельные узлы, равно количеству элементов, входящих в электрическую схему всего устройства. Условие (2.6) – не может быть узла, в котором не содержится ни одного элемента. Условие (2.7) – соответствует числу конструктивных элементов, которые необходимо разместить в коммутационном пространстве, (2.8) – требуемое число узлов, в которые требуется скомпоновать конструктивные элементы устройства, (2.9) – определяет количество контактов используемого разъема.

Для оценки качества компоновки схемы в узлы, что соответствует оценке качества разбиения на куски, введем понятие коэффициента разбиения . Для этого допустим, что граф G разбит на k кусков: Тогда множество ребер U графа G можно представить в виде

(2.10).

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

Тогда отношение суммарного числа внутренних ребер (ребер подмножеств ) к суммарному числу соединительных ребер (ребер подмножеств ) назовем коэффициентом разбиения графа G.

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

Существует значительное количество алгоритмов компоновки, которые можно условно разбить на пять групп: 1) последовательные алгоритмы; 2) итерационные алгоритмы; 3) алгоритмы, использующие методы целочисленного программирования; 4) алгоритмы, основанные на решении задачи о назначении; 5) смешанные алгоритмы.

Последовательные алгоритмы компоновки. Метод максимальной конъюнкции – минимальной дизъюнкции.

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

Основной критерий разбиения графа на куски – минимум числа соединяющих ребер между кусками графа. Если формировать куски графа G так, чтобы каждый из кусков во множестве содержал возможно большее число ребер, то при этом получится локальный минимум суммарного числа K соединяющих ребер. Рассмотрим метод максимальной конъюнкции – минимальной дизъюнкции. Пусть дана схема с множеством элементов , соединенных между собой множеством электрических цепей Ее необходимо скомпоновать в узлы, включающие по t элементов. Число внешних связей узлов не должно превышать z (z – число контактов в разъеме).

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

Вначале отбирается множество элементов, назначение каждого из которых в формируемый узел не превышает предельно допустимого числа z внешних связей узла. Затем из полученного множества элементов выбираются такие, которые имеют с назначенными в формируемый узел элементами наибольшее число общих цепей. При работе алгоритма схема представляется в виде графа Кенига G(E,V,R) , в котором подмножество вершин E и V интерпретируют соответственно множества элементов E и электрических цепей V. При этом вершинa соединяется с вершиной ребром в том случае, когда элемент принадлежит цепи . Для вычисления на ЭВМ граф G(E,V,R) задается матрицей инцидентности Q=||q|| (n m),в которой число строк n определяется количеством элементов схемы, а столбцов m – количеством электрических цепей. Элемент стоящий на пересечении i-й строки и j-го столбца, равен 1, если элемент подключен к цепи и нулю в противном случае.

Алгоритм: 1) Ввод матрицы . 2) По матрице определяем локальные степени вершин : 3) Из множества нераспределённых вершин Е выбираем вершину c локальной степенью . 4) Назначаем выбранную вершину во множество , формируемого узла. 5) Строку матрицы , соответствующую назначенной вершине , модифицируем путём поразрядной дизъюнкции со строками матрицы,соответствующими нераспределённым элементам : , , ... . 6) Определяем суммы элементов = в модифицированных строках 7) Из множества строк выбираем такие, в которых Объединяем их во множество 8) Если то переходим к 17, иначе к 9. 9) Строку матрицы , соответствующую элементу , модифицируем путем поразрядной конъюнкции со строками множества : , ,... . 10) Определяем суммы элементов в модифицированных строках . 11) Из множества строк выбираем такую, в которой 12) Вершину дающую назначаем в формируемый узел . 13) Если | то идти к 17, иначе к 14. 14) Определяем множество нераспределенных элементов . Если , то идти к 19, иначе к 15. 15) Составляем матрицу Для чего в исходной матрице вместо строк, соответствующих элементам, назначенным в узел , записываем дизъюнкцию всех указанных строк. 16) Идти к 5. 17) Узел считаем сформированным. Поэтому преобразуем матрицу . Исключаем из нее строки, соответствующие элементам, включенным в узел . Получаем матрицу . 18) Идти к 2. 19) Конец.

Ход работы: Дана схема соединений, которую необходимо скомпоновать в узлы, содержащие не более 4 элементов.

Рис.1 Исходная схема.

Рис.2 Матрица инцидентности.

Рис.3 Матрица инцидентности (результат).

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

Рис.4 Машинная компоновка элементов в блоки.

Рис.5 Эскиз компоновки схемы на блоки “вручную”

Ручной расчет работы алгоритма:

М аксимальную локальную степень, равную 4, имеют вершины e₃, e₁₀. В качестве исходной выбираем 1-ю по порядку. Выполним дизъюнкцию 3-й строки с остальными.

3 00001110000001 1 10000000000000

3 v 1 10001110000001 Σ = 5

3 00001110000001 2 00011000000000

3 v 2 00011110000001 Σ = 5

3 00001110000001 4 00000000000010

3 v 4 00001110000011 Σ = 5

3 00001110000001 5 00000000000111

3 v 5 00001110000111 Σ = 6

3 00001110000001 6 00000001101000

3 v 6 00001111101001 Σ = 7

3 00001110000001 7 00010100000000

3 v 7 00011110000001 Σ = 5

3 00001110000001 8 01000000000000

3 v 8 01001110000001 Σ = 5

3 00001110000001 9 00100000000000

3 v 9 00101110000001 Σ = 5

3 00001110000001 10 11100010000000

3 v 10 11101110000001 Σ = 7

3 00001110000001 11 00000001110000

3 v 11 00001111110001 Σ = 7

3 00001110000001 12 00000000011100

3 v 12 00001110011101 Σ = 7

Выбираем вершины, имеющие min c(q_ik), и включение которых в узел не превысит условия z <= 7.

Подходящими являются:

e₁, e₂, e₄, e₇, e₈, e₉,

В ыполним конъюнкцию 3 строки со строками отобранных элементов:

3 00001110000001 1 10000000000000

3 ^ 1 00000000000000 Σ = 0

3 00001110000001 2 00011000000000

3 ^ 2 00001000000000 Σ = 1

3 00001110000001 4 00000000000010

3 ^ 4 00000000000000 Σ = 0

3 00001110000001 7 00010100000000

3 ^ 7 00000100000000 Σ = 1

3 00001110000001 8 01000000000000

3 ^ 8 00000000000000 Σ = 0

3 00001110000001 9 00100000000000

3 ^ 9 00000000000000 Σ = 0

Выбираем вершину e₂, величина S у которой максимальна

2v3 | 00011110000001 | 5 1 | 10000000000000 | 1 4 | 00000000000010 | 1 5 | 00000000000111 | 3 6 | 00000001101000 | 3 7 | 00010100000000 | 2 8 | 01000000000000 | 1 9 | 00100000000000 | 1 10 | 11100010000000 | 4 11 | 00000001110000 | 3 12 | 00000000011100 | 3

Дизъюнкции строки 2v3 со всеми остальными: