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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

115
2 2
2 1
1
log log
s
n
n
E
s n n n
. (9.5)
Равенство (9.5) записано в предположении, что число процессоров, необ-
ходимых для реализации каскадной схемы, выбрано равным
2
n
s
. Нетрудно
заметить, что эффективность каскадной схемы падает с ростом числа слагае-
мых:
0
s
n
plim .
Указанный недостаток преодолевается применением модифицированной
каскадной схемы. Граф-схема соответствующего этой схеме алгоритма для
случая
k
n
2
,
s
k
2
, s=2 приведена на рис. 9.1. Здесь цифрами 1-16 обозначе-
ны операции ввода, а цифрами 17-31 – операции суммирования. В этом вариан-
те каскадной схемы вычисления проводятся в два этапа:
- на первом этапе все суммируемые значения подразделяются на nlog/n
2
групп по nlog
2
элементов в каждой группе, вычисления внутри группы вы-
полняются последовательно, а вычисления для групп осуществляются парал-
лельно на nns
2
log/
процессорах;
- на втором этапе к полученным nn
2
log/ суммам применяется каскадная схе-
ма.
На первом этапе требуется nlog
2
операций (при использовании
nlog/ns
2
процессоров). Для выполнения второго этапа необходимо
nlognlog/nlog
222
(9.6)
параллельных операций, выполняемых на
2
22
/nlog/ns
процессорах. С учетом неравенства (9.6) для описанной схемы при
nlog/ns
2
(9.7)
имеем
nlogT
s 2
2
. (9.8)

Страницы