Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями

Перейти к навигации Перейти к поиску
Строка 39: Строка 39:
(а) Пусть F – множество деревьев, порожденных B на G. Пусть F' – произвольное подмножество F, включающее все деревья <math>T \in F \;</math> с числом вершин меньше <math>2^i \;</math>.
(а) Пусть F – множество деревьев, порожденных B на G. Пусть F' – произвольное подмножество F, включающее все деревья <math>T \in F \;</math> с числом вершин меньше <math>2^i \;</math>.


(б) <math>B_i \leftarrow \{ e \;</math> | ''e'' является минимальным внешним ребром <math>T \in F' \} \;</math>; <math>B \leftarrow B \cup B_i \;</math>
(б) <math>B_i \leftarrow \{ e \;</math> | <math>e \;</math> является минимальным внешним ребром <math>T \in F' \} \;</math>; <math>B \leftarrow B \cup B_i \;</math>


3. '''return''' B
3. '''return''' B




Различные стратегии выбора F0 на шагу 1а могут привести к получению различных Bi. Тем не менее, B[1; i] всегда является подмножеством TQ и порождает 2i-лес. В частности, В [ 1; \lfloor log \; n \rfloor ] порождает ровно одно дерево, которым и является TQ. Используя стандартные техники распараллеливания алгоритмов, каждый шаг можно реализовать за время O(log n) на машине EREW PRAM с линейным числом процессоров (см, например, [ ]). Таким образом, минимальное остовное дерево TQ может быть найдено за время O(log n). Большинство параллельных алгоритмов поиска MST используют подобный подход. Параллельные алгоритмы являются «последовательными» в том смысле, что вычисление Bi начинается только после нахождения Bi-1.
Различные стратегии выбора F' на шагу 2(а) могут привести к получению различных <math>B_i \;</math>. Тем не менее, B[1, i] всегда является подмножеством <math>T^*_G \;</math> и порождает <math>2^i \;</math>-лес. В частности, <math>B[1, \lfloor log \; n \rfloor ]</math> порождает ровно одно дерево, которым и является <math>T^*_G \;</math>. Используя стандартные техники распараллеливания алгоритмов, каждый шаг можно реализовать за время O(log n) на машине EREW PRAM с линейным числом процессоров (см, например, [5]). Таким образом, минимальное остовное дерево <math>T^*_G \;</math> может быть найдено за время <math>O(log^2 \; n)</math>. Большинство параллельных алгоритмов поиска MST используют подобный подход. Параллельные алгоритмы являются «последовательными» в том смысле, что вычисление <math>B_i \;</math> начинается только после нахождения <math>B_{i-1} \;</math>.




Алгоритм для EREW с временем исполнения O(log n), предложенный в [ ], основан на некоторых структурных свойствах, связанных с минимальными остовными деревьями, и способен вычислять элементы Bi более независимым образом. У этого алгоритма имеются <math>\lfloor log \; n \rfloor</math> одновременных потоков (поток представляет собой группу процессоров). Для <math>1 < i < \lfloor log \; n \rfloor</math>, поток (i) пытается вычислить Bi, начиная работу задолго до того, как поток (i-1) вычислит Bi-1, и получая результаты работы потоков от 1 до i-1 (т.е. Bi,--- ; 5;-i) по мере продвижения. Говоря более точно, алгоритм выполняется за <math>\lfloor log \; n \rfloor</math> меташагов, где каждый меташаг выполняется за время O(1). Поток (i) выдает в результате Bi по окончании i-го меташага. Вычисление потока (i) разбито на <math>\lfloor log \; n \rfloor</math> фаз. Вначале рассмотрим простой случай, когда 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), предложенный в [1], основан на некоторых структурных свойствах, связанных с минимальными остовными деревьями, и способен вычислять элементы <math>B_i \;</math> более независимым образом. У этого алгоритма имеются <math>\lfloor log \; n \rfloor</math> одновременных потоков (поток представляет собой группу процессоров). Для <math>1 < i < \lfloor log \; n \rfloor</math>, поток (i) пытается вычислить Bi, начиная работу задолго до того, как поток (i-1) вычислит Bi-1, и получая результаты работы потоков от 1 до i-1 (т.е. Bi,--- ; 5;-i) по мере продвижения. Говоря более точно, алгоритм выполняется за <math>\lfloor log \; n \rfloor</math> меташагов, где каждый меташаг выполняется за время O(1). Поток (i) выдает в результате Bi по окончании i-го меташага. Вычисление потока (i) разбито на <math>\lfloor log \; n \rfloor</math> фаз. Вначале рассмотрим простой случай, когда 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)-го меташага.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Параллельные_алгоритмы_вычисления_компонент_связности_и_минимальных_остовных_деревьев