ВУЗ:
Составители:
125
Заметим, что здесь в соответствии с (9.22)
2 / 1
m n s
– оценка максимального числа операций (умножения и сложения) для вычисле-
ния всех элементов одного промежуточного m×1-вектора.
Количество суммируемых значений для каждого элемента результирующе-
го вектора на втором этапе равно числу промежуточных векторов, т.е. совпада-
ет с числом процессоров s. Максимальный размер блока результирующего век-
тора, закрепленный за одним процессором-получателем в общем случае равен
m/s. Следовательно, оценка числа операций на этом (втором) этапе равна
sm/s.
Оценим теперь ускорение и эффективность параллельного алгоритма с
учетом затрат времени на пересылку данных. Временные затраты на передачу
данных, необходимых процессору-получателю для вычисления одного блока
результирующего вектора составят
/ /
w m s
, (9.24)
где α – латентность сети передачи данных, β – пропускная способность сети, w
– размер элемента данных в байтах.
Общие временные затраты на коммуникации зависят от топологии сети.
Если имеется возможность одновременно отправлять и принимать сообщения
между любой парой процессоров, тогда временные затраты с учетом (9.24) со-
ставят
1
1 / /
s
T s w m s
. (9.25)
Если топология вычислительной системы представлена в виде гиперкуба,
передача всех данных может быть выполнена за slog
2
шагов, на каждом из ко-
торых максимально возможная (т.к. в общем случае размеры закрепляемых за
процессором блоков различаются) длина передаваемых и получаемых сообще-
ний
/
m s
элементов
2
2
log / /
s
T s w m s
. (9.26)
Страницы
- « первая
- ‹ предыдущая
- …
- 123
- 124
- 125
- 126
- 127
- …
- следующая ›
- последняя »
