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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

153
231232
1
22
2
njjj
s
T
n
i
n
i
s
. (11.10)
Применяя те же, что и ранее, элементарные формулы для подсчета сумм, полу-
чаем
55
6
30111541
2
23
nn
nnn
s
T
s
.
Если это допустимо, при больших n можно применять приближенную оценку:
55
6
15
3
21
223
nnnn
s
T
s
. (11.11)
Учтем теперь затраты на передачу данных. В прямом ходе на каждой ите-
рации для определения ведущей строки процессоры обмениваются найденными
в своей полосе максимальными значениями в столбце с исключаемой перемен-
ной. Для выполнения этой операции необходимо log
2
s шагов. С учетом количе-
ства итераций общие затраты на передачу максимальных значений
/wslogn)comm(T
s 2
1
1 , (11.12)
где
– латентность сети передачи данных,
– пропускная способность сети, и
w – размер пересылаемого элемента данных.
На каждой итерации прямого хода метода Гаусса выполняется также рас-
сылка выбранной ведущей строки. Сложность данной операции передачи дан-
ных определяется величиной
/wslogn)comm(T
s 2
2
1 . (11.13)
Наконец, при выполнении обратного хода алгоритма Гаусса на каждой
итерации осуществляется рассылка всем процессорам значения очередной вы-
численной неизвестной. Общее время, затрачиваемое на рассылку:
/wslogn)comm(T
s 2
3
1 . (11.14)
С учетом (11.9), (11.12), (11.13), (11.14) общая сложность параллельного
алгоритма Гаусса составит

Страницы