|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 35: |
Строка 35: |
| | 2. Релаксация множества рёбер <math>E</math> | | 2. Релаксация множества рёбер <math>E</math> |
| | | | |
| − | а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t^' (z)=t(v)+ w(e)</math>. | + | а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t' (z)=t(v)+ w(e)</math>. |
| | | | |
| − | б) Если <math>t^' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math> ). | + | б) Если <math>t' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math>). |
| | | | |
| | 3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра. | | 3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра. |
| Строка 110: |
Строка 110: |
| | == Программная реализация алгоритма == | | == Программная реализация алгоритма == |
| | === Особенности реализации последовательного алгоритма === | | === Особенности реализации последовательного алгоритма === |
| − | === Локальность данных и вычислений ===
| |
| − | ==== Локальность реализации алгоритма ====
| |
| − | ===== Структура обращений в память и качественная оценка локальности =====
| |
| − |
| |
| − | [[file:bellman_ford_1.png|thumb|center|700px|Рисунок 2. Алгоритм Беллмана-Форда. Общий профиль обращений в память]]
| |
| − |
| |
| − | На рис. 2 представлен профиль обращений в память для реализации алгоритма Беллмана-Форда. Первое, что сразу стоит отметить – число обращений в память гораздо больше числа задействованных данных. Это говорит о частом повторном использовании одних и тех же данных, что обычно приводит к высокой временной локальности. Далее, видна явная регулярная структура производимых обращений в память, видны повторяющиеся итерации работы алгоритма. Практически все обращения образуют фрагменты, похожие на последовательный перебор, кроме самой верхней части, где наблюдается более сложная структура.
| |
| − |
| |
| − | Рассмотрим более детально отдельные фрагменты общего профиля, чтобы лучше разобраться в его структуре. На рис. 3 представлен фрагмент 1 (выделен на рис. 2), на котором показаны первые 500 обращений в память (отметим, что другой наклон двух последовательных переборов связан с измененным отношением сторон в рассматриваемой области). Данный рисунок показывает, что выделенные желтым части 1 и 2 являются практически идентичными последовательными переборами; отличие между ними только в том, что в части 1 обращения выполняются в два раза чаще, поэтому на рис. 3 эта часть представлена большим числом точек. Как мы знаем, подобные профили характеризуются высокой пространственной и низкой временной локальностью.
| |
| − |
| |
| − | [[file:bellman_ford_2.png|thumb|center|700px|Рисунок 3. Профиль обращений, фрагмент 1]]
| |
| − |
| |
| − | Далее рассмотрим более интересный фрагмент 2, отмеченный на рис. 2 (см. рис. 4). Здесь можно снова увидеть подтверждение регулярности обращений в нижней области профиля, однако верхняя область явно устроена гораздо сложнее; хотя и здесь просматривается регулярность. В частности, также видны те же самые итерации, в которых здесь можно выделить большие последовательности обращений к одним и тем же данным. Пример такого поведения, оптимального с точки зрения локальности, выделен на рисунке желтым.
| |
| − |
| |
| − | [[file:bellman_ford_3.png|thumb|center|700px|Рисунок 4. Профиль обращений, фрагмент 2]]
| |
| − |
| |
| − | Чтобы понять структуру обращений в память в верхней части, можно рассмотреть ее еще подробнее. Приведем визуализацию небольшой области фрагмента 2, выделенной на рис. 4 зеленым. Однако в данном случае дальнейшее приближение (рис. 5) не привносит большей ясности: видна нерегулярная структура внутри итерации, характер которой достаточно сложно описать. Но в данном случае этого и не требуется – можно заметить, что по вертикали отложено всего 15 элементов, при этом обращений к ним выполняется гораздо больше. Независимо от структуры обращений, такой профиль обладает очень высокой как пространственной, так и временной локальностью.
| |
| − |
| |
| − | [[file:bellman_ford_4.png|thumb|center|700px|Рисунок 5. Небольшая часть фрагмента 2]]
| |
| − |
| |
| − | А так как основная масса обращений приходится именно на фрагмент 2, можно утверждать, что и весь общий профиль обладает высокой пространственной и временной локальностью.
| |
| − |
| |
| − | ===== Количественная оценка локальности =====
| |
| − |
| |
| − | Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по характеристике cvg.
| |
| − |
| |
| − | На рисунке 6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что по производительности работы с памятью данная реализация алгоритма показывает очень хорошие результаты. В частности, значение daps сравнимо с оценкой для теста Linpack, который известен высокой эффективностью взаимодействия с подсистемой памяти.
| |
| − |
| |
| − |
| |
| − | [[file:bellman_ford_daps.png|thumb|center|700px|Рисунок 6. Сравнение значений оценки daps]]
| |
| | | | |
| | === Возможные способы и особенности параллельной реализации алгоритма === | | === Возможные способы и особенности параллельной реализации алгоритма === |
| | Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе. | | Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе. |
| | | | |
| − | === Масштабируемость алгоритма и его реализации === | + | === Результаты прогонов === |
| − | ==== Масштабируемость алгоритма ====
| |
| − | | |
| − | Алгоритм обладает значительным потенциалом масштабируемости, так как каждое ребро обрабатывается независимо и можно поручить каждому вычислительному процессу свою часть рёбер графа. Узким местом является доступ к разделяемому всеми процессами массиву расстояний. Алгоритм позволяет ослабить требования к синхронизации данных этого массива между процессами (когда один процесс может не сразу увидеть новое значение расстояния, записанное другим процессом), за счёт, может быть, большего количества глобальных итераций.
| |
| − | | |
| − | ==== Масштабируемость реализации алгоритма ====
| |
| − | Проведём исследование масштабируемости параллельной реализации алгоритма Беллмана-Форда согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
| |
| − | | |
| − | Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:
| |
| − | | |
| − | * число процессоров [1 : 28] с шагом 1;
| |
| − | * размер графа [2^20 : 2^27].
| |
| − | | |
| − | Проведем отдельные исследования сильной масштабируемости вширь реализации алгоритма Беллмана-Форда.
| |
| − | | |
| − | Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера.
| |
| − | | |
| − | [[file:Сильная_масштабируемость_вширь_алгоритма_Беллмана-Форда.png|thumb|center|700px|Рисунок 7. Параллельная реализация алгоритма Беллмана-Форда масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа]]
| |
| − | | |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | Для проведения экспериментов использовалась реализация алгоритма Беллмана-Форда, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.
| |
| − | На рисунках показана эффективность реализации алгоритма Беллмана-Форда, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.
| |
| − | [[file:Bellman-Ford cpu.png|thumb|center|700px|Рисунок 8. График загрузки CPU при выполнении алгоритма Беллмана-Форда]]
| |
| − | | |
| − | На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 5%. Это достаточно неэффективная картина даже для программ, запущенных c использованием одного ядра в реализации.
| |
| − | | |
| − | [[file:Bellman-Ford LoadAvg.png|thumb|center|700px|Рисунок 9. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Беллмана-Форда]]
| |
| − | | |
| − | На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно на уровне 1. Это указывает на постоянную загрузку аппаратных ресурсов не более чем 1 процессом, однако это число для узла слишком мало, что может указывать на не очень рациональное использование ресурсов.
| |
| − | | |
| − | [[file:Bellman-Ford L1.png|thumb|center|700px|Рисунок 10. График кэш-промахов L1 в секунду при работе алгоритма Беллмана-Форда]]
| |
| − |
| |
| − | На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 140 млн/сек. Это очень высокий показатель, показывающий потенциальную причину неэффективности.
| |
| − | | |
| − | [[file:Bellman-Ford L2.png|thumb|center|700px|Рисунок 11. График кэш-промахов L2 в секунду при работе алгоритма Беллмана-Форда]]
| |
| − |
| |
| − | На графике кэш-промахов второго уровня видно, что число таких промахов тоже крайне высокое и находится на уровне 140 млн/сек, что указывает на крайне неэффективную работу с памятью.
| |
| − | | |
| − | [[file:Bellman-Ford-L3.png|thumb|center|700px|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма Беллмана-Форда]]
| |
| − | | |
| − | На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.
| |
| − | | |
| − | [[file:Bellman-Ford Inf Data.png|thumb|center|700px|Рисунок 13. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Беллмана-Форда]]
| |
| − | | |
| − | На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.
| |
| − | | |
| − | [[file:Bellman-Ford Inf Pckts.png|thumb|center|700px|Рисунок 14. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Беллмана-Форда]]
| |
| − | | |
| − | На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.
| |
| − |
| |
| − | В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно, однако очень неэффективно использовала память из-за очень большого размера графа.
| |
| − | | |
| | === Выводы для классов архитектур === | | === Выводы для классов архитектур === |
| − | === Существующие реализации алгоритма ===
| |
| | | | |
| − | * C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html bellman_ford_shortest]</code>).
| |
| − | * Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).
| |
| − | * Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html BellmanFordShortestPath]</code>).
| |
| − | * OpenMP Stinger {{Buttonlink|http://top53.parallel.ru/algo_results/implementation/10}}
| |
| − | * Nvidia nvGraph {{Buttonlink|http://top53.parallel.ru/algo_results/implementation/19}}
| |
| − | * Graph500 MPI {{Buttonlink|http://top53.parallel.ru/algo_results/implementation/24}}
| |
| − | * Ligra {{Buttonlink|http://top53.parallel.ru/algo_results/implementation/41}}
| |
| | == Литература == | | == Литература == |
| | | | |
| Алгоритм Беллмана-Форда
|
| Последовательный алгоритм
|
| Последовательная сложность
|
[math]O(|V||E|)[/math]
|
| Объём входных данных
|
[math]O(|V| + |E|)[/math]
|
| Объём выходных данных
|
[math]O(|V|^2)[/math]
|
| Параллельный алгоритм
|
| Высота ярусно-параллельной формы
|
[math]N/A, max O(|V|) [/math]
|
| Ширина ярусно-параллельной формы
|
[math]O(|E|)[/math]
|
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Беллмана-Форда[1][2][3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [math]O(|V||E|)[/math] против [math]O(|E| + |V|\ln(|V|))[/math] у алгоритма Дейкстры), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.
1.2 Математическое описание алгоритма
Пусть задан граф [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 Вычислительное ядро алгоритма
Основной операцией алгоритма является релаксация ребра: если [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 Макроструктура алгоритма
Алгоритм последовательно уточняет значения функции [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 Схема реализации последовательного алгоритма
Последовательный алгоритм реализуется следующим псевдокодом:
Входные данные:
граф с вершинами 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 Последовательная сложность алгоритма
Алгоритм выполняет [math]|V|-1[/math] итерацию, на каждой из которых происходит релаксация [math]|E|[/math] рёбер. Таким образом, общий объём работы составляет [math]O(|V||E|)[/math] операций.
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
- Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
- На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).
1.7 Информационный граф
На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.
Рисунок 1. Информационный граф обобщенного алгоритма Беллмана-Форда.
На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).
Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.
Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями.
1.8 Ресурс параллелизма алгоритма
Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 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 Входные и выходные данные алгоритма
Входные данные: взвешенный граф [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 Свойства алгоритма
Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро [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 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе.
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
- ↑ Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
- ↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
