Лекции по параллельным вычислениям. Гергель В.П - 94 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

94
m
i
jm
t,ft,,...,F
1
1
, (7.4)
где
.случаепротивномв
,,ttпри
t,f
jij
j
0
1
Значение функции F в каждый момент времени t совпадает с числом одновре-
менно (параллельно) выполняемых в этот момент операторов. Например, по
диаграмме, показанной на рис. 7.2, можно построить функцию плотности за-
грузки
t,,,,,,,,F 96874332 , которая при t=1 равна 2, при t=2 равна 3, при t=7
равна 2 и т.д.
Предположим теперь, что граф, дополненный транзитивными связями со-
держит l полных множеств ВНО (каждая пара таких множеств может иметь не-
пустое пересечение). Обозначим l,i,r
i
1 , число операторов, образующих i-е
полное множество, и найдем
l
r,...,rmaxR
1
.
Тогда
t,,...,FmaxR
m
,...,
m
1
1
,
т.к. возможно такое распределение выполняемых операторов, когда на каком-то
отрезке времени выполняются все операторы, входящие в полное множество
ВНО с числом операторов R.
Из этого следует, что минимальное число процессоров одинаковой специа-
лизации и производительности, способных выполнить данный алгоритм за вре-
мя
кр
TT
, не превышает
l
r,...,rmaxR
1
,
где l,i,r
i
1 - число операторов, входящих в i-е полное множество ВНО, со-
ставленное по соответствующему этому алгоритму информационному графу.

Страницы