Теория и практика параллельных вычислений
int A, int B)
// Программа 10.1. — Алгоритм Флойда
int ProcRank; // Ранг текущего процесса
int ProcNum; // Количество процессов
// Функция вычисления минимума
int Min( int A, int B) {
int Result = (A < B) ? A : B;
if((A < 0) && (B >= 0)) Result = B;
if((B < 0) && (A >= 0)) Result = A;
if((A < 0) && (B < 0)) Result = -1;
return Result;
}
// Главная функция программы
int main(int argc, char* argv[]) {
int *pMatrix; // Матрица смежности
int Size; // Размер матрицы смежности
int *pProcRows; // Строки матрицы смежности текущего процесса
int RowNum; // Число строк для текущего процесса
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);
MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);
// Инициализация данных
ProcessInitialization(pMatrix, pProcRows, Size, RowNum);
// Распределение данных между процессами
DataDistribution(pMatrix, pProcRows, Size, RowNum);
// Параллельный алгоритм Флойда
ParallelFloyd(pProcRows, Size, RowNum);
// Сбор результатов работы алгоритма
ResultCollection(pMatrix, pProcRows, Size, RowNum);
// Завершение вычислений процесса
ProcessTermination(pMatrix, pProcRows);
MPI_Finalize();
return 0;
}
|
// Программа 10.1. — Алгоритм Флойда int ProcRank; // Ранг текущего процесса int ProcNum; // Количество процессов // Функция вычисления минимума int Min(int A, int B) { int Result = (A < B) ? A : B; if((A < 0) && (B >= 0)) Result = B; if((B < 0) && (A >= 0)) Result = A; if((A < 0) && (B < 0)) Result = -1; return Result; } // Главная функция программы int main(int argc, char* argv[]) { int *pMatrix; // Матрица смежности int Size; // Размер матрицы смежности int *pProcRows; // Строки матрицы смежности текущего процесса int RowNum; // Число строк для текущего процесса MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); // Инициализация данных ProcessInitialization(pMatrix, pProcRows, Size, RowNum); // Распределение данных между процессами DataDistribution(pMatrix, pProcRows, Size, RowNum); // Параллельный алгоритм Флойда ParallelFloyd(pProcRows, Size, RowNum); // Сбор результатов работы алгоритма ResultCollection(pMatrix, pProcRows, Size, RowNum); // Завершение вычислений процесса ProcessTermination(pMatrix, pProcRows); MPI_Finalize(); return 0; } |
| Пример 10.1. |
| Закрыть окно |
// Функция для рассылки строки всем процессам
void RowDistribution(int *pProcRows, int Size, int RowNum, int k,
int *pRow) {
int ProcRowRank; // Ранг процесса, которому принадлежит k-я строка
int ProcRowNum; // Номер k-й строки в полосе матрицы
// Нахождение ранга процесса – владельца k-й строки
int RestRows = Size;
int Ind = 0;
int Num = Size / ProcNum;
for(ProcRowRank = 1; ProcRowRank < ProcNum + 1; ProcRowRank ++) {
if(k < Ind + Num ) break;
RestRows -= Num;
Ind += Num;
Num = RestRows / (ProcNum - ProcRowRank);
}
ProcRowRank = ProcRowRank - 1;
ProcRowNum = k - Ind;
if(ProcRowRank == ProcRank)
// Копирование строки в массив pRow
copy(&pProcRows[ProcRowNum * Size], &pProcRows[(ProcRowNum + 1) *
Size], pRow);
// Распределение k-й строки между процессами
MPI_Bcast(pRow, Size, MPI_INT, ProcRowRank, MPI_COMM_WORLD);
}
|
// Функция для рассылки строки всем процессам void RowDistribution(int *pProcRows, int Size, int RowNum, int k, int *pRow) { int ProcRowRank; // Ранг процесса, которому принадлежит k-я строка int ProcRowNum; // Номер k-й строки в полосе матрицы // Нахождение ранга процесса – владельца k-й строки int RestRows = Size; int Ind = 0; int Num = Size / ProcNum; for(ProcRowRank = 1; ProcRowRank < ProcNum + 1; ProcRowRank ++) { if(k < Ind + Num ) break; RestRows -= Num; Ind += Num; Num = RestRows / (ProcNum - ProcRowRank); } ProcRowRank = ProcRowRank - 1; ProcRowNum = k - Ind; if(ProcRowRank == ProcRank) // Копирование строки в массив pRow copy(&pProcRows[ProcRowNum * Size], &pProcRows[(ProcRowNum + 1) * Size], pRow); // Распределение k-й строки между процессами MPI_Bcast(pRow, Size, MPI_INT, ProcRowRank, MPI_COMM_WORLD); } |
| Пример 10.2. |
| Закрыть окно |
