Планирование распределения программных модулей по процессорам…
3
множество несвязанных между собой пучков нитей
s
P
,
где под ни-
тью понимается непрерывная последовательность программных мо-
дулей, расположенных на одном процессоре,
0,1,...,
s
q
.
После че-
го
вычислим ранние сроки окончания выполнения операторов, ис-
пользуя следующий алгоритм [11], модифицированный для учета
времени передачи информации:
1. Вычисляется
1
: 0,
j
t
где
: 1,...,
j
M
(
М
— размер матрицы
следования
S
).
2. Просматриваются строки матрицы
S
сверху вниз, выбирается
первая необработанная строка и осуществляется переход к следую-
щему шагу; если обработаны все строки, происходит переход в конец
алгоритма.
3. Если выбрана
j
-я строка, не содержащая единичных элементов,
вычисляется
1
:
,
j
j
t
p
где
j
p
— вес
j
-го оператора, и осуществляется
переход на шаг 5.
4. Если
j
-я строка содержит единичные элементы, то вычисляется
1
1
: max
,
q
j
j
j
t
t
p
где максимум берется по множеству времен
1
q
j
t
(
q
j
— номер эле-
мента
j
-й строки, равного единице). Если в множестве
1
q
j
t
есть ну-
левые элементы, то выполняется шаг 6, в противном случае выполня-
ется шаг 5.
5. Строка
j
метится как обработанная и исключается из рассмот-
рения. Осуществляется переход на шаг 2.
6. Так как найдены не все значения
1
q
j
t
, осуществляется поиск
следующей необработанной строки и переход на шаг 3.
Среди множеств
s
P
выделим множество
z
P
, нити которого
имеют максимальное число связей с другими нитями этого множе-
ства. В множестве
z
P
выберем нить
i
T
и будем выполнять ее на
вычислительном модуле с номером
w N
. Образуем последователь-
ность связей
i
-й нити с другими нитями множества
1 2
: , ,...,
i
i
i
z
d
P S S S
,
где верхний индекс обозначает номер нити, которой принадлежит
данная связь, а нижний — порядковый номер связи нити.
Для учета времени передачи данных между нитями пучка вначале
определим время передачи информации по связи на расстоянии, равном
единице:
1
2
,
,...,
.
i
i
i
d
t S t S t S
Определим также, какая нить из множе-
ства
z
P
соединена связью
i
m
S
, имеющей
max
,
0,1,...,
i
m
t S m
d
.
