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

Материал из WEGA
Перейти к навигации Перейти к поиску
Строка 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 на шагу могут привести к получению различных 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)-го меташага.


== Применение ==
== Применение ==

Версия от 21:22, 27 марта 2016

Ключевые слова и синонимы

Алгоритмы EREW PRAM для нахождения компонент связности и минимальных остовных деревьев


Постановка задачи

Пусть дан взвешенный неориентированный граф G с n вершинами и m ребрами. Необходимо вычислить минимальное остовное дерево (или остовный лес) графа G на параллельной машине с произвольным доступом к памяти (parallel random access machine, PRAM) без возможности одновременной записи.


Минимальное остовное дерево графа представляет собой остовное дерево с минимальной возможной суммой весов ребер. Параллельная машина с произвольным доступом к памяти (PRAM) – это абстрактная модель для разработки параллельных алгоритмов и понимания возможностей параллелизма. В этой модели процессоры (каждый из которых является машиной с произвольным доступом к памяти) работают синхронно, обмениваясь друг с другом сообщениями при помощи совместно используемой памяти. PRAM можно различать по тому обстоятельству, разрешается ли более чем одному процессору одновременно производить операции чтения и записи с одной и той же ячейкой совместно используемой памяти. Более строгой является модель с одновременным чтением и одновременной записью CRCW (concurrent-read, concurrent-write), более слабой – с эксклюзивным чтением и эксклюзивной записью, EREW (exclusive-read, exclusive-write). Введение в алгоритмы PRAM см. в работах Карпа и Рамачандрана [8] и Джаджи [5].


Предполагается, что входной граф G представлен в виде списков смежности. Изолированные вершины (имеющие степень 0) удаляются, в результате чего предполагается, что [math]\displaystyle{ m \ge n \; }[/math].

Основные результаты

Задача нахождения минимального остовного дерева (MST) связана с задачей нахождения компоненты связности (CC) неориентированного графа. Последовательные алгоритмы решения задач CC и MST за время O(m) и O(m log n), соответственно, известны уже несколько десятилетий. Также было предложено несколько более эффективных алгоритмов MST, в том числе недавний алгоритм Петти-Рамачандрана [9], являющийся доказуемо оптимальным.


В параллельном контексте эти задачи решаются сходным образом. В случае CRCW PRAM обе задачи можно решить за время O(log n) при помощи n + m процессоров (см, например, Коул и Вишкин [3]). Используя рандомизацию, можно ограничиться для решения (n + m)/log n процессорами с ожидаемым временем исполнения O(log n) [2, 10].


В случае EREW PRAM для решения задач CC и MST в начале восьмидесятых были разработаны алгоритмы с временем исполнения [math]\displaystyle{ O(log^2 \;n) }[/math]. Некоторое время считалось, что для моделей с эксклюзивной записью (как для случая одновременного чтения, так и для эксклюзивного) невозможно улучшить временную границу [math]\displaystyle{ O(log^2 \; n) }[/math] [8]. Первый прорыв совершили Джонсон и Метаксас [6], предложившие алгоритмы с временем исполнения [math]\displaystyle{ O(log^{1.5} \; n) }[/math] для обеих задач. Чонг и Лэм вскоре улучшили этот результат до O(log n log log n). Если допускается рандомизация, то временная сложность может быть уменьшена до ожидаемого времени O(log n) в оптимальном случае [7, 10, 11]. Наконец, Чонг, Хан и Лэм [1] получили алгоритм для задач MST и CC с временем исполнения O(log n) для n + m процессоров, не требующий рандомизации. Заметим, что время [math]\displaystyle{ \Theta (log \; n) }[/math] является оптимальным, поскольку данные графовые задачи имеют не меньшую сложность, чем выполнение операции OR для n бит, для которой Кук и коллеги [4] показали, что она требует [math]\displaystyle{ \Omega (log \; n) }[/math] времени для PRAM с эксклюзивной записью, независимо от количества используемых процессоров.


Рассмотрим примерный подход к вычислению минимального остовного дерева параллельным образом без использования одновременных операций записи.


