Реализация параллельного алгоритма

Разработаем параллельную программу для умножения матрицы на вектор при ленточной схеме разделения данных по строкам. Напомним, что для организации параллельных вычислений

предполагается использование многопроцессорных систем с общей памятью – тем самым, для

разработки можно применить технологию OpenMP. В этом случае преобразовать разработанную ранее последовательную программу матрично-векторного умножения сравнительно просто – для этого достаточно добавить директиву parallel for в функцию SerialResultCalculation (назовем новый вариант функции ParallelResultCaclualtion):

// Function for calculating matrix-vector multiplication

void ParallelResultCalculation (double* pMatrix, double* pVector,

double* pResult, int Size) {

int i, j; // Loop variables

#pragma omp paralell for private (j)

for (i=0; i<Size; i++) {

for (j=0; j<Size; j++)

pResult[i] += pMatrix[i*Size+j]*pVector[j];

}

}

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

Параллельные области в данной функции задаются директивой parallel for. Компилятор,

поддерживающий технологию OpenMP, разделяет выполнение итераций цикла между несколькими потоками параллельной программы, количество которых обычно совпадает с числом вычислительных элементов (процессоров и/или ядер) в вычислительной системе. Параметр директивы private указывает необходимость создания отдельных копий для задаваемых переменных для каждого потока, данные копии могут использоваться в потоках независимо друг от друга.

Следует отметить, что матрица pMatrix и вектора pVector и pResult являются общими для всех потоков. Однако элементы матрицы pMatrix и вектора pVector используются только на чтение, а элементы вектора pResult между потоками разделяются без пересечения. Тем самым использование общих данных является корректным и организация параллельных вычислений выполнена правильно, без ошибок.

Проверка правильности параллельной программы

Для проверки корректности работы параллельных программ разработайте функцию TestResult, которая сравнит результаты последовательного и параллельного алгоритмов. Для выполнения последовательного алгоритма можно использовать функцию SerailResultCalculation, разработанную в упражнении 2. Результат работы этой функции можно сохранить, например, в векторе pSerialResult, а затем поэлементно сравнить этот вектор с вектором pResult, полученным при помощи параллельного алгоритма. Далее представлен возможный вариант такой функции:

 

// Testing the result of parallel matrix-vector multiplication

void TestResult(double* pMatrix, double* pVector, double* pResult,

int Size) {

// Buffer for storing the result of serial matrix-vector multiplication

double* pSerialResult;

int equal = 0; // Flag, that shows wheather the vectors are identical

int i; // Loop variable

pSerialResult = new double [Size];

SerialResultCalculation(pMatrix, pVector, pSerialResult, Size);

for (i=0; i<Size; i++) {

if (pResult[i] != pSerialResult[i])

equal = 1;

}

if (equal == 1)

printf("The results of serial and parallel algorithms "

"are NOT identical. Check your code.");

else

printf("The results of serial and parallel algorithms are "

"identical.");

delete [] pSerialResult;

}

Результатом работы представленной функции является печать диагностического сообщения. Используя эту функцию, можно проверять результат работы параллельных алгоритмов независимо от того, насколько велики исходные объекты при любых значениях исходных данных. Так же функция не зависит от варианта используемого алгоритма и способа перемножения матрицы на вектор. Вместо функции DummyDataInitialization, которая генерирует исходные объекты простого вида, вызовите функцию RandomDataInitialization, которая генерирует матрицу и вектор при помощи датчика случайных чисел. Скомпилируйте и запустите приложение. Задавайте различные объемы исходных данных. Убедитесь в том, что приложение работает корректно.