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

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

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

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

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

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

2. Перенумеровать вершины $T$ в порядке обратного обхода.

3. В порядке возрастания номера вершины выполнить следующие действия:

a. $D(v) := 1+ \sum_{v \rightarrow w}D(w)$

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

c. $H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }$

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

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

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

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

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

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

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

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

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

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

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

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

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

Последовательный вариант алгоритма аналогичен алгоритму Тарьяна и имеет линейную сложность $O(m + n)$.

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

Далее представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма. Информационный граф алгоритма — ориентированный граф, состоящий из вершин, соответствующих операциям алгоритма, и направленных дуг, соответствующих передаче данных (результаты одних операций передаются в качестве аргументов другим операциям) между ними.

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

Рассмотрим подробнее данный информационный граф: в начале работы алгоритма происходит поиск в ширину (BFS) для построения дерева {1, 2}, затем поиск в глубину для нумерации вершин {3, 4, 5}, а затем подсчет величин Low, Disc {6} и сохранение ответа {7}.

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

Алгоритм изначально параллельный, время работы $O(\ln n)$ на $O(m + n)$ процессорах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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