Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
| Алгоритм Тарьяна-Вишкина поиска компонент двусвязности/мостов в графе | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(|V| + |E|) }[/math] |
| Объём входных данных | [math]\displaystyle{ O(|V| + |E|) }[/math] |
| Объём выходных данных | [math]\displaystyle{ max O(|V|) }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ N/A }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(|V|) }[/math] |
Основные авторы описания: И.В.Афанасьев
Свойства и структура алгоритма
Общее описание алгоритма
Параллельный алгоритм Тарьяна-Вишкина [1] находит компоненты двухсвязности неориентированного графа за время [math]\displaystyle{ O(\ln |V|) }[/math] на [math]\displaystyle{ O(|V| + |E|) }[/math] процессорах. Алгоритм может быть адаптирован для поиска мостов. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время[2][3] как на системах архитектуры SMP, так и при вычислениях на GPU.
Математическое описание алгоритма
1. Для каждой компоненты связности графа найти какое-либо остовное дерево [math]\displaystyle{ T }[/math].
2. Перенумеровать вершины [math]\displaystyle{ T }[/math] в порядке обратного обхода.
3. В порядке возрастания номера вершины выполнить следующие действия:
a. [math]\displaystyle{ D(v) := 1+ \sum_{v \rightarrow w}D(w) }[/math]
b. [math]\displaystyle{ L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]
c. [math]\displaystyle{ H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]
d. Пометить ребро [math]\displaystyle{ v \rightarrow w }[/math] мостом, если [math]\displaystyle{ H(w)\lt =N(w) }[/math] и [math]\displaystyle{ L(w)\gt N(w)-D(w) }[/math].
Вычислительное ядро алгоритма
Вычислительно затратной частью алгоритма является поиск в ширину, вычисляющий величины [math]\displaystyle{ N(v) }[/math], вычислительным ядром которого является обход вершин, смежной к выбранной вершине [math]\displaystyle{ v }[/math] с последующем добавлением еще не посещенных вершин в множество [math]\displaystyle{ P }[/math]. Данная операция выполняться на каждом шаге для каждой вершины [math]\displaystyle{ v }[/math] графа.
Макроструктура алгоритма
На первом шаге работы алгоритма строится остовный лес графа с использованием модифицированного алгоритма Шилоаха-Вишкина.
Для этого для каждой вершины [math]\displaystyle{ v }[/math] определяется указатель на родительскую вершину [math]\displaystyle{ P(v) }[/math]; на шаге инициализации [math]\displaystyle{ P(v):=v }[/math]. Далее остовный лес строится чередованием двух параллельных операций:
• Удвоение указателей: [math]\displaystyle{ P(v):=P(P(v)) }[/math] ;
• Соединение: [math]\displaystyle{ P(P(v)):=P(w) }[/math], где [math]\displaystyle{ v }[/math] – вершина [math]\displaystyle{ P }[/math]-дерева ( [math]\displaystyle{ P(v)=v }[/math]на текущем шаге), [math]\displaystyle{ w }[/math]– некоторая вершина, для которой существует ребро [math]\displaystyle{ (v,w)\in E }[/math]. Ребро помечается, как принадлежащее остовному лесу .
Далее производятся следующие шаги:
• перенумерация вершин в обратном порядке обхода (post-order);
• вычисление количества потомков [math]\displaystyle{ D(v) }[/math] для каждой вершины;
• вычисление значений [math]\displaystyle{ L(v) }[/math] и [math]\displaystyle{ H(v) }[/math] для каждой вершины;
• пометка рёбер [math]\displaystyle{ v \rightarrow w }[/math] мостами, если [math]\displaystyle{ H(w)\lt =N(w) }[/math] и [math]\displaystyle{ L(w)\gt N(w)-D(w) }[/math].
Основной идеей для обеспечения завершения работы алгоритма за [math]\displaystyle{ O( \ln |V|) }[/math] шагов является систематическое использование операции удвоения указателей.
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательный вариант алгоритма аналогичен алгоритму Тарьяна[4] и имеет линейную сложность [math]\displaystyle{ O(|E| + |V|) }[/math].
Информационный граф
Далее на рисунке 1 представлен информационный граф алгоритма, демонстрирующий его основные уровни параллелизма.
В начале работы производится инциализация связанных компонент графа [1] и выделение тривиальных компонент (размера 1 и 2) [2], затем инициализация уровней для всех вершин [3] и последовательные поиски в ширину [4],[BFS] до тех пор, пока все вершины не будут размечены различными уровнями.
Далее происходит поиск ребер, которые войдут в остовное дерево [5] и последовательное построение данного дерева на основе поиска в глубину [6],[7]. Затем друг за другом вычисляются необходимые метрики для каждой их вершин L, H и D [8],[9]. В конце на основе данных метрик вычисляются мосты в графе [10].
Ресурс параллелизма алгоритма
Алгоритм изначально параллельный, время работы [math]\displaystyle{ O(\ln(|V|)) }[/math] на [math]\displaystyle{ O(|V| + |E|) }[/math] процессорах.
Изначальные инициализации компонент и уровней вершин [1] и [3] могут выполняться параллельно за [math]\displaystyle{ O(|V|) }[/math] операций. Шаг трим [2] так же может быть выполнен за [math]\displaystyle{ O(|E|) }[/math] параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем разделе.
Нумерация вершин [math]\displaystyle{ D(v) }[/math] в порядке обходе графа поиском в глубину [5],[6] должно выполняться сугубо последовательно за [math]\displaystyle{ O(|V|) }[/math] операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.
Вычисление величин [math]\displaystyle{ L }[/math], [math]\displaystyle{ H }[/math] и ребер, являющихся мостами [8],[9],[10] может выполняться каждое за [math]\displaystyle{ O(|V|) }[/math] операций.
Таким образом, ширина ярусно-параллельной формы алгоритма равна [math]\displaystyle{ O(|E|) }[/math], а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).
Входные и выходные данные алгоритма
Входные данные: граф [math]\displaystyle{ G(V, E) }[/math], [math]\displaystyle{ |V| }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ |E| }[/math] рёбер [math]\displaystyle{ e_j = (v^{(1)}_{j}, v^{(2)}_{j}) }[/math].
Объём входных данных: [math]\displaystyle{ O(|V| + |E|) }[/math].
Выходные данные
Список ребер, являющихся мостами в графе.
Объём выходных данных:
1. [math]\displaystyle{ O(|E|) }[/math] в случае хранения массива принадлежности каждого ребра к множеству мостов в графе
2. [math]\displaystyle{ max O(|V|) }[/math] в случае хранения мостов в виде списка пар вершин
Свойства алгоритма
1. Компонента сильной связности – подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.
2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Программа, реализующая алгоритм Тарьяна-Вышкина, состоит из двух частей: CPU части, отвечающей за параллельные вычисления на многоядерных CPU, а так же копирование данных на GPU и общее управлениями вычислениями, и GPU части, отвечающей только за вычисления на графическом ускорителе.
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2 Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- размер графа [2^18 : 2^26].
Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.
Основной характеристикой для сравнения было выбрано время выполнения, так как производительность (определения как TEPS то есть число ребер графа, которое алгоритм обрабатывает в секунду) для данной операции не отражает реальную эффективность обработки.
Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.).
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
- ↑ Edwards, James A, and Uzi Vishkin. “Better Speedups Using Simpler Parallel Programming for Graph Connectivity and Biconnectivity,” PMAM’12, 103–114, New York, USA: ACM Press, 2012. doi:10.1145/2141702.2141714
- ↑ Guojing Cong, and David A Bader. “An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs),” 45b, IEEE, 2005. doi:10.1109/IPDPS.2005.100.
- ↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.