Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Размещение конструктивных элементов в монтажном пространстве (задача размещения)

Поиск

Размещение определяет качество трассировки, быстродействие, надежность. Из-за малого времени переключения схем ЦВМ - длина соединений влияет на задержки в распространении сигнала, затрудняет синхронизацию.

Исходные данные для размещения:

1) прямоугольная конструкция (ячейка, кристалл, панель);

2) число элементов для размещения;

3) граф схемы соединений элементов G=(X, U).

На заданную конструкцию накладывается координатная сетка (решетка) и оси координат s, t, представляя ее таким образом в виде графа Gr,. Теперь задача размещения сводится к отображению заданного графа схемы G=(X,U) в координатную сетку Gr, таким образом, чтобы вершины множества X размещались в ее узлах и суммарная длина связей:

или суммарное число пересечений

 
 

 


были наименьшими для возможных способов отождествления вершин графа и узлов сетки. В приведенных формулах переменная ri,j равна числу кратных ребер между вершинами хi; xj, а Р(ui,j) - числу пересечений ребра ui,j со всеми остальными ребрами графа, di,j - расстояние между узлами сетки, в которых размещены вершины хi; xj.

Расстояние di,j между узлами сетки, в которых размещены вершины хi; xj определяется выражением: di,j =|Si – Sj|+|ti- tj|.

Функция расстояний для узлов сетки Gr задается матрицей расстояний D.

 

D =|| di,j||;

где:

di,j =0, если хi = xj;

и di,j = di,j, если хi ≠ xj;

 

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

Итерационные, последовательные, смешанные, а также алгоритмы, основанные на идеях метода ветвей и границ.

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

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

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

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

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

Исходными данными для решения размещенияявляются граф G=(X,U), интерпретирующий схему электрическую принципиальную, и монтажная плоскость заданных размеров, на которой размещен граф сетки Gr. В общем случае считают, что монтажная плоскость имеет прямоугольную форму. В частном случае форма монтажной плоскости может быть любой формы. Требуется разместить вершины xi графа G в узлысетки Gr с минимизацией суммарной длины ребер uj из U. Число узлов сетки Gr больше иди равно числу вершин графа G. Предположим, что часть узлов сетки Gr уже отождествлена с некоторыми вершинами графа схемы.

Этап 1. Пусть вершина хi из множества Х помещена в (j+1)- юпозицию, где j - число занятых позиций, тогда коэффициентом связности ∆(xi) называется выражение; ∆(xi)= ai;h – ai,z, где ai;h - число ребер, связывающих xi- ювершину с ранее размещенными: ai,z = p(xi)- ai;h, т.е. число ребер, связывающих xi с не размещенными вершинами, где p(xi)- число ребер, инцидентных вершине xi; (локальная степень xi). Тогда ∆(xi)= ai;h – ai,z, где ai,h - число ребер, соединяющих xi с ранее размещенными вершинами. Значение ∆(xi) определяется для всех не размещенных вершин и выбирается xi с max ∆(xi). Вершина xi помещается в первую свободную позицию (узелсетки Gr). Как правило, размещение вершин начинается с крайнего левого узла сетки. Процесс последовательно продолжается до тех пор, пока не будут размещены все вершины графа G.

Этап 2 (итерационная часть алгоритма размещения)

Итерационная часть алгоритма размещения основана на понятии центра тяжести вершины.

Для оценки степени «предпочтительности» ν-й позиции для каждой вершины графа xj вводится понятие средней длины ребра - Lj_

 
 


, где

di,j - расстояние между узлами сетки, в которые помещены вершины xi и все смежные ей j- eвершины;

ri,j - числосвязей вершины xj со всеми смежными с ней j - ми вершинами графа G;

Lj - средняя длинаребер, инцидентных вершине xj, помещенной в позицию ν.

Очевидно,что при любом ui,j из Uj[(di,j = 1 ) → Lj =1], где Uj множество ребер, инцидентных вершине xj, помещенной в позицию v.

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

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

Для характеристики системы точек, связанных с вершиной xj вводится понятие центра тяжести, что позволяет рассматривать их как систему связанных материальных точек и отыскать такое положение для xj, которое обеспечит равновесие в сетке с точки зрения минимизации L(G). Вычисление координат центра тяжести (sc и tc) системы материальных точек производится по формулам:



 