Без потери общности будем считать, что все веса ребер различны. В таком случае граф G имеет уникальное минимальное остовное дерево; обозначим его как [math]\displaystyle{ T^*_G \; }[/math]. Пусть B – подмножество ребер графа G, не содержащих циклов. B естественным образом порождает множество деревьев [math]\displaystyle{ F = {T_1, T_2, ..., T_l} \; }[/math]: две вершины G принадлежат к одному дереву, если они связаны ребром из множества B. B называется [math]\displaystyle{ \lambda }[/math]-лесом, если каждое дерево [math]\displaystyle{ T \in F \; }[/math] имеет не менее [math]\displaystyle{ \lambda }[/math] вершин. Например, если множество B пусто, то B является 1-лесом; остовное дерево является n-лесом.


Предположим, что B является [math]\displaystyle{ \lambda }[/math]-лесом и все его ребра входят в [math]\displaystyle{ T^*_G \; }[/math]. Тогда B может быть дополнено для получения [math]\displaystyle{ 2 \lambda }[/math]-леса при помощи жадного подхода:

Пусть F' – произвольное подмножество F, включающее все деревья [math]\displaystyle{ T \in F \; }[/math] с числом вершин меньше [math]\displaystyle{ 2 \lambda }[/math]. Для любого дерева из F' выберем его минимальное внешнее ребро (т.е. ребро с минимальным весом, соединяющее его с вершиной вне дерева). Обозначим множество таких ребер за B'. Можно показать, что B' состоит только из ребер, принадлежащих к [math]\displaystyle{ T^*_G \; }[/math], а [math]\displaystyle{ B \cup B' \; }[/math] является [math]\displaystyle{ 2 \lambda }[/math]-лесом. Это обстоятельство позволяет найти [math]\displaystyle{ T^*_G \; }[/math] за [math]\displaystyle{ \lfloor log \; n \rfloor }[/math] шагов следующим образом.


1. [math]\displaystyle{ B \leftarrow \empty \; }[/math]

2. For i = 1 to [math]\displaystyle{ \lfloor log \; n \rfloor }[/math] do /* Шаг i */

(а) Пусть F – множество деревьев, порожденных B на G. Пусть F' – произвольное подмножество F, включающее все деревья [math]\displaystyle{ T \in F \; }[/math] с числом вершин меньше [math]\displaystyle{ 2^i \; }[/math].

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

3. return B


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


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

Применение

Нахождение компонент связности или минимальных остовных деревьев представляет собой важнейший этап нескольких параллельных алгоритмов решения других графовых задач. Например, алгоритм Чонга-Хана-Лэма становится основой для алгоритма вычисления ушной декомпозиции и нахождения двусвязности с временем исполнения O(log n) без использования одновременных операций записи.

См. также

Литература

1. Chong, K.W., Han, Y., Lam, T.W.: Concurrent Threads and Optical Parallel Minimum Spanning Trees Algorithm. J. ACM 48(2), 297-323(2001)

2. Cole, R., Klein, P.N., Tarjan, R.E.: Finding minimum spanning forests in logarithmic time and linear work using random sampling. In: Proceedings of the 8th Annual ACM Symposium on Parallel Architectures and Algorithms, 1996, pp. 243-250

3. Cole, R., Vishkin, U.: Approximate and Exact Parallel Scheduling with Applications to List, Tree, and Graph Problems. In: Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 478-491

4. Cook, S.A., Dwork, C., Reischuk, R.: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. 15(1), 87-97 (1986)

5. JaJa, J.: An Introduction to Parallel Algorithms. Addison-Wesley (1992)

6. Johnson, D.B., Metaxas, P.: Connected Components in O(lg3/2 jVj) Parallel Time for the CREW PRAM. In: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 688-697

7. Karger, D.R.: Random sampling in Graph Optimization Problems. Ph. D. thesis, Department of Computer Science, Stanford University (1995)

8. Karp, R.M., Ramachandran, V.: Parallel Algorithms for Shared-Memory Machines. In: Van Leeuwen Ed, J. (ed) Handbook of Theoretical Computer Science, vol. A, pp. (869-941). MIT Press, Massachusetts (1990)

9. Pettie, S. Ramachandran, V.: An Optimal Minimum Spanning Tree Algorithm. J. ACM 49(1), 16-34 (2002)

10. Pettie, S., Ramachandran, V.: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SIAM J. Comput. 31 (6), 1879-1895 (2002)

11. Poon, C.K., Ramachandran, V.: A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest. Algorithmica 35(3), 257-268 (2003)