ВУЗ:
Составители:
3 Векторно-ориентированные алгоритмы LU-разложения
Для приведенного примера 3.2 алгоритма сдваивания в задаче сложения
n чисел средняя степень параллелизма равна
1
q
n
2
+
n
4
+ ··· + 1
=
2
q
− 1
q
=
n − 1
log n
,
тогда как в предыдущем примере 3.1 средняя степе нь параллелизма мак-
симальна. Этот алгоритм (3.3) обладает «идеальным» параллелизмом, в то
время как для алгоритма на рис. 3.3 средняя степень параллелизма в log n
раз меньше идеальной.
3.3 Параллельное умножение матрицы на вектор
Пусть A — матрица размера (m × n), а x — вектор длины n. Тогда
Ax =
(a
1
, x)
···
(a
m
, x)
, (3.4)
где a
i
— i-я ст рока матрицы A, а (a
i
, x) — обычное скаля рное произведение
векторов a
i
и x. Каждое из m имеющихся здесь скалярных произведений,
как известно, тре бует суммирования n поэлеме нтных произведений a
ij
x
j
.
Как показано в предыдущем подразделе, такое с ум м ирование можно распа-
раллеливать сдваиванием, но такой параллелизм вычисления каждого от-
дельного скалярного произведения так или иначе неидеален. Однако m ска-
лярных произведений в (3.4) можно вычислять параллельно. Другой способ
умножения матрицы на вектор дается формулой
Ax =
n
X
j=1
x
j
a
j
, (3.5)
где a
j
теперь обозначает j-й с т олбец матрицы A.
Различие представлений (3.4) и (3.5) можно рассматривать ка к различие
двух способов доступа к данным в памяти, что показывают две программы
на рис. 3.4. Программа слева на рис. 3.4 реализует метод (3.4), тогда как
программа справа реализует метод (3.5), и различие здес ь только в порядке
индексов для циклов. Алгоритм, основанный на представлении (3.5), запи-
сывается так:
y = 0, для j от 1 до n выполнить y = y + x
j
a
j
.
58
Страницы
- « первая
- ‹ предыдущая
- …
- 56
- 57
- 58
- 59
- 60
- …
- следующая ›
- последняя »
