Выполнение параллельного алгоритма Фокса

За выполнение параллельного алгоритма Фокса матричного умножения отвечает функция ParallelResultCalculation, в качестве аргументов которой выступают все матричные блоки и размер этих блоков.

Согласно схеме параллельных вычислений, описанной в упражнении 3, для выполнения матричного умножения с помощью алгоритма Фокса необходимо выполнить GridSize итераций, каждая из которых состоит из выполнения трех действий:

• рассылка блока матрицы А по строке процессорной решетки (функция ABlockCommunication),

• выполнение умножения матричных блоков (функция SerialResultCalculation),

• циклический сдвиг блоков матрицы В вдоль столбца процессорной решетки (функция ВBlockCommunication).

Итак, в начале каждой итерации iter алгоритма для каждой строки процессной решетки выбирается процесс, который будет рассылать свой блок матрицы А по процессам соотвествующей строки решетки. Номер этого процесса Pivot в строке определяется в соответствии с выражением:

Pivot = (i+iter) mod GridSize,

где i – номер строки процессорной решетки, для которой определяется номер рассылающего процесса (для каждого процесса номер строки, в которой он расположен, можно определить, обратившись к первому значению в массиве GridCoords), а операция mod есть операция вычисления остатка от деления. Таким образом, на каждой итерации рассылающим назначается процесс, у которого значение второй координаты GridCoords совпадает с Pivot. После того, как номер рассылающего процесса определен, необходимо выполнить широковещательную рассылку блока матрицы А по строке. Для этого использована функция MPI_Bcast в рамках коммуникатора RowComm. Здесь используется дополнительный блок матрицы А: первый блок pMatrixAblock хранит тот блок матрицы, который был помещен на данный процесс перед началом вычислений, а блок pAblock хранит тот блок матрицы, который принимает участие в умножении на данной итерации алгоритма. Перед выполнением широковещательной рассылки содержимое блока pMatrixAblock копируется в буфер pAblock, а затем буфер pAblock рассылается на все процессы строки.

После выполнения умножения матричных блоков нужно осуществить циклический сдвиг блоков матрицы В вдоль столбцов процессорной решетки. Такой сдвиг можно выполнить несколькими разными способами. Наиболее очевидный подход состоит в организации последовательностей передачи и приема матричных блоков при помощи функций MPI_Send и MPI_Receive. Сложность здесь состоит в том, чтобы организовать эту последовательность таким образом, чтобы не возникло тупиковых ситуаций, то есть таких ситуаций, когда один процесс ждет приема сообщения от другого процесса, тот, в свою очередь, от третьего, и так далее.

Для организации циклического сдвига блоков pBblock матрицы В используется функция MPI_Sendrecv_replace. Каждый процесс посылает сообщение предыдущему процессу того же столбца процессорной решетки и принимает сообщение от следующего процесса. Процесс, расположенный в нулевой строке процессорной решетки посылает свой блок процессу, расположенному в последней строке (строке с номером GridSize-1).

После того, как блоки матрицы A разосланы, необходимо выполнить перемножение блоков pAblock и pBblock, и результат прибавить к блоку pCblock. Для умножения матричных блоков на каждом процессе необходимо выполнить последовательный алгоритм матричного умножения над матрицами pAblock и pBblock размера BlockSize × BlockSize, для чего используется функция SerialResultCalculation.

Сбор результатов

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

Для сбора результирующей матрицы использована функция MPI_Gather библиотеки MPI. Эта функция собирает данные со всех процессов в коммуникаторе на одном процессе. Действия, выполняемые этой функцией, противоположны действиям функции MPI_Scatter.

Процедура сбора результирующей матрицы C реализуется непосредственно в функции ResultCollection.