Эффективный способ организации параллельных вычислений - одновременное выполнение нескольких операций обновления значений матрицы D. Операции обновления значений матрицы могут выполняться независимо на одной и той же итерации внешнего цикла, т.к. на итерации k не происходит изменения элементов Di,k и Dk,j.
В работе использовалось горизонтальное разбиение матрицы, т.е. каждому процессу передавалось несколько строк матрицы, с которыми он выполнял необходимые действия.
При таком способе разбиения данных на каждой итерации алгоритма Флойда потребуется передавать между подзадачами только элементы одной из строк матрицы D (k-й строки). Для эффективного выполнения подобной коммуникационной операции топология сети должна представлять собой гиперкуб или полный граф.
Параллельный алгоритм:
1) Определение исходных данных задачи (число вершин).
2) Создание матрицы смежности и её заполнение (случайным образом).
3) Распределение данных между процессами (каждый получает горизонтальную полосу матрицы).
4) Выполнение параллельного алгоритма Флойда.
5) Сбор со всех процессов горизонтальных полос результирующей матрицы кратчайших расстояний.
6) Освобождение памяти, выделенной для хранения данных.
Параллельный алгоритм Флойда заключается в том, что на k-й итерации мы отсылаем k-ю строку всем процессам, а затем каждый процесс выполняет последовательный алгоритм Флойда для полосы матрицы смежности.
