Алгоритм DCSC поиска компонент сильной связности: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
ASA (обсуждение | вклад) |
Teplov (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
'''Алгоритм 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> (при условии ограниченной степени вершин). | ||
| + | |||
| + | Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Алгоритм не подходит для графов, в которых имеется малое число компонент сильной связности, так как ход исполнения алгоритма в этом случае фактически является последовательным. | ||
| + | |||
| + | Основной операцией является поиск вершин, достижимых из данной в прямом или обратном направлении. Эта операция реализуется параллельным поиском в ширину. Следует отметить, что в данном случае не требуется синхронизации между итерациями поиска в ширину, поскольку требуется только определить достижимые вершины, но не расстояния до них | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Версия 18:41, 18 ноября 2016
Содержание
- 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] (при условии ограниченной степени вершин).
Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Алгоритм не подходит для графов, в которых имеется малое число компонент сильной связности, так как ход исполнения алгоритма в этом случае фактически является последовательным.
Основной операцией является поиск вершин, достижимых из данной в прямом или обратном направлении. Эта операция реализуется параллельным поиском в ширину. Следует отметить, что в данном случае не требуется синхронизации между итерациями поиска в ширину, поскольку требуется только определить достижимые вершины, но не расстояния до них
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
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.
