ВУЗ:
Составители:
133
Если размерность матрицы n оказывается больше, чем число процессоров
s, подзадачи можно укрупнить, объединив несколько соседних строк и столб-
цов перемножаемых матриц. При этом исходная матрица A разбивается на ряд
горизонтальных полос, а матрица B представляется в виде набора вертикальных
(для первого алгоритма) или горизонтальных (для второго алгоритма) полос.
Если n кратно s, размер полос k=n/s. Распределение подзадач между процессо-
рами следует осуществлять таким образом, чтобы подзадачи, являющиеся со-
седними в кольцевой топологии, располагались на процессорах, между кото-
рыми имеются прямые линии передачи данных.
10.3 Анализ эффективности алгоритмов
при ленточном разбиении матриц
Проведем теперь анализ эффективности описанных выше двух алгоритмов.
Время выполнения последовательного алгоритма
12
2
1
nnT , (10.2)
где τ – время выполнения одной элементарной скалярной операции. Выпишем
соотношения для подсчета вычислительных затрат при параллельной реализа-
ции алгоритма.
Первый вариант параллельного алгоритма – это наиболее часто используе-
мая, обычная схема вычислений, при которой, как уже указывалось выше, для
вычисления одного элемента необходимо
1
2
n
операций (n операций умноже-
ния и
1
n
операций сложения). А для вычисления всех элементов потребуется
12
2
nn операций.
Во втором варианте потребуется n
2
умножений и
1
nn сложений в каж-
дой строке. Для вычисления всех n строк матрицы С соответственно потребует-
ся
121
22
nnnnnn , т.е. вычислительная сложность обоих вариантов
одинакова. Различия в ускорении и эффективности вариантов могут иметь ме-
сто лишь за счет разных затрат на коммуникации. Построим эти оценки.
Страницы
- « первая
- ‹ предыдущая
- …
- 131
- 132
- 133
- 134
- 135
- …
- следующая ›
- последняя »
