4446
правок
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями
Материал из WEGA
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев (посмотреть исходный код)
Версия от 20:57, 27 марта 2016
, 27 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== Основные результаты == | == Основные результаты == | ||
Задача нахождения минимального остовного дерева (MST) связана с задачей нахождения компоненты связности (CC) неориентированного графа. Последовательные алгоритмы решения задач CC и MST за время O(m) и O(m log n), соответственно, известны уже несколько десятилетий. Также было предложено несколько более эффективных алгоритмов MST, в том числе недавний алгоритм Петти-Рамачандрана [9], являющийся доказуемо оптимальным. | Задача нахождения минимального остовного дерева (MST) связана с задачей нахождения [[компонента связности|компоненты связности]] (CC) неориентированного графа. Последовательные алгоритмы решения задач CC и MST за время O(m) и O(m log n), соответственно, известны уже несколько десятилетий. Также было предложено несколько более эффективных алгоритмов MST, в том числе недавний алгоритм Петти-Рамачандрана [9], являющийся доказуемо оптимальным. | ||
| Строка 40: | Строка 40: | ||
Алгоритм для EREW с временем исполнения O(log n), предложенный в [ ], основан на некоторых структурных свойствах, связанных с минимальными остовными деревьями, и способен вычислять элементы Bi более независимым образом. У этого алгоритма имеются blog nc одновременных потоков (поток представляет собой группу процессоров). Для 1 < i < blog nc , поток (i) пытается вычислить Bi, начиная работу задолго до того, как поток (i-1) вычислит Bi-1, и получая результаты работы потоков от 1 до i-1 (т.е. Bi,--- ; 5;-i) по мере продвижения. Говоря более точно, алгоритм выполняется за blog nc меташагов, где каждый меташаг выполняется за время O(1). Поток (i) выдает в результате Bi по окончании i-го меташага. Вычисление потока (i) разбито на blog ic фаз. Вначале рассмотрим простой случай, когда i представляет собой степень двойки. Фаза 1 потока (i) начинается на (i/2 + 1)-м меташагу, т.е. когда B1 ; ■ ■ ; B i/2 уже доступны. Фаза 1 занимает не более i/4 меташагов и заканчивается на (i/2 + i/4)-м меташагу. Фаза 2 начинается на (i/2 + i/4 + 1)-м меташагу, т.е. когда уже доступны Bi/2+1; • • ; B i /2+i/4, и занимает i/8 меташагов. Каждая последующая фаза использует вдвое меньше меташагов, чем предшествующая ей. Последняя фаза (log i) начинается и заканчивается на i-м меташагу; заметим, что B доступно после (i-1)-го меташага. | Алгоритм для EREW с временем исполнения O(log n), предложенный в [ ], основан на некоторых структурных свойствах, связанных с минимальными остовными деревьями, и способен вычислять элементы Bi более независимым образом. У этого алгоритма имеются blog nc одновременных потоков (поток представляет собой группу процессоров). Для 1 < i < blog nc , поток (i) пытается вычислить Bi, начиная работу задолго до того, как поток (i-1) вычислит Bi-1, и получая результаты работы потоков от 1 до i-1 (т.е. Bi,--- ; 5;-i) по мере продвижения. Говоря более точно, алгоритм выполняется за blog nc меташагов, где каждый меташаг выполняется за время O(1). Поток (i) выдает в результате Bi по окончании i-го меташага. Вычисление потока (i) разбито на blog ic фаз. Вначале рассмотрим простой случай, когда i представляет собой степень двойки. Фаза 1 потока (i) начинается на (i/2 + 1)-м меташагу, т.е. когда B1 ; ■ ■ ; B i/2 уже доступны. Фаза 1 занимает не более i/4 меташагов и заканчивается на (i/2 + i/4)-м меташагу. Фаза 2 начинается на (i/2 + i/4 + 1)-м меташагу, т.е. когда уже доступны Bi/2+1; • • ; B i /2+i/4, и занимает i/8 меташагов. Каждая последующая фаза использует вдвое меньше меташагов, чем предшествующая ей. Последняя фаза (log i) начинается и заканчивается на i-м меташагу; заметим, что B доступно после (i-1)-го меташага. | ||
== Применение == | == Применение == | ||
