1. Создание виртуальной декартовой топологии

Согласно схеме параллельных вычислений, описанной выше, для эффективного выполнения алгоритма Фокса необходимо организовать доступные процессы MPI-программы в виртуальную топологию в виде двумерной квадратной решетки. Это возможно только в том случае, когда число доступных процессов является полным квадратом, т.е. ProcNum = GridSize×GridSize, где GridSize – размером решетки.

Функция CreateGridCommunicators создает коммуникатор в виде двумерной квадратной решетки, определяет координаты каждого процесса в этой решетке, а также создает коммуникаторы отдельно для каждой строки и каждого столбца.

Для непосредственного создания декартовой топологии (решетки) для данного коммуникатора с декартовой топологией процессов в библиотеке MPI предназначена функция MPI_Cart_create.

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

Для создания коммуникаторов для каждой строки и каждого столбца процессорной решетки используется библиотечная MPI-функция MPI_Cart_sub, позволяющая разделить решетку на подрешетки.

2. Определение размеров объектов и ввод исходных данных

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

Для определения элементов исходных матриц используются функции DummyDataInitialization и RandomDataInitialization. Превая используется для тестирования, вторая – для проведения вычислительных экспериментов.

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

3. Завершение процесса вычислений

Чтобы корректно завершить процесс вычислений, необходимо освободить память, выделенную динамически в процессе выполнения программы: для хранения исходных матриц pAMatrix и pBMatrix, для хранения результирующей матрицы pCMatrix, для хранения четырех матричных блоков pMatrixAblock, pAblock, pBblock, pCblock на всех процессах. Для этого предназначена функция ProcessTermination.

4. Распределение данных между процессами

Согласно схеме параллельных вычислений, исходные матрицы, которые нужно перемножить, расположены на ведущем процессе. Ведущий процесс – процесс с рангом 0, расположен в левом верхнем углу процессорной решетки.

Нужно распределить матрицы поблочно между процессами так, чтобы блоки A_ij и B_ij были распределены процессу, расположенному на пересечении i-ой строки и j-ого столбца процессорной решетки. Матрицы и матричные блоки хранятся в одномерных массивах построчно. Блок матрицы не хранится непрерывной последовательностью элементов в массиве хранения матрицы, следовательно, для распределения по блокам невозможно выполнить с использованием стандартных типов данных библиотеки MPI.

Для организации передачи блоков в рамках одной и той же коммуникационной операции можно сформировать средствами MPI производный тип данных. Однако в данной программе используется следующая двухэтапная схема распределения данных. На первом этапе матрица разделяется на горизонтальные полосы, каждая из которых содержит BlockSize строк. Эти полосы распределяются по процессам, составляющим нулевой столбец процессорной решетки. Для этого используется функция MPI_Scatter в рамках коммуникатора ColComm (всего создается GridSize коммуникаторов для столбцов топологической решетки).

На втором этапе каждая полоса разделяется на блоки между процессами, составляющими строки процессорной решетки. Распределение полосы на блоки осуществляется последовательно через распределение строк полосы при помощи функции MPI_Scatter в рамках коммуникатора RowComm (всего создается GridSize коммуникаторов для строк топологической решетки).

Описанное блочное разделение матрицы между процессами процессорной решетки реализуется функцией CheckerboardMatrixScatter.

Наконец, для выполнения алгоритма Фокса необходимо разделить матрицу А и матрицу В на блоки. Эта процедура реализуется функцией DataDistribution. Функция TestBlocks осуществляет контроль правильности распределения исходных данныхи последовательно распечатывает содержимое матричного блока на всех процесах.