Теория и практика параллельных вычислений
Программная реализация
Представим возможный вариант параллельной реализации алгоритма Флойда. При этом описание отдельных модулей не приводится, если их отсутствие не оказывает влияния на понимание общей схемы параллельных вычислений.
1. Главная функция программы. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы.
Пример 10.1.
(html, txt)
Функция Min вычисляет меньшее из двух целых чисел, учитывая применяемый способ задания несуществующих дуг в матрице смежности (в рассматриваемой реализации для этого используется значение -1).
Функция ProcessInitialization определяет исходные данные решаемой задачи (количество вершин графа), выделяет память для хранения данных, осуществляет ввод матрицы смежности (или формирует ее при помощи какого-либо датчика случайных числе).
Функция DataDistribution распределяет исходные данные между процессами. Каждый процесс получает горизонтальную полосу матрицы смежности.
Функция ResultCollection осуществляет сбор со всех процессов горизонтальных полос результирующей матрицы кратчайших расстояний между любыми парами вершин графа.
Функция ProcessTermination выполняет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных.
Реализация всех перечисленных функций может быть выполнена по аналогии с ранее рассмотренными примерами и предоставляется читателю в качестве самостоятельного упражнения.
2. Функция ParallelFloyd. Данная функция осуществляет итеративное изменение матрицы смежности в соответствии с алгоритмом Флойда.
// Параллельный алгоритм Флойда void ParallelFloyd(int *pProcRows, int Size, int RowNum) { int *pRow = new int[Size]; int t1, t2;
for(int k = 0; k < Size; k++) { // Распределение k-й строки среди процессов RowDistribution(pProcRows, Size, RowNum, k, pRow);
// Обновление элементов матрицы смежности for(int i = 0; i < RowNum; i++) for(int j = 0; j < Size; j++) if( (pProcRows[i * Size + k] != -1) && (pRow [j]!= -1)){ t1 = pProcRows[i * Size + j]; t2 = pProcRows[i * Size + k] + pRow[j]; pProcRows[i * Size + j] = Min(t1, t2); } }
delete []pRow; }
3. Функция RowDistribution. Данная функция рассылает k-ю строку матрицы смежности всем процессам программы.
Пример 10.2.
(html, txt)
