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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

152
тей для
s/in
еще не обработанных строк из числа закрепленных за ним
s
/
n
строк. Поскольку для каждой правой части выполняются 2 операции (ум-
ножение и вычитание), общее число операций, необходимых для обновления
всех правых частей, составит
2
2
0
2
n
s
i
T
s
.
Кроме обновления правых частей на каждой итерации обратного хода один
из процессоров выполняет операцию деления для определения очередной пе-
ременной. При этом остальные процессоры, конечно, простаивают, но эти n
операций (по числу определяемых переменных) необходимо включить в общие
вычислительные затраты:
2
2
0
2
n
s
i
n i
T n
s
.
Наконец, для построения приближенных достаточных оценок, как и ранее,
отменим операцию округления и добавим
12
n операций, которые могут
дополнительно иметь место на всех
12
n итерациях обновления правых час-
тей, если в результате округления на каждой добавляется одна строка. Тогда
оценка сверху общих вычислительных затрат для реализации обратного хода
составит
232
1
122
2
0
2
0
2
nin
s
nn
s
in
T
n
i
n
i
s
. (11.8)
С учетом (11.7), (11.8) суммарные затраты на реализацию прямого и об-
ратного хода составят
231232
1
2
0
2
0
2
nininin
s
T
n
i
n
i
s
. (11.9)
Как и ранее осуществим замену
i
n
j
, при этом пределы суммирования при
записи слагаемых в обратном порядке будут n,j 2 . Тогда (11.9) перепишется
в виде

Страницы