СППР

41

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

Сформулируем задачу распределения функций. Пусть задано множество функций F, подлежащих распределению между l элементами:

F = [Fi J = I,/};		Fi C s F j-Z ; i,j = l,j; i * j .	Любую		из	функций
Fi s F xF *	можно реализовать на одном из / элементов; F *				-	множество
уже распределённых функций.
Введём параметр распределения X ik:
χ	f1,	если і - я фунция реализуете я на к - м элементе, к = 1,/,
‘к ~	(0 - в противном случае.		_	__
		і			т.е. каждую
Обязательно выполнение условия £ X ik = 1, к = 1,1, і = I1/ ,
		/«I
функцию можно закрепить только за одним элементом.

Далее через atj обозначим алгоритмическую связность /-й функции с

7-й (относительная частота выполнения функции Fj после функции Fi), Bi

- объём памяти, необходимый для выполнения i-й функции, в№ - располагаемый объём памяти вычислительных средств к-то элемента.

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

найти min Y Y a ijX ik	(1.6)
Ar=Ii=I
при ограничениях
Y B iX ik < в ^ , к = U
J = I	(1.7)
Y X ik = I, ATf t =W -
I=I

Решением	задачи	будет	совокупность	векторов
X 1 = \хп,...,хп,...,хп\·,		X 2 =\Х/2,---,Хі2>—>Х/2\і		—;
Χ'ι —\Χ\ι ,·■■,X її,·■·,X л I с составляющими			X ik =Q,\, обеспечивающих

минимум целевой функции (1.6).

Задачу можно интерпретировать как задачу разрезания конечного ориентированного взвешенного графа G = (Y,V), в котором вершинам множества Y ставится в соответствие объём памяти, занимаемый й

42

функцией Bi а множеству дуг - алгоритмическая связность i-й функции с

j-й - аij. Решение	состоит в разрезании графа G	на k = l подграфов <Gk>,
удовлетворяющих	условиям	и требованиям

минимума целевой функции (1.6) при ограничениях на другие параметры

(1.7).

Рассмотрим возможность применения алгоритма, изложенного в работе [23] для решения поставленной задачи. Алгоритм последовательно закрепляет вершины графа G = (Y1V) за заданным числом подграфов

В процессе работы алгоритма все вершины делятся на уже закреплённые (Fn ) и ещё не закреплённые

свободные.

Нижняя оценка степени связности графа G при переносе некоторой i-й вершины из множества F1 в множество Fn определяется следующим образом;

где Q(Yn) - связность к подграфов, частично сформированных закреплением вершин (сумма весов рёбер, связывающих закреплённые вершины на различных частично сформированных подграфах); ∆Qjj(Yn) -

приращение Q(Yn) при включении некоторой i-й свободной вершины (Yi єFl ) в некоторый подграф Gj, нижняя оценка суммы весов рёбер,

соединяющих вершины из множества уже закреплённых вершин F n с

вершинами из множества ещё свободных Fl, которые образуют граф Г"; dij - нижняя оценка связности разрезания графа Г", составленного из

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

где alh - сумма весов ребер, соединяющих вершину l Є Ft со всеми вершинами из F *, креме вершин подграфа Gk;

Пусть на m-м шаге алгоритма n вершин, образующих Fn*,

закрепляются за подграфами Gk, k = 1 +l . В графе Г"(Vn,Un),

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

Вершина закрепляется за тем подграфом, который будет иметь наименьшее значение Q(Y„+l), определяемое по формуле (1.8). Процедура аналогично выполняется для остальных вершин.

Точное решение задачи можно ,получить за конечное число шагов алгоритма, который реализует процесс направленного перебора с возвращениями и напоминает метод "ветвей и границ”. К тому же для вычисления нижней оценки суммы весов дуг требуется решение транспортной задачи.

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

Известны два эвристических алгоритма [24, 25], которые принципиально применимы для решения задачи разрезания графа в постановке (1.6), (1.7): алгоритм разбиения взвешенного графа на связные подграфы с заданным числом вершин и минимальным суммарным весом разрезанных рёбер; алгоритм разбиения меченой сети на заданное число связных подграфов с ограничениями на суммы весов вершин и минимальным суммарным весом разрезанных рёбер.

В первом случае задан неориентированный конечный связный

минимальной величина Z - сумма весов разрезанных ребер.

44

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

Формируется симметричная матрица смежности исходного

взвешенного где

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

Данный недостаток устраняется другим алгоритмом, решающим задачу разрезания графа в следующей постановке [24]. Имеется меченая сеть G=<A, Р>, т.е. неориентированный конечный связный граф, в котором

вершины снабжены	весами;	А = {а; }	- множество вершин, Ul = и ;
P - множество рёбер;	a(j - вес ребра		вес вершины
at . Требуется разрезать граф G m l			связных подграфов
таких, что сумма весов вершин этих подграфов
удовлетворяет оценке	В < В к	В. При этом должна быть минимальной

величина Z - сумма весов разрезанных рёбер в разбиении графа. Этот алгоритм, как и предыдущий, строится, исходя из матричного способа задания взвешенного графа, и использует идею выделения вершин для искомого подграфа. Отличие заключается в том, что вместо количества вершин применяются веса вершин, на сумму которых накладываются ограничения.

Рассмотрим эвристический алгоритм, позволяющий устранить указанный недостаток [26]. Пусть дан ориентированный конечный взвешенный граф G =<А, Р>, соответствующий функциям, выполняемым вычислительными средствами, где А = {я,·} - множество вершин, \А\ = п \Р

- множество рёбер;	β;-	вес вершины а ,; а# - вес ребра
А*к - множество	уже	закритлённых	вершин за	подграфами <G*>.
Необходимо разрезать граф G нa T связных подграфов				п . Л. И.'ъ Ir — I
			О
I.... Т, таких, что сумма весов р >азрезанных рёбер Z бу
сумма весов вершин подграфов			удовлетворяет оценке Bk < Bk,
к - 1,2....Г.

45

Алгоритм работает следующим образом.

I. Вводится матрица смежности вершин графа W1(операция 1).

II. Суммируются элементы матрицы W1 в строках (в столбцах) и определяются локальные степени связи вершин графа G1. Путём приписывания соответствующих строк и столбцов формируется расширенная матрица W ^ (операция 2).

III. В строке а, матрицы W^ , соответствующей вершине а, с

наибольшей локальной степенью связи, определяется наибольший элемент GiJ (операции 3, 4). Если в строке а, несколько наибольших элементов, то

выбирается вершина столбца с наибольшей суммой:

1. Если вершина а, или а ■уже закреплена за одним из подграфов,

то переходим к операции 4.

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

3. Если вершина а, не связана ни с одной уже закреплённой вершиной, то выбирается следующая строка ак с наибольшей локальной

степенью связи и поиск продолжается.					ABk < $j+ $j <Bk;
IV.	1.	Если	выполняется	условие
ABk = Bk -η ιίηβ;,		то	вершина а, закрепляется		за множеством

(операция 9). Формирование множества Ak заканчивается. Подграф Gk сформирован.

2. Если выполняется условие β, +ру < Bk , то вершина Oj (O1)

закрепляется за множеством Ак\ к которому принадлежит ранее

закреплённая вершина (операции 11,12). Записывается матрица смежности графа, полученного из исходного графа путём конденсации вершин

Oi и aj . Матрица получается из матрицы путём вычёркивания

Oi строк (столбцов) и приписывания строки (столбца), полученной

поэлементным сложением аг й и α, -й строк (столбцов) матрицы .

3. Если выполняется условие β, + Py >Bk , то я,· не включается в

множество A ^ . Множество Ak заканчивается (закрывается). Подграф Gk

сформирован.

V. В суммарной строке Oi(J) определяем наибольший элемент.

46

1. Если наибольший элемент строки a, (J) , стоящий в столбце ак, больше (или равен) суммы других элементов столбца ак и выполняется

условие + Pir < Bk, το множество Ak ' пополняется вершиной ак (если

она не закреплена за другим подграфом). Переходим к п. IV.2, где вместо Oj фигурирует Oj(J); а вместо а}- ак. Процесс конденсации

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

