ВУЗ:
Составители:
127
9.6 Умножение матрицы на вектор при блочном разделении данных
Общее время умножения блоков матрицы А размером (
p
/
n
)×(
q
/
n
) на со-
ответствующие блоки вектора b можно записать, используя полученные ранее
формулы для ленточного разбиения по строкам и столбцам:
/ 2 / 1
s
T n p n q
.
Здесь
12
q/n - количество операций сложения и умножения в одной
строке блока при разбиении на
q
/
n
столбцов, а
p
/
n
- количество строк в ка-
ждом блоке.
С учетом последующего суммирования промежуточных векторов вычис-
лительные затраты увеличатся. Объединение промежуточных результатов мо-
жет быть выполнено с использованием каскадной схемы за qlog
2
итераций.
Приближенно эти затраты можно учесть, добавив слагаемое τ qlog
2
. При этом
оценка общих потерь с учетом потерь на коммуникации составит
2
/ 2 / 1 log /
s
T n p n q q w n p
.
Если количество строк матрицы кратно p, а количество столбцов – кратно
q, т. е. s=p·q, m=k·p и n=k·q, выражения для ускорения и эффективности можно
записать в виде
2
2 1
/ 2 / 1 log /
n n
R
n p n q q w n q
, (9.31)
2
2 1
2 log /
s
n n
E
n n q s q w n q
. (9.32)
Напомним, что здесь s=p·q.
В заключение укажем на возможный способ выбора блочной структуры
матрицы А. В данном случае увеличение числа блоков по горизонтали приво-
Страницы
- « первая
- ‹ предыдущая
- …
- 125
- 126
- 127
- 128
- 129
- …
- следующая ›
- последняя »
