Ю.М. Руденко
4
Предположим, что это будет нить
jm
T
. Связь
i
m
S
в нити
i
T
соединяет
оператор
y
с оператором
a
нити
jm
T
, при этом вес оператора
y
стано-
вится равным
, ,
i
y
y m
p p t S r i j
(2)
а весь оператора
a
, .
i
а
а m
p p t S r i j
(3)
В нити
i
T
все операторы, начиная с
y
, сдвинуты по оси времени
вправо на величину
, .
i
m
t S r i j
Аналогично в нити
jm
T
все опера-
торы, начиная с
a
, сдвинуты на величину
, .
i
m
t S r i j
Для нити
jm
T
выделяется вычислительный модуль с номером
1,
.
w w w N
Таким образом, нить
jm
T
будет выполняться на вычислительном
модуле с учетом информационных связей с другими нитями. Связь
i
m
S
исключается из дальнейшего планирования. Выполнение осталь-
ных нитей планируется аналогичным образом.
Пример.
Рассмотрим планирование распределения программных
модулей по узлам вычислительной системы, представленной
D
n
-графом [1] типа «Циркулянт»
G
(11, 1, 2, 5) для граф-схемы алго-
ритма решаемой задачи (рис. 1). Эта структура должна удовлетворять
следующим соотношениям:
1
, ,...,
,
n
n
D G N q q
1
0
...
1 2 ,
n
q
q N
где
N
— число вершин в графе (вершины нумеруются от 0
до
1
N
);
1
,...,
n
q q
— такие числа, образующие граф, что множество
1
, ,...,
n
N q q
имеет наибольший общий делитель, равный единице
.
Вершина
i
соединяется ребрами с вершинами, для которых спра-
ведлива следующая система модулярных соотношений:
1
mod ,
i q
N
………………
mod .
n
i q
N
На граф-схеме, приведенной на рис. 1, указаны время решения
соответствующего программного модуля и время передачи информа-
ции, заданные в относительных единицах.
