|
|
| Line 1: |
Line 1: |
| − | {{algorithm | + | {{level-a}} |
| − | | name = Алгоритм Тарьяна-Вишкина поиска компонент двусвязности/мостов в графе
| |
| − | | serial_complexity = <math>O(|V| + |E|)</math>
| |
| − | | pf_height = <math>N/A </math>
| |
| − | | pf_width = <math> O(|V|) </math>
| |
| − | | input_data = <math>O(|V| + |E|)</math>
| |
| − | | output_data = <math>max O(|V|)</math>
| |
| − | }} | |
| | | | |
| − | Primary author of this description: [[:ru:Участник:Elijah|I.V.Afanasyev]].
| + | {{Russian}} |
| | | | |
| − | == Properties and structure of the algorithm ==
| + | [[Category:Started articles]] |
| | | | |
| − | === General description of the algorithm ===
| + | [[ru:Алгоритм Тарьяна-Вишкина поиска компонент двусвязности]] |
| − | | |
| − | Параллельный '''алгоритм Тарьяна-Вишкина''' <ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> находит [[Связность в графах|компоненты двухсвязности]] неориентированного графа за время <math>O(\ln |V|)</math> на <math>O(|V| + |E|)</math> процессорах. Алгоритм может быть адаптирован для поиска [[Связность в графах|мостов]]. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время<ref>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</ref><ref>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.</ref> как на системах архитектуры SMP, так и при вычислениях на GPU.
| |
| − | | |
| − | === Mathematical description of the algorithm ===
| |
| − | | |
| − | 1. Для каждой компоненты связности графа найти какое-либо остовное дерево <math>T</math>.
| |
| − | | |
| − | 2. Перенумеровать вершины <math>T</math> в порядке обратного обхода.
| |
| − | | |
| − | 3. В порядке возрастания номера вершины выполнить следующие действия:
| |
| − | | |
| − | a. <math>D(v) := 1+ \sum_{v \rightarrow w}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)<=N(w)</math> и <math>L(w)>N(w)-D(w)</math>.
| |
| − | | |
| − | === Computational kernel of the algorithm ===
| |
| − | | |
| − | Вычислительно затратной частью алгоритма является поиск в ширину, вычисляющий величины <math>N(v)</math>, вычислительным ядром которого является обход вершин, смежной к выбранной вершине <math>v</math> с последующем добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняться на каждом шаге для каждой вершины <math>v</math> графа.
| |
| − | | |
| − | === Macro structure of the algorithm ===
| |
| − | | |
| − | На первом шаге работы алгоритма строится остовный лес графа с использованием модифицированного алгоритма Шилоаха-Вишкина.
| |
| − | | |
| − | Для этого для каждой вершины <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)<=N(w)</math> и <math>L(w)>N(w)-D(w)</math>.
| |
| − | | |
| − | Основной идеей для обеспечения завершения работы алгоритма за <math>O( \ln |V|)</math> шагов является систематическое использование операции удвоения указателей.
| |
| − | | |
| − | === Implementation scheme of the serial algorithm ===
| |
| − | | |
| − | На первом шаге работы алгоритма строится остовный лес графа при помощи последовательных вызовов поисков в ширину от еще не посещенных на предыдущих шагах вершин. При необходимости может быть выполнен шаг Trim, выделяющий вершины, принадлежащие связанным компонентам единичного размера.
| |
| − | | |
| − | После этого производится построение островного дерева при помощи поиска в глубину, с подсчетом величин <math>D(v)</math>.
| |
| − | | |
| − | Затем производятся вычисления величин <math>L</math> и <math>H</math> по формулам, приведенным в пунктах b,c в предыдущем разделе.
| |
| − | | |
| − | === Serial complexity of the algorithm ===
| |
| − | | |
| − | Последовательный вариант алгоритма аналогичен [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритму Тарьяна]]<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> и имеет линейную сложность <math>O(|E| + |V|)</math>.
| |
| − | | |
| − | === Information graph ===
| |
| − | | |
| − | Далее на рисунке 1 представлен информационный граф алгоритма, демонстрирующий его основные уровни параллелизма.
| |
| − | | |
| − | [[file:tarjan_vishkin_ig.png|thumb|center|600px|Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина]]
| |
| − | | |
| − | В начале работы производится инциализация связанных компонент графа [1] и выделение тривиальных компонент (размера 1 и 2) [2], затем инициализация уровней для всех вершин [3] и последовательные поиски в ширину [4],[BFS] до тех пор, пока все вершины не будут размечены различными уровнями.
| |
| − | | |
| − | Далее происходит поиск ребер, которые войдут в остовное дерево [5] и последовательное построение данного дерева на основе поиска в глубину [6],[7]. Затем друг за другом вычисляются необходимые метрики для каждой их вершин L, H и D [8],[9]. В конце на основе данных метрик вычисляются мосты в графе [10].
| |
| − | | |
| − | === Parallelization resource of the algorithm ===
| |
| − | | |
| − | Алгоритм изначально параллельный, время работы <math>O(\ln(|V|))</math> на <math>O(|V| + |E|)</math> процессорах.
| |
| − | | |
| − | Изначальные инициализации компонент и уровней вершин [1] и [3] могут выполняться параллельно за <math>O(|V|)</math> операций. Шаг трим [2] так же может быть выполнен за <math>O(|E|)</math> параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем [[Поиск_в_ширину_(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>, а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).
| |
| − | | |
| − | === Input and output data of the algorithm ===
| |
| − | | |
| − | '''Входные данные''': граф <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> в случае хранения мостов в виде списка пар вершин
| |
| − | | |
| − | === Properties of the algorithm ===
| |
| − | | |
| − | 1. Компонента сильной связности – подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.
| |
| − | | |
| − | 2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.
| |
| − | | |
| − | == Software implementation of the algorithm ==
| |
| − | | |
| − | === Implementation peculiarities of the serial algorithm ===
| |
| − | | |
| − | === Locality of data and computations ===
| |
| − | ==== Locality of implementation ====
| |
| − | ===== Structure of memory access and a qualitative estimation of locality =====
| |
| − | ===== Quantitative estimation of locality =====
| |
| − | === Possible methods and considerations for parallel implementation of the algorithm ===
| |
| − | | |
| − | Программа, реализующая алгоритм Тарьяна-Вышкина, состоит из двух частей: CPU части, отвечающей за параллельные вычисления на многоядерных CPU, а так же копирование данных на GPU и общее управлениями вычислениями, и GPU части, отвечающей только за вычисления на графическом ускорителе.
| |
| − | | |
| − | === Scalability of the algorithm and its implementations ===
| |
| − | ==== Scalability of the algorithm ====
| |
| − | ==== Scalability of of the algorithm implementation ====
| |
| − | | |
| − | Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
| |
| − | | |
| − | Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:
| |
| − | | |
| − | * размер графа [2^18 : 2^26].
| |
| − | | |
| − | Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.
| |
| − | | |
| − | Основной характеристикой для сравнения было выбрано время выполнения, так как производительность (определения как TEPS то есть число ребер графа, которое алгоритм обрабатывает в секунду) для данной операции не отражает реальную эффективность обработки.
| |
| − | | |
| − | Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.).
| |
| − | | |
| − | [[file:Tarjan vishkin scaling wide.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма Тарьяна-Вишкина масштабируемость вширь: производительность в зависимости от размера графа]]
| |
| − | | |
| − | === Dynamic characteristics and efficiency of the algorithm implementation ===
| |
| − | | |
| − | === Conclusions for different classes of computer architecture ===
| |
| − | === Existing implementations of the algorithm ===
| |
| − | | |
| − | === Conclusions for different classes of computer architecture ===
| |
| − | === Existing implementations of the algorithm ===
| |
| − | | |
| − | [[Category:Articles in progress]]
| |
| − | | |
| − | [[Ru:Алгоритм Тарьяна-Вишкина поиска компонент двусвязности]]
| |
