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

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

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

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

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

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

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

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

были наименьшими для возможных способов отождествления вершин графа и узлов сетки. В приведенных формулах переменная r_i,j равна числу кратных ребер между вершинами х_i; x_j , а Р(u_i,j) - числу пересечений ребра u_i,j со всеми остальными ребрами графа, d_i,j - расстояние между узлами сетки, в которых размещены вершины х_i; x_j.

Расстояние d_i,j между узлами сетки, в которых размещены вершины х_i; x_j определяется выражением: d_i,j =|S_i – S_j|+|t_i- t_j|.

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

D=|| d_i,j||;

где:

d_i,j=0, если х_i = x_j;

и d_i,j= d_i,j, если х_i ≠ x_j;

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

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

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

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

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

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

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

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

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

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

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

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

, где

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

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

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

Очевидно,что при любом u_i,j изU_j[(d_i,j =1) → L_j =1], где U_j – множество ребер, инцидентных вершинеx_j, помещенной в позицию v.

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

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

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

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

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

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

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

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

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

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

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

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

5.Вычислить для вершины x_i координаты центра тяжести s_c и t_c.

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

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

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

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

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

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

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

Таблица 2

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

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

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

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

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

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

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

L₂≈1,3; L₃≈1,5; L₄≈1,7; L₅≈1,7; L₆≈2,2; L₇≈2,2; L₈=2; L₉=2.

Вершина x₆, имеет наибольшею суммарную длину связей: L_j=L₆=2,2.

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

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

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

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

Шаг 5. По значениям координат (s_c⁶ и t_c⁶) определяем подмножество вершин, которые можно поменять местами с вершиной х₆. Это все вершины, попавшие в радиус равный 1 (из узла 4), - х₄, х₅, х₇, х₈, т.к. они смежны вершине х_6.

Шаг 6. Вычисляем новые значения L₅⁶, L₄⁶, L₈⁶, L₇⁶ для вершин х_4, х_5, х_7, х₈, условно переставив каждую из них на место вершины х_6, т.е. в узел 6, и значения L₆⁴, L₆⁵, L₆⁷, L₆⁸ для х₆, условно поместив ее в узлы размещения вершин х₄, х₅, х_7, x_8.

Пример вычисления L₄⁶:

Аналогично вычисляются значения: L₅⁶ ≈1; L₇⁶ ≈2,4; L₈⁶≈2,5.

Пример вычисления L₆⁴:

Аналогично вычисляются значения: L₆⁵≈ 1,3;L₆⁷ ≈1,7; L₆⁸ ≈ 1,6.

Шаг 7. Вычисляем значения отклонений σ_j ^v для вершин х₆ и x₅; х₄; х₇; x₈.

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

σ⁴₆=L₆-L⁴₆= 2,2-1,6 = 0,6;

σ ⁵₆=L₆-L⁵₆ =2,2-1,3 = 0,9;

σ ⁷₆=L₆-L⁶₇= 2,2-1,1 = 0,5

σ ⁸₆=L₆- L⁸₆=2,2-1,6 = 0,6;

для вершин x₄; х₅; х₇; х₈

σ⁶₄=L₄-L⁶₄=1,7-2,3 = -0,6;

σ ⁶₅=L₅-L⁶₅=1,7-1 = 0,7;

σ ⁶₇ =L₇-L⁶₇= 2,2 - 2,4 = -0,2;

σ ⁸₆=L₈- L⁶₈=2,0-2,5 = -0,5;

Шаг 8. Вычисляем коэффициент δ_ij = σ^v_i + σ^a_j для вершин х₆ и х₅; х₄, х₇;х₈.

δ_4,6=σ₆⁴+σ₄⁶=0,6 + (-0,6) = 0;

δ _5,6=σ⁵₆+σ⁶₅= 0,9 + 0,7 = 1,6;

δ _7,6 = σ⁷₆ + σ⁶₇ = 0,5 + (-0,2) = 0,3;

δ _8,6 = σ ⁸₆+ σ ⁶₈ =0,6+ (-0,5) = 0,1.

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

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

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

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

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

Например, графу, представленному на рис.2.13, соответствует мультиграф Gμ, представленныйна рис.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. Какие современные пакеты прикладных программ реализуют математический аппарат теории графов для решения задач проектирования?