подграфа Gk-

2. Если наибольший элемент строки at(J) , стоящий в столбце ак,

меньше суммы других элементов столбца ак, то множество вершин связного подграфа Gkнайдено (Ak= Ак ’).

VI. Удаляем из графа G вершины подмножества Ak со всеми инцидентными им рёбрами, т.е. вычёркиваем из матрицы W1 строки и столбцы, соответствующие вершинам подмножества Ak (операция 14).

Получаем матрицу смежности W2. Исследуем оставшийся подграф на связность. Если он связный, то переходим к операции 2.

После нахождения (к - 1) подмножеств Aj, A2,..., Ak^ и удаления вершин этих подмножеств из множества вершин А следует проверить, что

4

сумма весов оставшихся вершин удовлетворяет условию Σ Pi < Bk . В /=1

случае выполнения условия множество оставшихся вершин образует последнее искомое подмножество Ak; в противном случае одно из подмножеств A1, A2,...,Ak^ следует пополнить за счёт увеличения

суммарного веса разрезанных рёбер.

Рассмотрим простой пример практического применения алгоритма для распределения функций между локальными СППР. Предположим, что предварительно определено, что число локальных СППР равно трём (к = 1, 2, 3), а число выполняемых ими функций - шести (г = 1,..., 6;J = I , ..., 6).

Исходные данные о характеристиках выполняемых функций: относительная загрузка вычислительных средств СППР при

выполнении функций P1= 0,4; P2= 0,3; P3= 0,5; P4= 0,6; P5= 0,3; P6= 0,7;

