Лекция 6_2019

Часть 1. Умножение матрицы на вектор
Умножение матрицы на вектор
или
Задача умножения матрицы на вектор может быть сведена к выполнению m независимых операций умножения строк матрицы A на вектор b
В основу организации параллельных вычислений может быть положен принцип распараллеливания по данным

Способы распределения данных
Способы распределения данных из матрицы
горизонтальные полосы
вертикальные полосы
Чередующееся (цикличное) горизонтальное разбиение
блочное разбиение
Блочная схема
где: m – число строк матрицы А, n – размер вектора В, s – число процессоров,
k – число строк в блоке, v – номер строки внутри блока, i – номер блока

Способы распределения данных: ленточная схема
Непрерывное (последовательное) распределение
горизонтальные полосы
вертикальные полосы
Чередующееся (цикличное) горизонтальное разбиение

Последовательный алгоритм
Для выполнения матрично-векторного умножения необходимо выполнить m операций вычисления скалярного произведения
Трудоемкость вычислений имеет порядок O(mn).
// Последовательный алгоритм умножения матрицы на вектор
for ( i = 0; i < m; i++ ) {
c[i] = 0;
for ( j = 0; j < n; j++ ) {
c[i] += A[i][j]*b[j]
}
}
Базовая подзадача - минимальная задача, выполняемая всеми процессорами

Алгоритм 1: ленточная схема (разбиение матрицы по строкам)
Базовая подзадача - операция скалярного умножения одной строки матрицы на вектор:
Базовая подзадача для выполнения вычисления должна содержать:
строку матрицы А и копию вектора b.
После завершения вычислений каждая
базовая подзадача будет содержать один из
элементов вектора результата c
Для объединения результатов расчетов и
получения полного вектора c на каждом из
процессоров вычислительной системы
необходимо выполнить операцию
обобщенного сбора данных

Результаты вычислительных экспериментов

Алгоритм 2: ленточная схема (разбиение матрицы по столбцам)
Базовая подзадача - операция умножения столбца матрицы А на один из элементов вектора b:
Базовая подзадача для выполнения вычисления должна содержать
i-й столбец матрицы А и i-е элементы bi и ci векторов b и с
Каждая базовая задача i выполняет умножение своего столбца матрицы А на элемент bi, в итоге в каждой подзадаче получается вектор c'(i) промежуточных результатов
Для получения элементов результирующего вектора с подзадачи должны обменяться своими промежуточными данными

Схема информационного взаимодействия
Для получения элементов результирующего вектора с подзадачи должны обменяться своими промежуточными данными

Результаты вычислительных экспериментов

Алгоритм 3: блочная схема
Пусть:
количество процессоров p=s·q ,
количество строк матрицы является кратным s: m=k·s
количество столбцов является кратным q: l=n·q.
Подзадачи нумеруются индексами (i, j) располагаемых в подзадачах матричных блоков
Подзадачи выполняют умножение содержащегося в них блока матрицы A на блок вектора b
После перемножения блоков матрицы A и вектора b каждая подзадача (i,j) будет содержать вектор частичных результатов c'(i,j):

Алгоритм 3: блочная схема
Поэлементное суммирование векторов частичных результатов для каждой горизонтальной полосы (редукция) блоков матрицы A позволяет получить результирующий вектор c

Результаты вычислительных экспериментов
Общее количество базовых подзадач совпадает с числом процессоров p, p=s·q
Большое количество блоков по горизонтали (s) приводит к возрастанию числа итераций в операции редукции результатов блочного умножения,
увеличение размера блочной решетки по вертикали (q) повышает объем передаваемых данных между процессорами.

Сравнение алгоритмов

Часть 2. Умножение матриц
Умножение матриц:
или
Задача умножения матрицы на матрицу может быть сведена к выполнению m·n независимых операций умножения строк матрицы A на столбцы матрицы B
В основу организации параллельных вычислений может быть положен принцип распараллеливания по данным

