ПОСТАНОВКА ЗАДАЧИ
В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Математические модели в виде графов широко используются при моделировании разнообразных явлений, процессов и систем. Многие теоретические и реальные прикладные задачи могут быть решены при помощи тех или иных процедур анализа графовых моделей. В качестве примера можно привести задачу составления маршрута движения транспорта между различными городами при заданном расстоянии между населенными пунктами.
В данной работе рассматривается алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Целями данной работы являются:
- реализация последовательной версии алгоритма Флойда;
- реализация параллельной версии алгоритма Флойда с помощью библиотеки MPI;
- оценка эффективность параллельной схемы.
МЕТОД РЕШЕНИЯ
ДАНО: непустой взвешенный граф G=(V, E) с произвольными весами ребер. Вершины графа пронумерованы от 1 до n. Граф G представлен матрицей смежности.
Требуется найти длины кратчайших путей между всеми парами вершин графа, если в графе нет циклов отрицательной суммарной длины.
АЛГОРИТМ. Пусть вершины графа пронумерованы от 1 до n и введено обозначение d_ij^k для длины кратчайшего пути от i до j, который кроме самих вершин i, j проходит только через вершины 1…k. Очевидно, что d_ij^k — длина (вес) ребра (i,j), если таковое существует (в противном случае его длина может быть обозначена как ∞).
Существует два варианта значения d_ij^k,k∈(1,…,n):
- Кратчайший путь между i, j не проходит через вершину k, тогда d_ij^k=d_ij^(k-1)
- Существует более короткий путь между i, j, проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно, d_ij^k=d_ik^(k-1)+d_kj^(k-1).
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула для
d_ij^k имеет вид:
- d_ij^0 — длина ребра (i,j)
- d_ij^k=min(d_ij^(k-1),d_ik^(k-1)+d_kj^(k-1))
Алгоритм Флойда — Уоршелла последовательно вычисляет все значения
d_ij^k, для всех
i, j для
k от 1 до
n. Полученные значения
d_ij^m являются длинами кратчайших путей между вершинами
i, j.
СХЕМА РЕШЕНИЯ
Как следует из общей схемы алгоритма Флойда, основная вычислительная нагрузка при решении задачи поиска кратчайших путей состоит в выполнении операции выбора минимальных значений. Данная операция является достаточно простой, и ее распараллеливание не приведет к заметному ускорению вычислений. Более эффективный способ организации параллельных вычислений может состоять в одновременном выполнении нескольких операций обновления значений матрицы D.
Выделение информационных зависимостей.
Выполнение вычислений в подзадачах становится возможным только тогда, когда каждая подзадача (i, j) содержит необходимые для расчетов элементы Dij, Dik, Dkj матрицы D. Для исключения дублирования данных разместим в подзадаче (i, j) единственный элемент Dij, тогда получение всех остальных необходимых значений может быть обеспечено только при помощи передачи данных. Таким образом, каждый элемент Dkj строки k матрицы D должен быть передан всем подзадачам (k, j) 1≤j≤n, а каждый элемент Dik столбца k матрицы D должен быть передан всем подзадачам (i,k) 1≤i≤n.
Информационная зависимость базовых подзадач
(стрелками показаны направления обмена значениями на итерации k).
Масштабирование и распределение подзадач по процессорам.
Как правило, число доступных процессоров p существенно меньше, чем число базовых задач n^2 (p << n^2). Возможный способ укрупнения вычислений состоит в использовании ленточной схемы разбиения матрицы D – такой подход соответствует объединению в рамках одной базовой подзадачи вычислений, связанных с обновлением элементов одной или нескольких строк (горизонтальное разбиение) или столбцов (вертикальное разбиение) матрицы.
При таком способе разбиения данных на каждой итерации алгоритма Флойда потребуется передавать между подзадачами только элементы одной из строк матрицы D. Для оптимального выполнения подобной коммуникационной операции топология сети должна обеспечивать эффективное представление структуры сети передачи данных в виде гиперкуба или полного графа.
ЭФФЕКТИВНОСТЬ РЕШЕНИЯ
Общая трудоёмкость последовательного алгоритма равна n3. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы D. Всего в подзадачах n2/p таких элементов, число итераций алгоритма равно n, таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид (p – число процессоров):
Sp = n^3/(n^3/p) = p,
Ep = n^3/(p(n^3⁄p)) = 1.
Общий анализ сложности дает идеальные показатели эффективности параллельных вычислений.
Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы D всем процессорам вычислительной системы. Выполнение такой операции может быть выполнено за log2 p шагов.
Общая длительность выполнения коммуникационных операций:
Tp(comm) = n log2 p (α + wn/β),
где α – латентность сети передачи данных, β – пропускная способность сети, w – размер элемента матрицы в байтах.
Общее время выполнения параллельного алгоритма Флойда:
Tp = n^2(n/p) τ + n log2 p (α + wn/β),
где τ есть время выполнения операции выбора минимального значения.
РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ
Без передачи по сети:
| Кол-во вершин |
Последовательный алгоритм |
Парал. алгоритм (2 процесса) |
Парал. алгоритм (теор. время) |
Ускорение |
| 500 |
1.002246 |
0.696685 |
0.07054 |
1.452934 |
| 1000 |
8.167236 |
5.424743 |
5.41751 |
1.500531 |
| 2000 |
63.418071 |
43.661854 |
44.7101 |
1.45235 |
С передачей по сети:
| Кол-во вершин |
1.Парал. алгоритм (по 1 проц. на 2х комп.) |
2.Парал. алгоритм (по 2 проц. на 2х комп.) |
1.Ускорение |
2.Ускорение |
| 500 |
1.892246 |
1.646685 |
0.552934 |
0.622934 |
| 1000 |
7.477236 |
5.434743 |
1.110531 |
1.500531 |
| 2000 |
47.418071 |
31.661854 |
1.34235 |
2.03235 |
Эксперименты проводидись на компютерах с процессорами Intel Core 2 Duo E6550, 2.33 ГГц, 4 Гб RAM
2.00 Gb RAM
