Difference between revisions of "Bellman-Ford algorithm"
| [unchecked revision] | [unchecked revision] |
| Line 12: | Line 12: | ||
=== General description of the algorithm === | === General description of the algorithm === | ||
| − | The '''Bellman-Ford algorithm'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> was designed for [[Поиск кратчайшего пути от одной вершины (SSSP)|finding the shortest paths between nodes in a graph]]. | + | The '''Bellman-Ford algorithm'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> was designed for [[Поиск кратчайшего пути от одной вершины (SSSP)|finding the shortest paths between nodes in a graph]]. For a given weighted digraph, the algorithm finds the shortest paths between a singled-out source node and the other nodes of the graph. The Bellman-Ford algorithm scales worse than other algorithms for solving this problem (the complexity is <math>O(|V||E|)</math> against <math>O(|E| + |V|\ln(|V|))</math> for [[Алгоритм Дейкстры|Dijkstra's algorithm]]). However, its distinguishing feature is the applicability to graphs with arbitrary (including negative) weights. |
=== Mathematical description of the algorithm === | === Mathematical description of the algorithm === | ||
Revision as of 17:22, 24 November 2017
| Алгоритм Беллмана-Форда | |
| Sequential algorithm | |
| Serial complexity | [math]O(|V||E|)[/math] |
| Input data | [math]O(|V| + |E|)[/math] |
| Output data | [math]O(|V|^2)[/math] |
| Parallel algorithm | |
| Parallel form height | [math]N/A, max O(|V|) [/math] |
| Parallel form width | [math]O(|E|)[/math] |
Contents
- 1 Properties and structure of the algorithm
- 1.1 General description of the algorithm
- 1.2 Mathematical description of the algorithm
- 1.3 Computational kernel of the algorithm
- 1.4 Macro structure of the algorithm
- 1.5 Implementation scheme of the serial algorithm
- 1.6 Serial complexity of the algorithm
- 1.7 Information graph
- 1.8 Parallelization resource of the algorithm
- 1.9 Input and output data of the algorithm
- 1.10 Properties of the algorithm
- 2 Software implementation of the algorithm
- 2.1 Implementation peculiarities of the serial algorithm
- 2.2 Locality of data and computations
- 2.3 Possible methods and considerations for parallel implementation of the algorithm
- 2.4 Scalability of the algorithm and its implementations
- 2.5 Dynamic characteristics and efficiency of the algorithm implementation
- 2.6 Conclusions for different classes of computer architecture
- 2.7 Existing implementations of the algorithm
- 3 References
1 Properties and structure of the algorithm
1.1 General description of the algorithm
The Bellman-Ford algorithm[1][2][3] was designed for finding the shortest paths between nodes in a graph. For a given weighted digraph, the algorithm finds the shortest paths between a singled-out source node and the other nodes of the graph. The Bellman-Ford algorithm scales worse than other algorithms for solving this problem (the complexity is [math]O(|V||E|)[/math] against [math]O(|E| + |V|\ln(|V|))[/math] for Dijkstra's algorithm). However, its distinguishing feature is the applicability to graphs with arbitrary (including negative) weights.
1.2 Mathematical description of the algorithm
Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math]. Обозначим через [math]d(v)[/math] кратчайшее расстояние от источника [math]u[/math] до вершины [math]v[/math].
Алгоритм Беллмана-Форда ищет функцию [math]d(v)[/math] как единственное решение уравнения
- [math] d(v) = \min \{ d(w) + f(e) \mid e = (w, v) \in E \}, \quad \forall v \ne u, [/math]
с начальным условием [math]d(u) = 0[/math].
1.3 Computational kernel of the algorithm
Основной операцией алгоритма является релаксация ребра: если [math]e = (w, v) \in E[/math] и [math]d(v) \gt d(w) + f(e)[/math], то производится присваивание [math]d(v) \leftarrow d(w) + f(e)[/math].
1.4 Macro structure of the algorithm
Алгоритм последовательно уточняет значения функции [math]d(v)[/math].
- В самом начале производится присваивание [math]d(u) = 0[/math], [math]d(v) = \infty[/math], [math]\forall v \ne u[/math].
- Далее происходит [math]|V|-1[/math] итерация, в ходе каждой из которых производится релаксация всех рёбер графа.
Структуру можно описать следующим образом:
1. Инициализация: всем вершинам присваивается предполагаемое расстояние [math]t(v)=\infty[/math], кроме вершины-источника, для которой [math]t(u)=0[/math] .
2. Релаксация множества рёбер [math]E[/math]
а) Для каждого ребра [math]e=(v,z) \in E[/math] вычисляется новое предполагаемое расстояние [math]t^' (z)=t(v)+ w(e)[/math].
б) Если [math]t^' (z)\lt t(z)[/math], то происходит присваивание [math]t(z) := t' (z)[/math] (релаксация ребра [math]e[/math] ).
3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.
Если на [math]|V|[/math]-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро [math]e=(v,z)[/math], лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): [math]t(v)+w(e)\lt d(z)[/math]
1.5 Implementation scheme of the serial algorithm
Последовательный алгоритм реализуется следующим псевдокодом:
Входные данные:
граф с вершинами V, рёбрами E с весами f(e);
вершина-источник u.
Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u.
for each v ∈ V do d(v) := ∞
d(u) = 0
for i from 1 to |V| - 1:
for each e = (w, v) ∈ E:
if d(v) > d(w) + f(e):
d(v) := d(w) + f(e)
1.6 Serial complexity of the algorithm
Алгоритм выполняет [math]|V|-1[/math] итерацию, на каждой из которых происходит релаксация [math]|E|[/math] рёбер. Таким образом, общий объём работы составляет [math]O(|V||E|)[/math] операций.
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
- Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
- На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).
1.7 Information graph
На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.
На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).
Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.
Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями.
1.8 Parallelization resource of the algorithm
Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 1). Во-вторых, поиск кратчайших путей от фиксированной вершины [math]u[/math] так же может выполняться параллельно: инициализация начальных путей [2] требует [math]|V|[/math] параллельных операции, реаллаксация каждого ребра требует [math]O(|E|)[/math] параллельных операции.
Таким образом, при наличии [math]O(|E|)[/math] процессоров алгоритм завершит работу максимум за [math]|V|[/math] шагов. В реальности, шагов обычно требуется меньше, а именно [math]O(r)[/math] - максимальной длине среди всех кратчайших путей от выбранной вершины-источника [math]u[/math].
Таким образом, ширина ярусно-параллельной формы алгоритма равна [math]O(|E|)[/math], высота ЯПФ - [math]O(r) | r \lt |V|[/math].
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
1.9 Input and output data of the algorithm
Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]|V|[/math] вершин [math]v_i[/math] и [math]|E|[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]), вершина-источник [math]u[/math].
Объём входных данных: [math]O(|V| + |E|)[/math].
Выходные данные (возможные варианты):
- для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
- для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].
Объём выходных данных: [math]O(|V|)[/math].
1.10 Properties of the algorithm
Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро [math]e = (v, w)[/math] лежит на таком цикле, если вычисленные алгоритмом кратчайшие расстояния [math]d(v)[/math] удовлетворяют условию
- [math] d(v) + f(e) \lt d(w), [/math]
где [math]f(e)[/math] – вес ребра [math]e[/math]. Условие может быть проверено для всех рёбер графа за время [math]O(|E|)[/math].
2 Software implementation of the algorithm
2.1 Implementation peculiarities of the serial algorithm
2.2 Locality of data and computations
2.2.1 Locality of implementation
2.2.1.1 Structure of memory access and a qualitative estimation of locality
На рис. 2 представлен профиль обращений в память для реализации алгоритма Беллмана-Форда. Первое, что сразу стоит отметить – число обращений в память гораздо больше числа задействованных данных. Это говорит о частом повторном использовании одних и тех же данных, что обычно приводит к высокой временной локальности. Далее, видна явная регулярная структура производимых обращений в память, видны повторяющиеся итерации работы алгоритма. Практически все обращения образуют фрагменты, похожие на последовательный перебор, кроме самой верхней части, где наблюдается более сложная структура.
Рассмотрим более детально отдельные фрагменты общего профиля, чтобы лучше разобраться в его структуре. На рис. 3 представлен фрагмент 1 (выделен на рис. 2), на котором показаны первые 500 обращений в память (отметим, что другой наклон двух последовательных переборов связан с измененным отношением сторон в рассматриваемой области). Данный рисунок показывает, что выделенные желтым части 1 и 2 являются практические идентичными последовательными переборами; отличие между ними только в том, что в части 1 обращения выполняются в два раза чаще, поэтому на рис. 3 эта часть представлена большим числом точек. Как мы знаем, подобные профили характеризуются высокой пространственной и низкой временной локальностью.
Далее рассмотрим более интересный фрагмент 2, отмеченный на рис. 2 (см. рис. 4). Здесь можно снова увидеть подтверждение регулярности обращений в нижней области профиля, однако верхняя область явно устроена гораздо сложнее; хотя и здесь просматривается регулярность. В частности, также видны те же самые итерации, в которых здесь можно выделить большие последовательности обращений к одним и тем же данным. Пример такого поведения, оптимального с точки зрения локальности, выделен на рисунке желтым.
Чтобы понять структуру обращений в память в верхней части, можно рассмотреть ее еще подробнее. Приведем визуализацию небольшой области фрагмента 1, выделенную на рис. 4 зеленым. Однако в данном случае дальнейшее приближение (рис. 5) не привносит большей ясности: видна нерегулярная структура внутри итерации, характер которой достаточно сложно описать. Но в данном случае этого и не требуется – можно заметить, что по вертикали отложено всего 15 элементов, при этом обращений к ним выполняется гораздо больше. Независимо от структуры обращений, такой профиль обладает очень высокой как пространственной, так и временной локальностью.
А так как основная масса обращений приходится именно на фрагмент 2, можно утверждать, что и весь общий профиль обладает высокой пространственной и временной локальностью.
2.2.1.2 Quantitative estimation of locality
Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что по производительности работы с памятью данная реализация алгоритма показывает очень хорошие результаты. В частности, значение daps сравнимо с оценкой для теста Linpack, который известен высокой эффективностью взаимодействия с подсистемой памяти.
2.3 Possible methods and considerations for parallel implementation of the algorithm
Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а так же параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе.
2.4 Scalability of the algorithm and its implementations
2.4.1 Scalability of the algorithm
Алгоритм обладает значительным потенциалом масштабируемости, так как каждое ребро обрабатывается независимо и можно поручить каждому вычислительному процессу свою часть рёбер графа. Узким местом является доступ к разделяемому всеми процессами массиву расстояний. Алгоритм позволяет ослабить требования к синхронизации данных этого массива между процессами (когда один процесс может не сразу увидеть новое значение расстояния, записанное другим процессом), за счёт, может быть, большего количества глобальных итераций.
2.4.2 Scalability of of the algorithm implementation
Проведём исследование масштабируемости параллельной реализации алгоритма Беллмана-Форда согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2 Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [1 : 28] с шагом 1;
- размер графа [2^20 : 2^27].
Проведем отдельные исследования сильной масштабируемости вширь реализации алгоритма Беллмана-Форда.
Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера.
2.5 Dynamic characteristics and efficiency of the algorithm implementation
Для проведения экспериментов использовалась реализация алгоритма Беллмана-Форда, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле. На рисунках показана эффективность реализации алгоритма Беллмана-Форда, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.
На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 5%. Это достаточно неэффективная картина даже для программ, запущенных c использованием одного ядра в реализации.
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно на уровне 1. Это указывает на постоянную загрузку аппаратных ресурсов не более чем 1 процессом, однако их число для узла слишком мало, что с одной стороны может указывать на не очень рациональные использование ресурсов.
На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 140 млн/сек это очень высокий показатель, показывающие потенциальную причину неэффективности.
На графике кэш-промахов второго уровня видно, что число промахов достаточно тоже крайне высокое и находится на уровне 140 млн/сек, что указывает на крайне неэффективную работу с памятью.
На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.
На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на кпервом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.
На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно, однако очень неэффективно использовала память из-за очень большого размера графа.
2.6 Conclusions for different classes of computer architecture
2.7 Existing implementations of the algorithm
- C++: Boost Graph Library (функция
bellman_ford_shortest). - Python: NetworkX (функция
bellman_ford). - Java: JGraphT (класс
BellmanFordShortestPath).
