Алгоритм Тарьяна-Вишкина поиска компонент двусвязности: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | == Свойства и структура алгоритма == |
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Параллельный '''алгоритм Тарьяна-Вишкина''' <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 n)</math> на <math>O(m + n)</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. | Параллельный '''алгоритм Тарьяна-Вишкина''' <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 n)</math> на <math>O(m + n)</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. | ||
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 13: | Строка 13: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
Алгоритм изначально параллельный, время работы <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах. | Алгоритм изначально параллельный, время работы <math>O(\ln n)</math> на <math>O(m + n)</math> процессорах. | ||
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | === | + | === Локальность данных и вычислений === |
| − | === Возможные способы и особенности реализации | + | ==== Локальность реализации алгоритма ==== |
| + | ===== Структура обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Масштабируемость алгоритма ==== | ||
| + | ==== Масштабируемость реализации алгоритма ==== | ||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| + | |||
== Литература == | == Литература == | ||
| + | <references /> | ||
| − | + | [[Категория:Начатые статьи]] | |
Версия 14:27, 29 июля 2015
Содержание
- 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 Общее описание алгоритма
Параллельный алгоритм Тарьяна-Вишкина [1] находит компоненты двухсвязности неориентированного графа за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах. Алгоритм может быть адаптирован для поиска мостов. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время[2][3] как на системах архитектуры SMP, так и при вычислениях на GPU.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Последовательный вариант алгоритма аналогичен алгоритму Тарьяна[4] и имеет линейную сложность [math]O(m + n)[/math].
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм изначально параллельный, время работы [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах.
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 Существующие реализации алгоритма
3 Литература
- ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
- ↑ 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
- ↑ 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.
- ↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
