Лекция 6_2019

1. Лекция 6

Параллельные алгоритмы умножения
матриц и векторов

2.

Часть 1. Умножение матрицы на вектор
Умножение матрицы на вектор
или
c A b
a0,1 , ..., a0,n 1 b0
c0 a0, 0 ,
...
b1
c1
b
c a
,
a
,
...,
a
m 1,1
m 1, n 1 n 1
m 1 m 1, 0
Задача умножения матрицы на вектор может быть сведена к
выполнению m независимых операций умножения строк
матрицы A на вектор b
n
ci ai , b ai j bj , 0 i m
j 1
В основу организации параллельных вычислений может
быть положен принцип распараллеливания по данным

3.

Способы распределения данных
Способы распределения данных из матрицы
горизонтальные полосы
вертикальные полосы
блочное разбиение
Чередующееся (цикличное)
горизонтальное разбиение
Блочная схема
A00
A
A
s 11
A02
...
As 12
... A0 q 1
,
... As 1q 1
ai0 j0
Aij
aik 1 j0
iv ik v, 0 v k , k m / s
ai0 j1
...
aik 1 j1
...ai0 j
l 1
,
aik 1 jl 1
m = 8, s – 4, k = 8/4=2
Тогда