координаты "центра тяжести" вершины xj,


где ri,j - количество связей между вершиной х0 и смежными с ней вершинами {xi}; вершина xi - это вершина с максимальным значением L; p(xi) - степень вершины хi.

Оценка качества решения задачи размещения в целом производится по формуле:

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

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

1.На заданную монтажную конструкцию наложить координатную сетку с осями координат s, t, т.е. построить граф Gr.

2.Выполнить первоначальное размещение вершин графа схемы G, совместив их с узлами сетки Gr.

3.Для всех вершин графа G вычислить значения суммарных длин связей Lj.

4.Выбрать вершину хi с max Lj.

5.Вычислить для вершины xi координаты центра тяжести sc и tc.

6.Определить подмножество вершин X’, вершины которого определяют область возможных перестановок с вершиной xi.

Произвести парные перестановки вершин множества X’ с вершиной xi, и вычислить для каждой вершины xj из X’, а также для вершины xi величины Lνj и Lνi с учетом нового местоположения (Lνj - это длина связей j -ой вершины, совмещенной с узлом сетки ν).

7.Вычислить отклонение σ vj = Lνj – Lkj }- - для xj из X’ для всех вершин, выбранных в соответствии с п.п.4,6, где ν и k соответственно «старая» и «новая» позиции местоположения вершин.

8.Вычислить значения δij = σ vi + σ aj парных перестановок вершин множества X’ и вершины хi. Выбрать такую пару вершин, для которой значение δij максимальное.

9.Произвести перестановку вершин.

Рассмотрим пример решения задачи размещения.

Пусть дан граф G=(X,U). Его матрица смежности R=||ri,j|| 9x9 имеет следующие значения элементов:

Таблица 2

r1,4=3 r4,1 =3 r2,3=2 r4,2=1
r1,7=2 r7,1 =2 r2,4=1 r3,5=2
r1,8 =3 r8,1 =3 r3,2=2 r5,3=2
r4,6=5 r6,7=5 r7,9=2 r7,8=3
r6,4=5 r7,6=5 r9,7=2 r8,7=3
r5,6=2 r6,8=6 r5,9=4 -
r 6,5=2 r8,6=6 r9,5=4 -

Значение элемента ri,j матрицы R равно числу ребер, связывающих i -ю и j -ю вершины rрафа G.

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

Шаr 1. На монтажную плоскость накладываем граф-сетку Gr из 9–ти узлов с координатами (SxT). Примем, что координаты узла 1 имеют значения (0,0).

 
 

 


Шаг 2. Отобразим граф G в координатную сетку Gr так, чтобы номера его вершин совпадали с номерами узлов координатной сетки. В общем случае номер вершины, может не совпадать с номером узла (рис. 2.12а).

 
 

 

 


Рисунок 2.12а – Размещение элементов схемы на монтажном поле.

Шаг 3. Определяем Lj для всех вершин xj из X. Значения di,j - определяем по формуле:

       
   
 
 


Аналогично вычисляем:

 

L2≈1,3; L3≈1,5; L4≈1,7; L5≈1,7; L6≈2,2; L7≈2,2; L8=2; L9=2.

Вершина x6, имеет наибольшею суммарную длину связей: Lj=L6=2,2.

Шаг 4. Вычисляем координаты центра тяжести tc, sc для вершины х6, так как она имеет наибольшею суммарную длину связей Lj.

Для вычисления по этой формуле выбираются все вершины, смежные x6. Это х4; х5; х7; x8, т.е. j ={4; 5; 7; 8}.

tс6 =(1-5 + 1-2 + 2-5 + 2-6)/(5 + 2 + 5 + 6) = 29/18≈1,4;

sc6 =(0-5 + l-2 + 0-5 + l-6)/(5 + 2 + 5 + 6) = 8/18≈0,4.

Шаг 5. По значениям координат (sc6 и tc6) определяем подмножество вершин, которые можно поменять местами с вершиной х6. Это все вершины, попавшие в радиус равный 1 (из узла 4), - х4, х5, х7, х8, т.к. они смежны вершине х6.

