Самарский государственный технический университет филиал в г. Сызрани
Электротехнический Факультет
Дисциплина
Методы параллельных
вычислений
Лекция 9.
Параллельные методы умножения матрицы на вектор
Тараканов А.В., доцент, к.п.н. Кафедра Информатики и систем управления
Содержание
Постановка задачи
Способы распределения данных
Последовательный алгоритм
Алгоритм 1 – ленточная схема, разделение матрицы по строкам
Алгоритм 2 – ленточная схема, разделение матрицы по столбцам
Алгоритм 3 – блочная схема
Заключение
2 из 43
Введение
Матрицы и матричные операции широко используются в разных областях приложений науки и техники
Матричные вычисления требуют выполнения вычислительно-трудоемких расчетов
Матричные операции предоставляют прекрасную возможность для демонстрации многих приемов и методов параллельного программирования
Матричные операции представляют собой классическую область применения параллельных вычислений
3 из 43
Постановка задачи
Умножение матрицы на вектор
или |
|
|
|
|
|
|
|
c A b |
|
|
|
|
|
|
|||||
|
|
|
a |
|
, |
a |
|
, |
|
..., |
a |
|
|
b |
|
||||
c |
0 |
|
|
0,0 |
0,1 |
|
0,n 1 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
0 |
|
||||
c1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b1 |
|
||
c |
m 1 |
|
a |
m 1,0 |
, a |
m 1,1 |
, |
..., |
a |
m 1,n |
1 |
b |
|
||||||
|
|
|
|
|
|
|
|
n 1 |
|
||||||||||
Задача умножения матрицы на вектор может быть сведена к выполнению m независимых операций умножения
строк матрицы A на вектор b
n
ci ai ,b ai jbj , 0 i m
j1
Воснову организации параллельных вычислений может
быть положен принцип распараллеливания по данным
4 из 43
Способы распределения данных: ленточная схема
Непрерывное (последовательное) распределение
горизонтальные полосы |
|
|
|
вертикальные полосы |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A ( A0 |
, A1,..., Ap 1 ) |
T |
, |
A ( A0 , A1,..., Ap 1 ), |
|||||||||
|
Ai ( i |
, i ,..., i |
|
) , |
|||||||||
A (a |
i |
, a |
i |
,..., a |
i |
|
), |
|
k 1 |
||||
i |
|
|
k 1 |
|
|
|
0 |
1 |
|
||||
|
|
0 1 |
|
|
|
|
|
i j il j, 0 j l, l n / p |
|||||
i j ik j, 0 j k, k m / p |
|||||||||||||
(ai , 0 i m, строки матрицы A) |
( i , 0 i т, столбцы матрицы A) |
||||||||||||
5 из 43
Способы распределения данных: ленточная схема
Чередующееся (цикличное) горизонтальное разбиение
A ( A0 , A2 ,..., Ap 1 )T , Ai (ai0 , ai1 ,..., aik 1 ),
ij i jp, 0 j k, k m / p
6 из 43
Способы распределения данных: блочная схема
|
A |
A |
...A |
|
|
|
|
00 |
02 |
0q 1 |
|
, |
|
A |
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
A |
A |
...A |
1q 1 |
|
|
|
s 11 |
s 12 |
s |
|
|
|
|
ai0 j0 |
ai0 j1 |
...ai0 jl 1 |
|
|
|
|
|
|
|
|
A |
|
... |
a |
, |
|
ij |
a |
|
a |
|
|
|
|
ik 1 j0 |
ik 1 j1 |
ik 1 jl 1 |
|
iv ik v, 0 v k, k m / s ju jl u, 0 u l, l n / q
7 из 43
Последовательный алгоритм
//Алгоритм 7.1
//Последовательный алгоритм умножения матрицы на вектор
for ( i = 0; i < m; i++ ) { c[i] = 0;
for ( j = 0; j < n; j++ ) { c[i] += A[i][j]*b[j]
}
}
Для выполнения матрично-векторного умножения необходимо выполнить m операций вычисления скалярного произведения
Трудоемкость вычислений имеет порядок O(mn).
8 из 44
Алгоритм 1: ленточная схема (разбиение матрицы по строкам)…
Распределение данных – ленточная схема (разбиение матрицы по строкам)
Базовая подзадача - операция скалярного умножения одной строки матрицы на вектор
n
ci ai ,b ai jbj , 0 i m
j 1
9 из 43
Алгоритм 1: ленточная схема (разбиение матрицы по строкам)…
Выделение информационных зависимостей
–Базовая подзадача для выполнения вычисления должна
содержать строку матрицы А и копию вектора b. |
|||||||||
После завершения вычислений |
1 |
|
|
|
x |
|
= |
|
|
|
|
|
|
|
|
||||
каждая базовая подзадача |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
будет содержать один из |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
x |
= |
|
|
||
элементов вектора результата c |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– Для объединения результатов |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
x |
= |
|
|
||
|
|
|
|
|
|
||||
расчетов и получения полного |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных
10 из 43