Последовательный базовый алгоритм
double MatrixA[Size][Size];
double MatrixB[Size][Size];
double MatrixC[Size][Size];
int i,j,k;
...
for (i=0; i
for (j=0; j
{
MatrixC[i][j] = 0;
for (k=0; k
MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j];
}

Результаты вычислительных экспериментов
Эксперименты проводились на двухпроцессорном вычислитель-ном узле на базе четырех-ядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Micro-soft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.
Сравнение времени выполнения оптимизированной и неоптимизированной версий последовательного алгоритма умножения матриц
Графики зависимости времени выполнения оптимизированной и неоптимизированной версий последовательного алгоритма

Часть 2. Умножение матриц
×
=

Умножение матриц
×
=

Умножение матриц
Процесс хранит одну строку матрицы A и все столбцы матрицы B

Трудоемкость

Способы распределения данных
Способы распределения данных матрицы
горизонтальные полосы
вертикальные полосы
Чередующееся (цикличное) горизонтальное разбиение
блочное разбиение

Параллельный алгоритм 1: ленточная схема
Каждая подзадача содержит по одной строке матрицы А и одному столбцу матрицы В,
На каждой итерации проводится скалярное умножение содержащихся в подзадачах строк и столбцов, что приводит к получению соответствующих элементов результирующей матрицы С,
На каждой итерации каждая подзадача i, 0≤ i
После выполнения всех итераций алгоритма в каждой подзадаче поочередно окажутся все столбцы матрицы В.
По завершении итераций строки собираются в единую матрицу C.
Примечание. Для распределения подзадач между процессорами может быть использован любой способ, обеспечивающий эффективное представление кольцевой структуры информационного взаимодействия подзадач.

Параллельный алгоритм 1: ленточная схема
Топология информационных связей подзадач в виде кольцевой структуры:
1
2
3
4

Результаты вычислительных экспериментов

Параллельный алгоритм 1: ленточная схема
void MatrixMultiplicationMPI(double *&A, double *&B, double *&C, int &Size)
{
int dim = Size; int i, j, k, p, ind;
double temp;
MPI_Status Status;
int ProcPartSize = dim/ProcNum;
int ProcPartElem = ProcPartSize*dim;
double* bufA = new double[ProcPartElem];
double* bufB = new double[ProcPartElem];
double* bufC = new double[ProcPartElem];
int ProcPart = dim/ProcNum,
part = ProcPart*dim;
if (ProcRank == 0) { Flip(B, Size); }
MPI_Scatter(A, part, MPI_DOUBLE, bufA, part, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Scatter(B, part, MPI_DOUBLE, bufB, part, MPI_DOUBLE, 0, MPI_COMM_WORLD);
temp = 0.0;
for (i=0; i < ProcPartSize; i++)
{ for (j=0; j < ProcPartSize; j++)
{ for (k=0; k < dim; k++) temp += bufA[i*dim+k]*bufB[j*dim+k];
bufC[i*dim+j+ProcPartSize*ProcRank] = temp;
temp = 0.0;
}
}

int NextProc;
int PrevProc;
for (p=1; p < ProcNum; p++)
{ NextProc = ProcRank+1;
if (ProcRank == ProcNum-1) NextProc = 0;
PrevProc = ProcRank-1;
if (ProcRank == 0) PrevProc = ProcNum-1;
MPI_Sendrecv_replace(bufB, part, MPI_DOUBLE, NextProc, 0, PrevProc, 0, MPI_COMM_WORLD, &Status);
temp = 0.0;
for (i=0; i < ProcPartSize; i++)
{ for (j=0; j < ProcPartSize; j++)
{ for (k=0; k < dim; k++)
{ temp += bufA[i*dim+k]*bufB[j*dim+k];
}
if (ProcRank-p >= 0 ) ind = ProcRank-p;
else ind = (ProcNum-p+ProcRank);
bufC[i*dim+j+ind*ProcPartSize] = temp;
temp = 0.0;
}
}
}
MPI_Gather(bufC, ProcPartElem, MPI_DOUBLE, C, ProcPartElem, MPI_DOUBLE, 0, MPI_COMM_WORLD);
delete []bufA;
delete []bufB;
delete []bufC;
}

Параллельный алгоритм 2: ленточная схема
Идея: распределение данных в разбиении матриц A и B по строкам
Каждая подзадача содержит по одной строке матриц А и B,
На каждой итерации подзадачи выполняют поэлементное умножение векторов, в результате в каждой подзадаче получается строка частичных результатов для матрицы C,
На каждой итерации подзадача i, 0≤ i
После выполнения всех итераций алгоритма в каждой подзадаче поочередно окажутся все строки матрицы В

Параллельный алгоритм 2: ленточная схема

Параллельный алгоритм 2: ленточная схема
Алгоритм
Вначале производится рассылка в процесс ранга K элементов K-й строки матрицы A и элементов K-й строки матрицы B.
Элементы строки с, в которой будет содержаться соответствующая строка произведения AB, обнуляются.
Затем запускается цикл (число итераций равно N), в ходе которого выполняются два действия:
1) выполняется перемножение элементов строк матрицы A и матрицы B с одинаковыми номерами, и результаты добавляются к соответствующему элементу строки c;
2) выполняется циклическая пересылка строк матрицы B в соседние процессы (направление пересылки может быть произвольным: как по возрастанию рангов процессов, так и по их убыванию).
После завершения цикла в каждом процессе будет содержаться соответствующая строка произведения AB.
Останется переслать эти строки главному процессу.

Результаты вычислительных экспериментов

Простой блочный алгоритм

Простой блочный алгоритм
Вычисление произведения матриц в конечном поле с помощью простой параллельной схемы умножения.
Коэффициент ускорения равен 77%.

Метод Фокса
Распределение данных происходит по Блочной схеме
Базовая подзадача - процедура вычисления всех элементов одного из блоков матрицы С
Подзадача (i,j) отвечает за вычисление блока Cij, как результат, все подзадачи образуют прямоугольную решетку размером qxq,
В ходе вычислений в каждой подзадаче располагаются четыре матричных блока:
блок Cij матрицы C, вычисляемый подзадачей,
блок Aij матрицы A, размещаемый в подзадаче перед началом вычислений,
блоки A'ij, B'ij матриц A и B, получаемые подзадачей в ходе выполнения вычислений.

Параллельный алгоритм 2: метод Фокса
Выделение информационных зависимостей - для каждой итерации l, 0≤ l
блок Aij подзадачи (i,j) пересылается на все подзадачи той же строки i решетки; индекс j, определяющий положение подзадачи в строке, вычисляется в соответствии с выражением:
j = ( i+l ) mod q,
где mod есть операция получения остатка от целого деления;
полученные в результате пересылок блоки Aij’, Bij’ каждой подзадачи (i,j) перемножаются и прибавляются к блоку Cij
блоки Bij’ каждой подзадачи (i,j) пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

Схема информационного взаимодействия
Параллельный алгоритм 2: метод Фокса
Масштабирование и распределение подзадач по процессорам
Размеры блоков могут быть подобраны таким образом, чтобы общее количество базовых подзадач совпадало с числом процессоров p,
Наиболее эффективное выполнение метода Фокса может быть обеспечено при представлении множества имеющихся процессоров в виде квадратной решетки,
В этом случае можно осуществить непосредственное отображение набора подзадач на множество процессоров - базовую подзадачу (i,j) следует располагать на процессоре pi,j

Пример: метод Фокса
Итерация 1. Диагональные процессы раздают свои элементы матрицы А направо соседям, матрица В без изменений:

Пример: метод Фокса
Итерация 2. Верхнедиагональные процессы раздают свои элементы матрицы А направо соседям. В матрице В строки сдвигаются циклически вверх:
⇒

Пример: метод Фокса
х
=
Итерация 2.
Итерация 1.
Итерация 3.

Результаты вычислительных экспериментов

Алгоритм Кэннона при блочном разделении данных
Базовая подзадача - процедура вычисления всех элементов одного из блоков матрицы С
Подзадача (i,j) отвечает за вычисление блока Cij, все подзадачи образуют прямоугольную решетку размером qxq,
Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки в подзадачах могли бы быть перемножены без каких-либо дополнительных передач данных:
в каждую подзадачу (i,j) передаются блоки Aij, Bij,
для каждой строки i решетки подзадач блоки матрицы A сдвигаются на (i-1) позиций влево,
для каждого столбца j решетки подзадач блоки матрицы B сдвигаются на (j-1) позиций вверх,
процедуры передачи данных являются примером операции циклического сдвига

Перераспределение блоков исходных матриц
на начальном этапе выполнения метода
Параллельный алгоритм 3: метод Кэннона

Пример: метод Кэннона
Итерация 1. Циклический сдвиг по строкам: 0-я строка на 0 элементов влево
1-я строка на 1 элемент влево
2-я строка на 2 элемента влево
Циклический сдвиг по столбцам: 0-й на 0 элементов вверх
1-й на 1 элемент вверх
2-й на 2 элемента вверх
⇒
⇒
⇒

Пример: метод Фокса
х
=
Итерация 2.
Итерация 1.
Итерация 3.

Выделение информационных зависимостей
В результате начального распределения в каждой базовой подзадаче будут располагаться блоки, которые могут быть перемножены без дополнительных операций передачи данных,
Для получения всех последующих блоков после выполнения операции блочного умножения:
каждый блок матрицы A передается предшествующей подзадаче влево по строкам решетки подзадач,
каждый блок матрицы В передается предшествующей подзадаче вверх по столбцам решетки.
Параллельный алгоритм 3: метод Кэннона
Масштабирование и распределение подзадач по процессорам
Размер блоков может быть подобран таким образом, чтобы количество базовых подзадач совпадало с числом имеющихся процессоров,
Множество имеющихся процессоров представляется в виде квадратной решетки и размещение базовых подзадач (i,j) осуществляется на процессорах pi,j (соответствующих узлов процессорной решетки)

Результаты вычислительных экспериментов