Алгоритм Шилоаха-Вишкина поиска компонент связности
| Алгоритм Шилоаха-Вишкина поиска компонент связности | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O((m + n) \ln n) }[/math] |
| Объём входных данных | [math]\displaystyle{ O(m) }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(\ln n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ n + 2m }[/math] |
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Шилоаха-Вишкина[1] (англ. Shiloach-Vishking Algorithm) предназначен для поиска компонент связности неориентированного графа. Используется структура данных, аналогичная системе непресекающихся множеств. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах.
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Алгоритм изначально параллельный и при последовательной реализации фактически превращается в систему непресекающихся множеств.
Последовательная сложность алгоритма
Последовательная сложность алгоритма Шилоаха-Вишкина [math]\displaystyle{ O((m + n) \ln n) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Время работы алгоритма составляет [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах в модели CRCW PRAM.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]\displaystyle{ O(\log n) }[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.