80
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012
ми, которые должны быть размещены в сетевых узлах нижних яру-
сов. Завершается решение задач в узлах верхних ярусов, где проис-
ходит выполнение заданий, являющихся максимальными элемента-
ми. В процессе работы системы источниками передаваемых данных
становятся узлы, выполняющие задания, а стоками — узлы с задани-
ями, ожидающими данные в соответствии с графами алгоритмов. Во
всех сетевых узлах активные задания выполняются в порядке уста-
новленных очередей.
ЯП-архитектура исключает возможность зацикливаний, связан-
ных с бесконечными блужданиями данных по сети. Процессы пере-
дачи данных (будем называть их сообщениями) также допускают
распараллеливание. Каждое сообщение можно разбивать на блоки
(
пакеты), снабженные нумерацией и метками, идентифицирующими
решаемую задачу. Это потребуется для сборки переданного сообще-
ния из пакетов в узле-адресате при многозадачном режиме работы
сети. (При наличии длинных сообщений пакетная обработка ускоряет
работу сети.)
Для алгоритмической реализации предложенной схемы вычисле-
ний необходимо решить многокритериальную задачу о назначениях,
эквивалентную проецированию вершин графов алгоритмов в узлы
графа сети, а также многокритериальную задачу маршрутизации по-
токов данных в сети [4, 5].
Функциональная модель сети.
Топологию сети будем пред-
ставлять в виде графа Г = (
V
,
U
),
имеющего ЯП-форму. Вдоль дуг
u
∈
U
графа Г расположены линии (каналы) передачи данных. В уз-
лах
l
∈
V
,
l
= 1, 2, …,
n
,
размещены «источники» и «стоки» передава-
емых потоков данных. Эти множества разбиты на подмножества
V
h
и
U
h
ярусов узлов и дуг, соединяющих
V
h
,
V
h
+1
.
Будем считать дву-
дольные графы Г
h
= (
V
h
∪
V
h
+1
,
U
h
),
h
= 1, 2, …,
H
– 1,
полными.
Доставка данных для каждой задачи с номером
k
= 1, 2, …,
K
осуществляется по маршрутам графа сети ,
k
j
L
соединяющим узлы, в
которых размещены задания
k-
го графа алгоритма. Максимальные по
включению маршруты, далее называемые
k
-
цепями, определяют про-
должительность решения
k-
й задачи. Маршруты
k
j
L
могут строиться
одновременно с решением задачи о назначениях, в которой выбира-
ются сетевые узлы для исполнения соответствующих заданий
k
-
й
задачи.
Эффективная и равновесная маршрутизация сети может быть по-
строена с помощью параллельного алгоритма [4, 5]. ЯП-форма графа
сети существенно упрощает его реализацию: диспетчеризация зада-
ний и маршрутизация потоков данных могут проводиться одновре-
менно, распространяясь от яруса к ярусу.