Параллельные методы умножения матрицы на вектор (стр. 2 из 2)
ВЫВОД:
Замедление работы программы при использовании параллельного алгоритма (библиотека OpenMP) можно объяснить следующим отчётом профилировщика (см. Рисунок 6).
Рисунок 6. Сравнение данных профилировщика последовательной и параллельной программ
Как видно, значительное время при выполнении программы затрачивается в библиотеке libiomp5md.dll.
2. Умножение матрицы на вектор при разделении данных по столбцам.
Базовая подзадача - операция умножения столбца матрицы
на один из элементов вектора 
. Для организации вычислений в этом случае каждая базовая подзадача 
, должна иметь доступ к i-у столбцу матрицы .Каждая базовая задача
выполняет умножение своего столбца матрицы на элемент 
, в итоге в каждой подзадаче получается вектор 
промежуточных результатов. Для получения элементов результирующего вектора с необходимо просуммировать вектора , которые были получены каждой подзадачей. 
Рисунок 7. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор с использованием разбиения матрицы по столбцам.
При выполнении параллельного алгоритма умножения матрицы на вектор, основанного на вертикальном разделении матрицы, выполняется больше арифметических операций, т.к. на каждой итерации внешнего цикла после вычисления каждым потоком своей частичной суммы необходимо выполнить редукцию полученных результатов. Сложность выполнения операции редукции –
. После выполнения редукции данных, необходимо запомнить результат в очередной элемент результирующего вектора. Таким образом, время вычислений для данного алгоритма определяется формулой: 
.На выполнение подкачек данных в кэш тоже тратится некоторое время. Пусть
- накладные расходы на организацию параллельности на каждой итерации. Тогда суммарные накладные расходы составляют: 
.Таким образом, время выполнения параллельного алгоритма умножения матрицы на вектор, основанного на вертикальном разделении матрицы, может быть вычислено по формуле:
.void ParallelResultCalculation_columns(double* pMatrix, double* pVector, double* pResult, int Size) {
int i, j; // Loop variables
double IterGlobalSum = 0;
for (i=0; i<Size; i++) {
IterGlobalSum = 0;
#pragma omp parallel for reduction(+:IterGlobalSum)
for (j=0; j<Size; j++)
IterGlobalSum += pMatrix[i*Size+j]*pVector[j];
pResult[i] = IterGlobalSum;
}
}
Результаты вычислительных экспериментов приведены в таблице.
Таблица 3. Результаты вычислительных экспериментов для параллельного алгоритма умножения
матрицы на вектор при ленточной схеме разделении данных по столбцам.
Рисунок 8. Зависимость ускорения от количества исходных данных при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на ленточном вертикальном разбиении матрицы
Для нахождения
воспользуемся методом наименьших квадратов. Будем минимизировать квадрат разницы между экспериментальными и теоретическими значениями времени, при этом будет выступать в качестве подгоночного параметра. Воспользуемся функцией поиска решений в Excel.Будем минимизировать величину
Таким образом, получаем
= 5,27565E-06 с=5,3 мкс 
Рисунок 9. График зависимости экспериментального и теоретического времени выполнения параллельного алгоритма от объёма исходных данных при использовании двух потоков (ленточное разбиение матрицы по столбцам)
- Умножение матрицы на вектор при блочном разделении данных.
При блочном разделении матрица делится на прямоугольные наборы элементов – при этом, как правило, используется разделение на непрерывной основе. Пусть количество процессоров (ядер) составляет
, количество строк матрицы является кратным s, а количество столбцов – кратным q, то есть 
и 
.После перемножения блоков матрицы A и вектора b каждая подзадача (i,j) будет содержать вектор частичных результатов c'(i,j), определяемый в соответствии с выражениями:
Рисунок 10. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор с использованием блочного разделения данных.
Будем предполагать, что число блоков матрицы А совпадает по горизонтали и вертикали, т.е. s=q.
Для обозначения числа потоков будем использовать переменную π=q2. Для эффективного выполнения алгоритма число базовых подзадач должно совпадать с числом выделенных потоков.
Возьмём число потоков π=4.
Воспользуемся алгоритмом вычисления, основанном на использовании функций библиотеки OpenMP. В данном алгоритме используется вложенный параллелизм.
Для задания количества потоков будет использоваться переменная NestedThreadsNum.
void ParallelResultCalculation_blocks(double* pMatrix, double* pVector, double* pResult,
int Size) {
int NestedThreadsNum = 2;
omp_set_num_threads(NestedThreadsNum);
omp_set_nested(true);
#pragma omp parallel for
for (int i=0; i<Size; i++) {
double ThreadResult = 0;
#pragma omp parallel for reduction(+:ThreadResult)
for (int j=0; j<Size; j++)
ThreadResult += pMatrix[i*Size+j]*pVector[j];
pResult[i] = ThreadResult;
}
}
При анализе эффективности данного алгоритма воспользуемся следующими формулами.
Время выполнения вычислений ограничено сверху величиной: (количество вычислительных элементов совпадает с числом потоков, т.е. p=π)
При выполнении вычислений, «внутренние» параллельные секции создаются и закрываются много раз, кроме того, дополнительное время тратится на синхронизацию и выполнение операции редукции. Каждый поток создаёт параллельные секции
раз. Время выполнения алгоритма может быть вычислено по формуле: 
Результаты вычислительных экспериментов при блочном разделении данных приведены в таблице 5.
Таблица 5. Результаты вычислительных экспериментов для параллельного алгоритма умножения матрицы на вектор при блочной схеме разделении данных.
Рисунок 11. Зависимость ускорения от количества исходных данных при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на блочном разбиении матрицы
Рисунок 12. График зависимости экспериментального и теоретического времени выполнения параллельного алгоритма от объема исходных данных при использовании четырёх потоков при блочном разбиении матрицы
Вывод
В результате проделанной работы, мы пришли к выводу, что среди параллельных алгоритмов умножения матрицы на вектор, самым быстрым оказался алгоритм, основанный на разделении матрицы по строкам. Однако существенного ускорения за счёт распараллеливания достигнуть не удалось. Это связано с тем, что значительное время расходуется на ожидания внутри библиотек OpenMP.