Алгоритм Флойда

Постановка задачи

Пусть G есть граф G = (RV), для которого набор вершин νi, 1≤ i ≤n, задается множеством V, а список ребер графа rj = (vsj,vtj), 1≤j≤m определяется множеством R. Ребрам графа приписаны некоторые числовые характеристики (веса) wj, 1≤j≤m. Граф полагаем ориентированным. Для имеющегося графа G требуется найти минимальные длины путей между каждой парой вершин графа. В качестве практического примера можно привести задачу составления оптимального маршрута движения транспорта между различными городами при заданном расстоянии между населенными пунктами. Вершинами графа в этой задаче моделируются города, рёбрами — соединяющие их дороги. Веса рёбер графа определяют расстояния между городами.

Графы задаются при помощи матрицы смежности. Элемент матрицы характеризует вес ребра, входящего в вершину. На главной диагонали матрицы стоят нули. Для обозначения отсутствия ребра между вершинами при вычислениях используется -1. Использование матрицы смежности позволяет применять при реализации вычислительных процедур анализа графов матричные алгоритмы обработки данных.

В данной работе разобран алгоритм Флойда для решения задачи поиска оптимальных путей на графе и произведена его последовательная и параллельная реализация.

Цели работы:

1) Реализовать последовательную версию алгоритма Флойда;

2) Реализовать параллельную версию алгоритма Флойда с помощью библиотеки MPI;

3) Оценить эффективность параллельной схемы и привести результаты вычислительных экспериментов.

Метод решения

Для поиска минимальных расстояний между всеми парами пунктов назначения Флойд предложил алгоритм, сложность которого имеет порядок O(n^3). В общем виде данный алгоритм может быть представлен следующим образом:

// Последовательный алгоритм Флойда

for (k = 0; k < n; k++)

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

A[i,j] = min(A[i,j],A[i,k]+A[k,j]);

Реализация операции выбора минимального значения min должна учитывать способ указания в матрице смежности несуществующих ребер графа. Как можно заметить, в ходе выполнения алгоритма матрица смежности A изменяется, после завершения вычислений в матрице A будет храниться требуемый результат – длины минимальных путей для каждой пары вершин исходного графа.

Параллельная схема

Как следует из общей схемы алгоритма Флойда, основная вычислительная нагрузка при решении задачи поиска кратчайших путей состоит в выполнении операции выбора минимального значения. Данная операция является достаточно простой и ее распараллеливание не приведет к заметному ускорению вычислений. Более эффективный способ организации параллельных вычислений может состоять в одновременном выполнении нескольких операций обновления значений матрицы A.

Покажем корректность такого способа организации параллелизма. Для этого нужно доказать, что операции обновления значений матрицы A на одной и той же итерации внешнего цикла k могут выполняться независимо. Иными словами, следует показать, что на итерации k не происходит изменения элементов Aik и Akj ни для одной пары индексов (i, j). Рассмотрим выражение, по которому происходит изменение элементов матрицы A:

Aij <- min (Aij, Aik + Akj).

Для i=k получим

Akj <- min (Akj, Akk + Akj),

но тогда значение Akj не изменится, т.к. Akk=0.

Для j=k выражение преобразуется к виду

Aik <- min (Aik, Aik + Akk),

что также показывает неизменность значений Aik. Как результат, необходимые условия для организации параллельных вычислений обеспечены, и, тем самым, в качестве базовой подзадачи может быть использована операция обновления элементов матрицы A (для указания подзадач будем применять индексы обновляемых в подзадачах элементов).

Выполнение вычислений в подзадачах становится возможным только тогда, когда каждая подзадача (i, j) содержит необходимые для расчетов элементы Aij, Aik, Akj матрицы A. Для исключения дублирования данных разместим в подзадаче (i, j) единственный элемент Aij, тогда получение всех остальных необходимых значений может быть обеспечено только при помощи передачи данных.

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

Параллельный алгоритм Флойда заключается в том, что на k-й итерации мы отсылаем k-ю строку всем процессам, а затем каждый процесс выполняет последовательный алгоритм Флойда для своей полосы матрицы смежности, одновременно обновляя значение матрицы.

Анализ эффективности

Общая трудоемкость последовательного алгоритма равна O(n³), поскольку в нём присутствуют вложенные друг в друга три цикла. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы A. Всего в подзадачах n² таких элементов, учитывая число процессоров p, сложность подзадачи — O(n²⁄p). Число итераций алгоритма равно n. Сложность всего алгоритма — O(n³⁄p). Таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид:

S_p(n)=(T₁(n))/(T_p(n))=n³/((n³⁄p))=p,

E_p(n)=(T₁(n))/(p⋅T_p(n))=(S_p(n))/p=1.

Таким образом, общий анализ сложности дает идеальные показатели эффективности параллельных вычислений. Для уточнения полученных соотношений введем в полученное выражения время выполнения базовой операции выбора минимального значения и учтём затраты на выполнение операций передачи данных между процессами.

Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы A всем процессорам вычислительной системы. Выполнение такой операции может быть выполнено за log₂⁡p шагов. С учетом количества итераций алгоритма Флойда, длительность выполнения коммуникационных операций может быть определена как:

T_p=n⋅log₂⁡p⋅(α+ωn⁄β),

где α – латентность сети передачи данных, β – пропускная способность сети, ω – размер элемента матрицы в байтах.

С учетом полученных соотношений общее время выполнения параллельного алгоритма Флойда составляет:

T_p=n²(n⁄p)τ+n⋅log₂⁡p⋅(α+ωn⁄β),

где τ есть время выполнения операции выбора минимального значения.

Результаты вычислительных экспериментов

Тесты проводились на четырехъядерном процессоре intel core i5. Время указано в мс.