Алгоритм DCSC поиска компонент сильной связности: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Teplov (обсуждение | вклад) |
Elijah (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Алгоритм DCSC'''<ref>Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.</ref><ref>McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.</ref><ref>Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.</ref> (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит [[Связность в графах|компоненты сильной связности]] ориентированного графа с ожидаемой работой <math>O(n \ln n)</math> (при условии ограниченной степени вершин). | + | '''Алгоритм DCSC'''<ref>Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.</ref><ref>McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.</ref><ref>Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.</ref> (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит [[Связность в графах|компоненты сильной связности]] ориентированного графа с ожидаемой работой <math>O(n \ln n)</math> (при условии ограниченной констатой степени вершин). |
| − | + | Так же алгоритм носит другое название - Forward-Backward (сокр. FB-algorithm), в основном в литературе, связанной с его GPU-реализациями. <ref> Jiˇr ́ı Barnat, Petr Bauch, Lubosˇ Brim, and Milan Cˇesˇka. Computing Strongly Connected Components in Parallel on CUDA. Faculty of Informatics, Masaryk University, Botanicka ́ 68a, 60200 Brno, Czech Republic. </ref> | |
| − | + | Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Кроме того, выделение данных подмножеств и сильно связанной компоненты на каждом шаге так же может производиться параллельно (с использованием параллельных поисков в ширину). Следует отметить, что в данном случае не требуется синхронизации между итерациями поиска в ширину, поскольку требуется только определить достижимые вершины, но не расстояния до них. | |
| + | |||
| + | Алгоритм хорошо подходит для графов, имеющих небольшое число сильно-связанных компонент большого размера. При значительном увеличении числа сильно связанных компонент сложность данного алгоритма так же значительно увеличивается (пропорционально числу компонент), из-за чего данный алгоритм может стать менее эффективным в сравнении с последовательным алгоритмом Тарьяна, выделяющим сильно-связанные компоненты за один проход по графу. | ||
| + | |||
| + | Для увеличения эффективности работы алгоритма на графах с большим числом тривиальных сильно-связанных компонент (размера 1 или 2), предложена модификация алгоритма: перед началом работы классического алгоритма, производится шаг Trim, описанный в следующих разделах, позволяющий выделять все тривиальные сильно-связанные компоненты. В результате, к примеру в R-MAT графах, после шага Trim в графе остается всего лишь несколько компонент сильной связанности большого размера, на которых алгоритм будет иметь небольшую алгоритмическую сложность. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 33: | Строка 37: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Основными вычислительными операциями алгоритма является поиск вершин, достижимых из выбранной вершины <math>v</math>, а так же поиск вершин, из которых достижима выбранная вершина <math>v</math>. Обе данные операции могут быть реализованы через поиски в ширину, устроенные следующим образом: | ||
| + | |||
| + | 1. Вершина <math>v_0</math> помещается в начало в очереди и помечается ее как посещенная | ||
| + | |||
| + | 2. Верхняя вершина <math>v</math> извлекается из очереди. Для всех ребер <math>(v, u)</math>, исходящих из вершины <math>v</math>, проверяется, является ли посещенной вершина <math>u</math>. В случае, если является, вершина <math>u</math> помещается в начало очереди. | ||
| + | |||
| + | 3. Происходит переход на шаг 2 до тех пор, пока в очереди есть вершины. | ||
| + | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 52: | Строка 65: | ||
Для улучшения балансировки нагрузки на первых шагах можно выбирать не одну ведущую вершину, а сразу несколько. Тогда, если они принадлежат различным компонентам связности, граф будет сразу разбит на большое количество областей, которые будут далее обрабатываться параллельно. | Для улучшения балансировки нагрузки на первых шагах можно выбирать не одну ведущую вершину, а сразу несколько. Тогда, если они принадлежат различным компонентам связности, граф будет сразу разбит на большое количество областей, которые будут далее обрабатываться параллельно. | ||
| + | |||
| + | |||
| + | |||
| + | Важной модификацией алгоритма является шаг Trim, производимый перед основными вычислениями алгоритма DCSC, который может быть описан следующим образом: | ||
| + | |||
| + | 1. Пометить все вершины из <math>v \in V</math> активными. | ||
| + | |||
| + | 2. Для каждой вершины <math>v</math>вычислить число входящих (<math>in(v)</math>) и исходящих (<math>out(v)</math>) дуг <math>(v, u) \in E</math>, таких, что вершина <math>u</math> - активная. | ||
| + | |||
| + | 3. Все вершины <math>v \in V</math> , для которых <math>in(v)</math> или <math>out(v)</math> равно нулю, пометить как неактивные. | ||
| + | |||
| + | 4. Переходить на шаг 2, до тех пор, пока число активных вершин не перестанет изменяться. | ||
| + | |||
| + | Кроме того, в зависимости от схемы хранения графа может потребоваться предварительное нахождение транспонированного к нему для более эффективной реализации как шага trim, так и поиска вершин, из которых достижима заданная вершина <math>v</math> в вычислительном ядре алгоритма. | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| + | |||
| + | Последовательный алгоритм реализуется следующим псевдокодом: | ||
| + | |||
| + | '''Входные данные''': | ||
| + | граф с вершинами ''V'', рёбрами ''E''; | ||
| + | '''Выходные данные''': номера компонент сильной связанности ‘’c’’(‘’v’’) до каждой вершины ''v'' ∈ ''V''. | ||
| + | |||
| + | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия 21:43, 21 июля 2017
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм DCSC[1][2][3] (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит компоненты сильной связности ориентированного графа с ожидаемой работой [math]O(n \ln n)[/math] (при условии ограниченной констатой степени вершин).
Так же алгоритм носит другое название - Forward-Backward (сокр. FB-algorithm), в основном в литературе, связанной с его GPU-реализациями. [4]
Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Кроме того, выделение данных подмножеств и сильно связанной компоненты на каждом шаге так же может производиться параллельно (с использованием параллельных поисков в ширину). Следует отметить, что в данном случае не требуется синхронизации между итерациями поиска в ширину, поскольку требуется только определить достижимые вершины, но не расстояния до них.
Алгоритм хорошо подходит для графов, имеющих небольшое число сильно-связанных компонент большого размера. При значительном увеличении числа сильно связанных компонент сложность данного алгоритма так же значительно увеличивается (пропорционально числу компонент), из-за чего данный алгоритм может стать менее эффективным в сравнении с последовательным алгоритмом Тарьяна, выделяющим сильно-связанные компоненты за один проход по графу.
Для увеличения эффективности работы алгоритма на графах с большим числом тривиальных сильно-связанных компонент (размера 1 или 2), предложена модификация алгоритма: перед началом работы классического алгоритма, производится шаг Trim, описанный в следующих разделах, позволяющий выделять все тривиальные сильно-связанные компоненты. В результате, к примеру в R-MAT графах, после шага Trim в графе остается всего лишь несколько компонент сильной связанности большого размера, на которых алгоритм будет иметь небольшую алгоритмическую сложность.
1.2 Математическое описание алгоритма
Пусть [math]v[/math] – некоторая вершина графа. Определим следующие множества вершин:
⎯ [math]Fwd(v)[/math] – вершины, достижимые из [math]v[/math] .
⎯ [math]Pred(v)[/math] – вершины, из которых достижима [math]v[/math] (эквивалентно – вершины, достижимые из [math]v[/math] в графе, полученном из [math]G[/math] обращением всех рёбер).
Используя эти множества, разобьём все вершины графа на четыре области:
⎯ [math]V_1 = Fwd(v) \cap Pred(v) [/math]
⎯ [math]V_2 = Fwd(v) \setminus Pred(v) [/math]
⎯ [math]V_3 = Pred(v) \setminus Fwd(v)[/math]
⎯ [math]V_4 = V \setminus Pred(v) \setminus Fwd(v)[/math]
Тогда можно утверждать следующее:
1. Область [math]V_1[/math] является компонентой сильной связности.
2. Любая другая компонента сильной связности полностью содержится в одной из областей [math]V_2[/math], [math]V_3[/math], или [math]V_4[/math].
1.3 Вычислительное ядро алгоритма
Основными вычислительными операциями алгоритма является поиск вершин, достижимых из выбранной вершины [math]v[/math], а так же поиск вершин, из которых достижима выбранная вершина [math]v[/math]. Обе данные операции могут быть реализованы через поиски в ширину, устроенные следующим образом:
1. Вершина [math]v_0[/math] помещается в начало в очереди и помечается ее как посещенная
2. Верхняя вершина [math]v[/math] извлекается из очереди. Для всех ребер [math](v, u)[/math], исходящих из вершины [math]v[/math], проверяется, является ли посещенной вершина [math]u[/math]. В случае, если является, вершина [math]u[/math] помещается в начало очереди.
3. Происходит переход на шаг 2 до тех пор, пока в очереди есть вершины.
1.4 Макроструктура алгоритма
Алгоритм DCSC состоит в следующем:
1. Поместить в очередь множество [math]V[/math].
2. Параллельно обрабатывать очередь. Для каждого элемента очереди [math]V[/math]:
а) Выбрать произвольную ведущую вершину [math]v \in V[/math].
б) Вычислить множества [math]Fwd(v)[/math], [math]Pred(v)[/math] (эти два вычисления можно производить параллельно, кроме того, как указано выше, сами эти вычисления хорошо параллелизуются).
в) Добавить множество [math] V_1[/math] в список компонент сильной связности.
г) Добавить множества [math] V_2[/math], [math]V_3[/math] и [math]V_4[/math] в очередь.
3. Алгоритм завершает работу, когда очередь пуста и не осталось активных процессов-обработчиков.
Для улучшения балансировки нагрузки на первых шагах можно выбирать не одну ведущую вершину, а сразу несколько. Тогда, если они принадлежат различным компонентам связности, граф будет сразу разбит на большое количество областей, которые будут далее обрабатываться параллельно.
Важной модификацией алгоритма является шаг Trim, производимый перед основными вычислениями алгоритма DCSC, который может быть описан следующим образом:
1. Пометить все вершины из [math]v \in V[/math] активными.
2. Для каждой вершины [math]v[/math]вычислить число входящих ([math]in(v)[/math]) и исходящих ([math]out(v)[/math]) дуг [math](v, u) \in E[/math], таких, что вершина [math]u[/math] - активная.
3. Все вершины [math]v \in V[/math] , для которых [math]in(v)[/math] или [math]out(v)[/math] равно нулю, пометить как неактивные.
4. Переходить на шаг 2, до тех пор, пока число активных вершин не перестанет изменяться.
Кроме того, в зависимости от схемы хранения графа может потребоваться предварительное нахождение транспонированного к нему для более эффективной реализации как шага trim, так и поиска вершин, из которых достижима заданная вершина [math]v[/math] в вычислительном ядре алгоритма.
1.5 Схема реализации последовательного алгоритма
Последовательный алгоритм реализуется следующим псевдокодом:
Входные данные: граф с вершинами V, рёбрами E; Выходные данные: номера компонент сильной связанности ‘’c’’(‘’v’’) до каждой вершины v ∈ V.
1.6 Последовательная сложность алгоритма
Ожидаемая последовательная сложность алгоритма составляет [math]O(n \ln n)[/math] при условии, что степень вершин ограничена сверху константой.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Алгоритм не подходит для графов, в которых имеется малое число компонент сильной связности, так как ход исполнения алгоритма в этом случае фактически является последовательным.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- C++, MPI: Parallel Boost Graph Library (функция
strong_components), распределённый алгоритм DCSC сочетается с локальным поиском компонент сильной связности алгоритмом Тарьяна.
3 Литература
- ↑ Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.
- ↑ McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.
- ↑ Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.
- ↑ Jiˇr ́ı Barnat, Petr Bauch, Lubosˇ Brim, and Milan Cˇesˇka. Computing Strongly Connected Components in Parallel on CUDA. Faculty of Informatics, Masaryk University, Botanicka ́ 68a, 60200 Brno, Czech Republic.
