Алгоритм Тарьяна-Вишкина поиска компонент двусвязности

Алгоритм Тарьяна-Вишкина поиска компонент двусвязности/мостов в графе
Последовательный алгоритм
Последовательная сложность	[math]O(|V| + |E|)[/math]
Объём входных данных	[math]O(|V| + |E|)[/math]
Объём выходных данных	[math]max O(|V|)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]N/A [/math]
Ширина ярусно-параллельной формы	[math] O(|V|) [/math]

Основные авторы описания: И.В.Афанасьев

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Параллельный алгоритм Тарьяна-Вишкина находит компоненты двухсвязности неориентированного графа за время [math]O(\ln |V|)[/math] на [math]O(|V| + |E|)[/math] процессорах. Алгоритм может быть адаптирован для поиска мостов. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время как на системах архитектуры SMP, так и при вычислениях на GPU.

1.2 Математическое описание алгоритма

1. Для каждой компоненты связности графа найти какое-либо остовное дерево [math]T[/math].

2. Перенумеровать вершины [math]T[/math] в порядке обратного обхода [math]N(v) [/math].

3. В порядке возрастания номера вершины [math]N(v) [/math] выполнить следующие действия:

a. [math]D(v) := 1+ \sum_{v \rightarrow w}D(w) [/math], величины [math]D(W)[/math] определяются рекурсивно.

b. [math] L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }[/math]

c. [math] H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }[/math]

d. Пометить ребро [math]v \rightarrow w[/math] мостом, если [math]H(w)\lt =N(w)[/math] и [math]L(w) \gt N(w)-D(w)[/math].

1.3 Вычислительное ядро алгоритма

Наиболее вычислительно затратной частью алгоритма является поиск в ширину в исходном графе, вычисляющий величины [math]N(v)[/math]. В свою очередь, вычислительным ядром данного поиска в ширину является обход вершин, смежных к выбранной вершине [math]v[/math], с последующем добавлением еще не посещенных вершин в стек.

1.4 Макроструктура алгоритма

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

Для этого для каждой вершины [math]v[/math] определяется указатель на родительскую вершину [math]P(v)[/math]; на шаге инициализации [math]P(v):=v[/math]. Далее остовный лес строится чередованием двух параллельных операций:

• Удвоение указателей: [math]P(v):=P(P(v))[/math] ;

• Соединение: [math]P(P(v)):=P(w)[/math], где [math]v[/math] – вершина [math]P[/math]-дерева ( [math]P(v)=v[/math]на текущем шаге), [math]w[/math]– некоторая вершина, для которой существует ребро [math](v,w)\in E[/math]. Ребро помечается, как принадлежащее остовному лесу .

Далее производятся следующие шаги:

• перенумерация вершин в обратном порядке обхода (post-order);

• вычисление количества потомков [math]D(v)[/math] для каждой вершины;

• вычисление значений [math]L(v)[/math] и [math]H(v)[/math] для каждой вершины;

• пометка рёбер [math]v \rightarrow w[/math] мостами, если [math]H(w)\lt =N(w)[/math] и [math]L(w) \gt N(w)-D(w)[/math].

Основной идеей для обеспечения завершения работы алгоритма за [math]O( \ln |V|)[/math] шагов является систематическое использование операции удвоения указателей.

1.5 Схема реализации последовательного алгоритма

На первом шаге работы алгоритма строится остовный лес графа при помощи последовательных вызовов поисков в ширину от еще не посещенных на предыдущих шагах вершин. При необходимости может быть выполнен шаг Trim, выделяющий вершины, принадлежащие связанным компонентам единичного размера.

После этого производится построение остовного дерева при помощи поиска в глубину, с подсчетом величин [math]D(v)[/math].

Затем производятся вычисления величин [math]L[/math] и [math]H[/math] по формулам, приведенным в пунктах b,c в предыдущем разделе.

1.6 Последовательная сложность алгоритма

Последовательный вариант алгоритма аналогичен алгоритму Тарьяна и имеет линейную сложность [math]O(|E| + |V|)[/math].

1.7 Информационный граф

Далее на рисунке 1 представлен информационный граф алгоритма, демонстрирующий его основные уровни параллелизма.

Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина

В начале работы алгоритм производит инциализацию связанных компонент графа [1], с последующим выделением тривиальных компонент (размера 1 и 2) [2]; затем, производится инициализация уровней для всех вершин [3] при помощи последовательных поисков в ширину [4],[BFS], выполняемых до тех пор, пока все вершины не будут размечены различными уровнями.

Далее производится поиск ребер, вошедших в остовное дерево [5], с последовательным построением данного дерева на основе поиска в глубину [6],[7]. После этого друг за другом производится вычисление необходимых метрик для каждой из вершин L, H и D [8],[9]. Перед завершением работы алгоритма на основе данных метрик производится вычисление мостов в графе [10].

1.8 Ресурс параллелизма алгоритма

Алгоритм изначально разрабатывался для параллельной реализации, его время работы составляет [math]O(\ln(|V|))[/math] на [math]O(|V| + |E|)[/math] процессорах.

Изначальные инициализации связанных компонент и уровней вершин [1] и [3] могут выполняться параллельно за [math]O(|V|)[/math] операций. Шаг трим [2] так же может быть выполнен за [math]O(|E|)[/math] параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем разделе.

Нумерация вершин [math]D(v)[/math] в обратном порядке обходе графа производится при помощи поиска в глубину [5],[6], который должен выполняться сугубо последовательно за [math]O(|V|)[/math] операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.

Каждое из вычислений величин [math]L[/math], [math]H[/math], а так же проверка ребер на свойство, является ли каждое их них мостом [8],[9],[10], может выполняться параллельно за [math]O(|V|)[/math] операций.

Таким образом, ширина ярусно-параллельной формы алгоритма равна [math]O(|E|)[/math], а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).

1.9 Входные и выходные данные алгоритма

Входные данные: граф [math]G(V, E)[/math], [math]|V|[/math] вершин [math]v_i[/math] и [math]|E|[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math].

Объём входных данных: [math]O(|V| + |E|)[/math].

Выходные данные

Список ребер, являющихся мостами в графе.

Объём выходных данных:

1. [math]O(|E|)[/math] в случае хранения массива принадлежности каждого ребра к множеству мостов в графе

2. [math]max O(|V|)[/math] в случае хранения мостов в виде списка пар вершин

1.10 Свойства алгоритма

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

2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.

2 Программная реализация алгоритма

2.3 Возможные способы и особенности параллельной реализации алгоритма

Программа, реализующая алгоритм Тарьяна-Вышкина, состоит из двух частей: CPU части, отвечающей за параллельные вычисления на многоядерных CPU, а так же копирование данных на GPU и общее управлениями вычислениями, и GPU части, отвечающей только за вычисления на графическом ускорителе.

2.4 Масштабируемость алгоритма и его реализации

2.4.2 Масштабируемость реализации алгоритма

Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2 Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• размер графа [2^18 : 2^26].

Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.

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

Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.).

Рисунок 2. Параллельная реализация алгоритма Тарьяна-Вишкина масштабируемость вширь: производительность в зависимости от размера графа