Лекции по параллельным вычислениям. Гергель В.П - 119 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

119
9.3 Умножение матрицы на вектор, способы декомпозиции
Операция умножения матрицы на вектор – одна из самых часто встречаю-
щихся в самых различных задачах. Поэтому многие стандартные библиотеки
программ содержат процедуры для выполнения матричных операций. Тем не
менее изучение основных схем их распараллеливания полезно, т.к. во-первых,
это дает необходимые сведения для обоснованного выбора наиболее подходя-
щей для системы с данной топологией процедуры из имеющегося набора стан-
дартных, во-вторых, матричные операции являются классическими примерами
для демонстрации многих приемов и методов распараллеливания задач. Далее
для общности будем полагать, что матрицы являются плотными, т.е. число ну-
левых элементов в них мало по сравнению с общим количеством элементов
матриц.
При распараллеливании задачи умножения матрицы на вектор обычно ис-
пользуются два типа декомпозиции, показанные на рис. 5.3:
1. Ленточное разбиение – на полосы по горизонтали или вертикали.
2. Разбиение данных на прямоугольные фрагменты (блочное разделение).
При ленточном разбиении каждому процессору выделяется некоторое ко-
личество (обычно подряд идущих) строк или столбцов. При этом в случае гори-
зонтального разбиения матрица A представляется в виде
T
s
A,...,A,AA
110
,
110
ikiii
a,...,a,aA ,
s
/
m
k
,
k
j
,
j
ij
0
,
где
mi,a,...,a,aa
n,i,i,ii
0
21
– i-я строка матрицы A (предполагается, что
количество строк m кратно числу процессоров: m=k·s). Иногда с точки зрения
балансировки процессоров для конкретной топологии более предпочтительным
является циклическое чередование строк или столбцов. В этом случае
s
/
m
k
,
k
j
,
js
i
ij
0
.
На рис. 9.3 в качестве примера приведены граф-схема и временная диа-
грамма параллельного алгоритма умножения матрицы на вектор на 8 процессо-

Страницы