Шаг 6. Вычисляем новые значения L56, L46, L86, L76 для вершин х4, х5, х7, х8, условно переставив каждую из них на место вершины х6, т.е. в узел 6, и значения L64, L65, L67, L68 для х6, условно поместив ее в узлы размещения вершин х4, х5, х7, x8.


Пример вычисления L46:

Аналогично вычисляются значения: L56 1; L76 2,4; L86 2,5.

 

Пример вычисления L64:

 

Аналогично вычисляются значения: L65 1,3 ;L67 1,7; L68 1,6.

Шаг 7. Вычисляем значения отклонений σj v для вершин х6 и x 5; х4; х7; x8.

Для вершины х6:

σ46=L6-L46= 2,2-1,6 = 0,6;

σ 56=L6-L56 = 2,2-1,3 = 0,9;

σ 76=L6-L67= 2,2-1,1 = 0,5

σ 86=L6- L86= 2,2-1,6 = 0,6;

для вершин x4; х5; х7; х8

σ64=L4-L64= 1,7-2,3 = -0,6;

σ 65=L5-L65= 1,7-1 = 0,7;

σ 67 =L7-L67= 2,2 - 2,4 = -0,2;

σ 86=L8- L68= 2,0-2,5 = -0,5;

Шаг 8. Вычисляем коэффициент δij = σ vi + σ aj для вершин х6 и х5; х4, х78.

δ 4,66446 =0,6 + (-0,6) = 0;

δ 5,6 = σ 56+ σ 65= 0,9 + 0,7 = 1,6;

δ 7,6 = σ 76 + σ 67 = 0,5 + (-0,2) = 0,3;

δ 8,6 = σ 86 + σ 68 =0,6+ (-0,5) = 0,1.

Выбираем вершины с максимальным значением δij. Максимальное значение δij = δ 5,6 имеет взаимная перестановка вершин х6 и х5. Следовательно, меняем местами вершины х6 и х5.

 

 


Рисунок 2.12б – Окончательный вариант размещения элементов .

Первая итерация алгоритма размещения заканчивается. Переходим к новой итерации, повторяя аналогичные вычисления, в соответствии с шагами 3-8.

Окончательный вариант размещения (рисунок 2.12б) имеет суммарную длину L(G)= 55. Таким образом, суммарная длина уменьшилась с L(G)= 76 до L(G)= 55.

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

Например, графу, представленному на рис.2.13, соответствует мультиграф , представленныйна рис.2.14, 2.15.

 
 

 


Рисунок 2.13 – Пример графа

       
   
 

 


 


 

 


Рисунок 2.14


 

 

Рисунок 2.15


Далее «развернем» вершины мультиграфа, представленного на рис.2.14, соответственно вершинам графа на рис.2.13. Полученный граф, представленный на рис.2.16, соответствует лучшему размещению вершин графа с точки зрения меньшей суммарной длины соединений.

 
 

 

 


Рисунок 2.16 –Вариант лучшего размещения при минимизации длин связей.

Применение факторизации позволяет уменьшить общую длину соединений L(G) дополнительно на 5-7%.

 

Вопросы для самопроверки

  1. Какие требования предъявляются к математическим моделям РЭС?
  2. Чем отличаются различные математические модели РЭС? На каких этапах проектирования они применяются?
  3. Что такое коммутационная схема радиоэлектронного средства? Чем она отличается от схемы электрической принципиальной?
  4. В чем заключаются задачи покрытия и разбиения?
  5. Чем характеризуется задача размещения? Какие алгоритмы применяются на этом этапе?
  6. В чем суть задачи трассировки? В чем особенность алгоритмов, применяемых на данном этапе?
  7. Как классифицируются алгоритмы компоновки?
  8. Какие современные пакеты прикладных программ реализуют математический аппарат теории графов для решения задач проектирования?

Пример построения математической модели объекта проектирования и структурный синтез технического устройства

В этом разделе рассматривается процесс разработки модели и применения рассмотренных ранее алгоритмов проектирования на конкретном примере построения модуля РЭС.



Поделиться:


Последнее изменение этой страницы: 2016-12-15; просмотров: 378; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.26.149 (0.01 с.)