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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

134
Если
s
/
n
- целое число, время выполнения вычислений параллельного ал-
горитма, с учетом приведенных выше соотношений, составит
12
2
ns/nT
s
, (10.3)
где, как и ранее, τ – время выполнения одной скалярной операции.
Будем предполагать, что все операции передачи данных между процессо-
рами, соединенными в «кольцо», в ходе одной итерации алгоритма могут быть
выполнены параллельно. Объем передаваемых данных между процессорами
определяется размером полос и составляет n/s строк или столбцов длины n.
Общее количество параллельных операций передачи сообщений на единицу
меньше числа итераций алгоритма (на последней итерации передача данных не
является обязательной). Таким образом, оценка затрат на передачу определяет-
ся как
/1 snnwsT
s
, (10.4)
где α– латентность, β – пропускная способность сети передачи данных, а w –
размер элемента матрицы в байтах.
С учетом полученных соотношений достижимое ускорение
/112/
12
2
2
snnwsnsn
nn
R
, (10.5)
а эффективность
2
2
2 1
2 1 1 /
s
n n
E
n n s s w n n s
. (10.6)
Из полученных соотношений видно, что для сохранения эффективности, уве-
личение числа процессоров оправдано только в случае соответственного роста
вычислительной сложности задачи.
Тот факт, что в обоих алгоритмах отсутствуют операции, которые не могут
быть распараллелены и могут выполняться только последовательно, проявляет-
ся в том, что вычисленное по указанным формулам максимально достижимое

Страницы