ВУЗ:
Составители:
139
матриц А и В и прибавляет результаты умножения к текущему значению соот-
ветствующего блока матрицы C. При сделанных предположениях общее коли-
чество операций имеет порядок n
3
/s. Поскольку в данном алгоритме отсутству-
ют вычисления, которые могут выполняться только последовательно, при от-
сутствии потерь на коммуникации могут достигаться показатели ускорения и
эффективности s и 1 соответственно.
Подсчитаем теперь количество вычислительных операций параллельного
алгоритма с учетом затрат на выполнение операций передачи данных между
процессорами. Сложность выполнения скалярного умножения строки блока
матрицы A на столбец блока матрицы В можно оценить как 2(n/q) –1. Количе-
ство строк и столбцов в блоках равно n/q. Следовательно, вычислительная
сложность блочного умножения равна (n
2
/s)(2n/q–1). Для сложения блоков тре-
буется n
2
/s операций. С учетом сказанного время выполнения всех операций ал-
горитма
snqnsnqT
s
22
1/2 , (10.7)
где τ – время выполнения одной скалярной операции.
Оценим теперь затраты на выполнение операций передачи данных между
процессорами. На каждой итерации перед умножением блоков один из процес-
соров каждой строки решетки процессоров рассылает свой блок матрицы A ос-
тальным процессорам своей строки. При топологии сети в виде гиперкуба или
полного графа выполнение этой операции может быть обеспечено за log
2
q ша-
гов, а объем передаваемых блоков равен n
2
/p. При этом время выполнения опе-
рации передачи блоков матрицы A составит
/snwqlogT
s
2
2
, (10.8)
где – латентность, β – пропускная способность сети передачи данных, а w –
размер элемента матрицы в байтах.
Если топология строк решетки процессоров – кольцо, выражение для
оценки времени передачи блоков матрицы A принимает вид
Страницы
- « первая
- ‹ предыдущая
- …
- 137
- 138
- 139
- 140
- 141
- …
- следующая ›
- последняя »
