Теория и практика параллельных вычислений
Программная реализация
Рассмотрим возможный вариант параллельной реализации метода Гаусса для решения систем линейных уравнений. Следует отметить, что для получения более простого вида программы для разделения матрицы между процессами используется ленточная последовательная схема (полосы матрицы образуют последовательные наборы соседних строк матрицы). В описании программы реализация отдельных модулей не приводится, если их отсутствие не оказывает влияния на понимание общей схемы параллельных вычислений.
1. Главная функция программы. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы.
Пример 8.1.
(html, txt)
Следует пояснить использование дополнительных массивов. Элементы массива pParallelPivotPos определяют номера строк матрицы, выбираемых в качестве ведущих, по итерациям прямого хода метода Гаусса. Именно в этом порядке должны выполняться затем итерации обратного хода для определения значений неизвестных системы линейных уравнений. Массив pParallelPivotPos является глобальным, и любое его изменение в одном из процессов требует выполнения операции рассылки измененных данных всем остальным процессам программы.
Элементы массива pProcPivotIter определяют номера итераций прямого хода метода Гаусса, на которых строки процесса использовались в качестве ведущих (т.е. строка i процесса выбиралась ведущей на итерации pProcPivotIter[i]). Начальное значение элементов массива устанавливается нулевым, и, тем самым, нулевое значение элемента массива pProcPivotIter[i] является признаком того, что строка i процесса все еще подлежит обработке. Кроме того, важно отметить, что запоминаемые в элементах массива pProcPivotIter номера итераций дополнительно означают и номера неизвестных, для определения которых будут использованы соответствующие строки уравнения. Массив pProcPivotIter является локальным для каждого процесса.
Функция ProcessInitialization определяет исходные данные решаемой задачи (число неизвестных), выделяет память для хранения данных, осуществляет ввод матрицы коэффициентов системы линейных уравнений и вектора правых частей (или формирует эти данные при помощи какого-либо датчика случайных чисел).
Функция DataDistribution реализует распределение матрицы линейной системы и вектора правых частей между процессорами вычислительной системы.
Функция ResultCollection осуществляет сбор со всех процессов отдельных частей вектора неизвестных.
Функция ProcessTermination выполняет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных.
Реализация всех перечисленных функций может быть выполнена по аналогии с ранее рассмотренными примерами и предоставляется читателю в качестве самостоятельного упражнения.
2. Функция ParallelResultCalculation. Реализует логику работы параллельного алгоритма Гаусса, последовательно вызывает функции, выполняющие прямой и обратный ход метода.
// Функция для параллельного выполнения метода Гаусса void ParallelResultCalculation (double* pProcRows, double* pProcVector, double* pProcResult, int Size, int RowNum) { ParallelGaussianElimination (pProcRows, pProcVector, Size, RowNum); ParallelBackSubstitution (pProcRows, pProcVector, pProcResult, Size, RowNum); }
3. Функция ParallelGaussianElimination. Функция выполняет параллельный вариант прямого хода алгоритма Гаусса.
Пример 8.2.
(html, txt)
Функция ParallelEliminateColumns проводит вычитание ведущей строки из строк процесса, которые еще не использовались в качестве ведущих (т.е. для которых элементы массива pProcPivotIter равны нулю).
4. Функция ParallelBackSubstitution. Функция реализует параллельный вариант обратного хода Гаусса.
Пример 8.3.
(html, txt)
Функция FindBackPivotRow определяет строку, из которой можно вычислить значение очередного элемента результирующего вектора. Номер этой строки хранится в массиве pParallelPivotIter. По номеру функция FindBackPivotRow определяет номер процесса, на котором эта строка хранится, и номер этой строки в полосе pProcRows этого процесса.
