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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Следующая правка →
Общее описание алгоритма
 
Нет описания правки
Строка 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 />


<references />
[[Категория:Начатые статьи]]

Версия от 11:27, 29 июля 2015

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

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

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

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

Вычислительное ядро алгоритма

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

Схема реализации последовательного алгоритма

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

Последовательный вариант алгоритма аналогичен алгоритму Тарьяна[4] и имеет линейную сложность [math]\displaystyle{ O(m + n) }[/math].

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

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

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

Входные и выходные данные алгоритма

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

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

Особенности реализации последовательного алгоритма

Локальность данных и вычислений

Локальность реализации алгоритма

Структура обращений в память и качественная оценка локальности
Количественная оценка локальности

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

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

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

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

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Литература

  1. ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  2. ↑ 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
  3. ↑ 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.
  4. ↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Алгоритм_Тарьяна-Вишкина_поиска_компонент_двусвязности&oldid=2281