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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

157
обрабатываемые векторы дублируются. Вычислительная сложность последова-
тельного алгоритма дается соотношением (11.12). Определим вычислительные
затраты при параллельной реализации метода сопряженных градиентов.
Вычислительная сложность параллельного умножения матрицы на вектор
при ленточном разделении по строкам
1
2 / 2 1
s
T n n s n
.
С учетом дополнительных операций над векторами при условии их дублирова-
ния общая вычислительная сложность параллельного алгоритма составит
1
(2 / 2 1 13 )
s
T n n s n n
.
Если
sn / – целое число, ускорение и эффективность соответственно
2
23
23
13
24
132
n
s
nn
nn
R
,
223
23
13
2
4
132
sn
n
n
nn
E
s
.
С учетом информационного взаимодействия процессоров при умножении
матрицы на вектор сложность параллельных вычислений
3 2
4 2 / 13 2 log / 1 /
s
T n n s n n s w n s s
.
Тогда окончательно оценки ускорения и эффективности
3 2
3 2
2
2 13
4 2
13 2 log / 1 /
n n
R
n n
n n s w n s s
s
, (11.13)
3 2
3 2 2
2 13
4 2 13 2 log / 1 /
s
n n
E
n n sn sn s w n s s
. (11.14)
Представляет интерес проанализировать предельно достижимые в этом ме-
тоде показатели ускорения и эффективности. Из (11.13) легко установить, что
если потери на передачу данных отсутствуют, то при сравнительно малом n и

Страницы