Теория и практика параллельных вычислений
Программная реализация
Представим возможный вариант программной реализации алгоритма Фокса для умножения матриц при блочном представлении данных. Приводимый программный код содержит основные модули параллельной программы, отсутствие отдельных вспомогательных функций не сказывается на общем понимании реализуемой схемы параллельных вычислений.
1. Главная функция программы. Определяет основную логику работы алгоритма, последовательно вызывает необходимые подпрограммы.
Пример 7.1.
(html, txt)
2. Функция CreateGridCommunicators. Данная функция создает коммуникатор в виде двумерной квадратной решетки, определяет координаты каждого процесса в этой решетке, а также создает коммуникаторы отдельно для каждой строки и каждого столбца.
Создание решетки производится при помощи функции MPI_Cart_create (вектор Periodic определяет возможность передачи сообщений между граничными процессами строк и столбцов создаваемой решетки). После создания решетки каждый процесс параллельной программы будет иметь координаты своего положения в решетке; получение этих координат обеспечивается при помощи функции MPI_Cart_coords.
Формирование топологий завершается созданием множества коммуникаторов для каждой строки и каждого столбца решетки в отдельности (функция MPI_Cart_sub).
Пример 7.2.
(html, txt)
3. Функция ProcessInitialization. Данная функция определяет параметры решаемой задачи (размеры матриц и их блоков), выделяет память для хранения данных и осуществляет ввод исходных матриц (или формирует их при помощи какого-либо датчика случайных чисел). Всего в каждом процессе должна быть выделена память для хранения четырех блоков – для указателей на выделенную память используются переменные pAblock, pBblock, pCblock, pMatrixAblock. Первые три указателя определяют блоки матриц A, B и C соответственно. Следует отметить, что содержимое блоков pAblock и pBblock постоянно меняется в соответствии с пересылкой данных между процессами, в то время как блок pMatrixAblock матрицы A остается неизменным и применяется при рассылках блоков по строкам решетки процессов (см.
// Циклический сдвиг блоков матрицы В вдоль столбца процессной // решетки void BblockCommunication (double *pBblock, int BlockSize) { MPI_Status Status; int NextProc = GridCoords[0] + 1; if ( GridCoords[0] == GridSize-1 ) NextProc = 0; int PrevProc = GridCoords[0] - 1; if ( GridCoords[0] == 0 ) PrevProc = GridSize-1; MPI_Sendrecv_replace( pBblock, BlockSize*BlockSize, MPI_DOUBLE, NextProc, 0, PrevProc, 0, ColComm, &Status); }
8. Функция ParallelResultCalculation. Для непосредственного выполнения параллельного алгоритма Фокса умножения матриц предназначена функция ParallelResultCalculation, которая реализует логику работы алгоритма.
// Функция для параллельного умножения матриц void ParallelResultCalculation(double* pAblock, double* pMatrixAblock, double* pBblock, double* pCblock, int BlockSize) { for (int iter = 0; iter < GridSize; iter ++) { // Рассылка блоков матрицы A по строкам процессной решетки ABlockCommunication (iter, pAblock, pMatrixAblock, BlockSize); // Умножение блоков BlockMultiplication(pAblock, pBblock, pCblock, BlockSize); // Циклический сдвиг блоков матрицы B в столбцах процессной // решетки BblockCommunication(pBblock, BlockSize); } }