допустимые пределы загрузки вычислительных средств 0,4 < В < 1,7; матрица взаимосвязи выполняемых функций имеет вид (табл. 1.2):

47

Т а б л и ц а 1.2

Необходимо разбить граф G на 3 связных подграфа с минимальным суммарным весом разрезанных рёбер, причём сумма весов вершин каждого подграфа должна находиться в пределах ограничения

0,4 < Д < 1,7.

Решаем задачу в соответствии с предложенным алгоритмом.

Т а б л и ц а 1.3

JV1V=

Л,(1)= ias,aA}\ К 5 =р4 +P5= 0,6 + 0,3 =0,9; 0,4<0,9 < 1,7.

Т а б л и ц а 1.4

Wliy=

Так как наибольший элемент строки а4 5, равный 2, больше суммы

других элементов столбца аг и P4 5 2= 0,9 + 0,3 = 1,2; 0,4 < 1,2 < 1,7, то

множество Л,(1) следует пополнить вершиной а2 ’ А™={а4,а5,а2}.

46

1. Если наибольший элемент строки Oi(J), стоящий в столбце ак, больше (или равен) суммы других элементов столбца ак и выполняется

условие	+ Р* й Bk, то множество			пополняется вершиной ак (если
она не закреплена за другим подграфом). Переходим к п. IV.2, где вместо
Oi фигурирует α(·(J); а вместо				Oj - ак. Процесс конденсации
продолжается		до	максимально	допустимой	суммы	весов

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

подграфа Gk.

2. Если наибольший элемент строки Cti(J), стоящий в столбце ак,

меньше суммы других элементов столбца ак, то множество вершин

связного подграфа Gkнайдено (Ak=Ak^).

VI. Удаляем из графа G вершины подмножества Ak со всеми инцидентными им рёбрами, т.е. вычёркиваем из матрицы W1 строки и столбцы, соответствующие вершинам подмножества Ak (операция 14).

Получаем матрицу смежности W2- Исследуем оставшийся подграф на связность. Если он связный, то переходим к операции 2.

После нахождения (к - 1) подмножеств A1, A2.... ЛкА и удаления вершин этих подмножеств из множества вершин А следует проверить, что

сумма весоЬ оставшихся вершин удовлетворяет условию ^ p f < Bk . В

1=1

случае выполнения условия множество оставшихся вершин образует последнее искомое подмножество Ak; в противном случае одно из подмножеств A1, A2 ,...,Ak^l следует пополнить за счёт увеличения

суммарного веса разрезанных рёбер.

Рассмотрим простой пример практического применения алгоритма для распределения функций между локальными СППР. Предположим, что предварительно определено, что число локальных СППР равно трём (к = 1, 2,3), а число выполняемых ими функций - шести (; = 1,..., 6;j = 1,..., 6).

Исходные данные о характеристиках выполняемых функций: относительная загрузка вычислительных средств СППР при

выполнении функций βι= 0,4; P2= 0,3; P3= 0,5; P4= 0,6; P5= 0,3; P6= 0,7;

допустимые пределы загрузки вычислительных средств 0,4 < В < 1,7; матрица взаимосвязи выполняемых функций имеет вид (табл. 1.2):

47

Т а б л и ц а 1.2

Необходимо разбить граф G на 3 связных подграфа с минимальным суммарным весом разрезанных рёбер, причём сумма весов вершин каждого подграфа должна находиться в пределах ограничения

0,4 < .S < 1,7.

Решаем задачу в соответствии с предложенным алгоритмом.

Т а б л и ц а 1.3

4 1)= {α5,α4}; β4ι5 = β4 +P5= 0,6 + 0,3 = 0,9; 0,4< 0,9< 1,7.

Т а б л и ц а 1.4

Так как наибольший элемент строки а45, равный 2, больше суммы

других элементов столбца а2 и P4iSj2= 0,9 + 0,3 = 1,2; 0,4 < 1,2 < 1,7, то

множество ЛР следует пополнить вершиной а2:

{а4,а5,а2}·

48

Осталось три вершины, 3 > 2,40.

Т а б л и ц а 1.5

Видим, что множество Л[2) следует пополнить вершиной а3:

находим P4J 2i3= 1,2 +	0,5 =	1,7,	что удовлетворяет оцениванию. Итак,
л{2)= {а4,а5,а2, а3}.
Осталось две вершины:		аг и а6. Веса этих вершин удовлетворяют
оцениванию. Выходит,	A2 = Ia1),		A3 ={ай). Подсчитаем сумму весов

разрезанных рёбер:

Z = 9,1 - (0,5 + I + I + 0,5 + I + I) = 4,1.

«2(0,3)

Рис. 1.8. Разбиение графа G на подграфы Gi, G2, G3

Итак, исходный граф G в соответствии с условиями задачи разбит на подграфы Gi, G2, G3, изображённые на рис. 1.8.

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