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

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

В случае EREW PRAM для решения задач CC и MST в начале восьмидесятых были разработаны алгоритмы с временем исполнения <math>O(log^2 \;n)</math>. Некоторое время считалось, что для моделей с эксклюзивной записью (как для случая одновременного чтения, так и для эксклюзивного) невозможно улучшить временную границу <math>O(log^2 \; n)</math> [8]. Первый прорыв совершили Джонсон и Метаксас [6], предложившие алгоритмы с временем исполнения <math>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>\Theta (log \; n)</math> является оптимальным, поскольку данные графовые задачи имеют не меньшую сложность, чем выполнение операции OR для n бит, для которой Кук и коллеги [4] показали, что она требует <math>\Omega (log \; n)</math> времени для PRAM с эксклюзивной записью, независимо от количества используемых процессоров.

Алгоритм для EREW с временем исполнения O(log n), предложенный в [1], основан на некоторых структурных свойствах, связанных с минимальными остовными деревьями, и способен вычислять элементы <math>B_i \;</math> более независимым образом. У этого алгоритма имеются <math>\lfloor log \; n \rfloor</math> одновременных потоков (поток представляет собой группу процессоров). Для <math>1 \le i \le \lfloor log \; n \rfloor</math> поток (i) пытается вычислить <math>B_i \;</math>, начиная работу задолго до того, как поток (i-1) вычислит <math>B_{i-1} \;</math>, и получая результаты работы потоков от 1 до i-1 (т.е. <math>B_1, ..., B_{i-1} \;</math>) по мере продвижения. Говоря более точно, алгоритм выполняется за <math>\lfloor log \; n \rfloor</math> меташагов, где каждый меташаг выполняется за время O(1). Поток (i) выдает в результате <math>B_i \;</math> по окончании i-го меташага. Вычисление потока (i) разбито на <math>\lfloor log \; i \rfloor</math> фаз. Вначале рассмотрим простой случай, когда i представляет собой степень двойки. Фаза 1 потока (i) начинается на (i/2 + 1)-м меташагу, т.е. когда <math>B_1, ..., B_{i/2} \;</math> уже доступны. Фаза 1 занимает не более i/4 меташагов и заканчивается на (i/2 + i/4)-м меташагу. Фаза 2 начинается на (i/2 + i/4 + 1)-м меташагу, т.е. когда уже доступны <math>B_{i/2+1}, ..., B_{i/2 + i/4} \;</math>, и занимает i/8 меташагов. Каждая последующая фаза использует вдвое меньше меташагов, чем предшествующая ей. Последняя фаза (log i) начинается и заканчивается на i-м меташагу; заметим, что <math>B_{i-1} \;</math> доступно после (i-1)-го меташага.

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

* ''[[Рандомизированные алгоритмы аппроксимации максимального потока]]