ВУЗ:
Составители:
122
Для построения оценок ускорения и эффективности с учетом затрат на вы-
числения и коммуникации предполагаем, что все (
1
2
n
) операций умножения
и сложения имеют одинаковую длительность τ, а вычислительная система од-
нородна, т.е. все процессоры обладают одинаковой производительностью. То-
гда временные затраты параллельного алгоритма, связанные непосредственно с
вычислениями, с учетом (9.15) составят
2 1
s
n
T n
s
. (9.16)
Если сеть передачи данных имеет структуру гиперкуба или полного графа,
операция сбора данных может быть выполнена за
slog
2
итераций. На первой
итерации взаимодействующие пары процессоров обмениваются сообщениями
объемом
snw , где w – размер одного элемента вектора в байтах. На второй
итерации этот объем увеличивается вдвое и оказывается равным
snw2 и т.д.
Общая длительность сбора данных
2 2
log log
1 1
2
1 1
2 / / log / 2 /
s s
i i
s
i i
T w n s s w n s
, (9.17)
где α– латентность сети передачи данных, β – пропускная способность сети.
Можно показать, что
2
2
log
log
1
1
2 2 1 1
s
s
i
i
s
. (9.18)
С учетом (9.16), (9.17) и (9.18) общее время выполнения параллельного ал-
горитма
2
2 1 log / 1 /
s
n
T n s w n s s
s
. (9.19)
Если n/s и slog
2
целые числа, в соответствии с (9.19) оценки для ускорения и
эффективности принимают вид
/ss/nwslognsn
nn
T
T
R
s
112
12
2
1
, (9.20)
Страницы
- « первая
- ‹ предыдущая
- …
- 120
- 121
- 122
- 123
- 124
- …
- следующая ›
- последняя »
