Параллельные алгоритмы для минимальных остовных деревьев

В теории графов минимальное остовное дерево (MST). $T$ графика ​ $G=(V,E)$ с $|V|=n$ и $|E|=m$ является дерева подграфом ​ $G$ который содержит все свои вершины и имеет минимальный вес.

MST — это полезные и универсальные инструменты, используемые в самых разных практических и теоретических областях. Например, компания, желающая поставлять в несколько магазинов определенный продукт с одного склада, может использовать MST, исходящий со склада, для расчета кратчайших путей к каждому магазину компании. В этом случае магазины и склад представляются вершинами, а дорожные соединения между ними - ребрами. На каждом ребре указана длина соответствующего дорожного соединения.

Если $G$ не имеет веса по ребрам, каждое остовное дерево имеет одинаковое количество ребер и, следовательно, одинаковый вес. В случае с взвешиванием по ребрам остовное дерево, сумма весов ребер которого наименьшая среди всех остовных деревьев $G$, называется минимальным связующим деревом (MST). Оно не обязательно уникально. В более общем смысле, графы, которые не обязательно связаны , имеют минимальные остовные леса , которые состоят из объединения MST для каждого связного компонента .

Поскольку поиск MST является широко распространенной проблемой в теории графов, существует множество последовательных алгоритмов ее решения. Среди них алгоритмы Прима , Крускала и Борувки , каждый из которых использует разные свойства MST. Все они действуют схожим образом – это подмножество $E$ итеративно увеличивается до тех пор, пока не будет обнаружен действительный MST. Однако, поскольку практические проблемы зачастую весьма велики (дорожные сети иногда имеют миллиарды ребер), производительность ключевым фактором является . Одним из вариантов его улучшения является распараллеливание известных алгоритмов MST .

Алгоритм Прима

Этот алгоритм использует свойство обрезки MST. Простая реализация псевдокода высокого уровня представлена ​​ниже:

$T\gets \emptyset$
$S\gets \{s\}$ where $s$ is a random vertex in $V$
repeat $|V|-1$ times
    find lightest edge $(u,v)$ s.t. $u\in S$ but $v\in (V\setminus S)$
    $S\gets S\cup \{v\}$
    $T\gets T\cup \{(u,v)\}$
return T

Каждое ребро наблюдается ровно дважды — а именно при рассмотрении каждого из его концов. Каждая вершина проверяется ровно один раз, всего $O(n+m)$ помимо выбора самого легкого ребра на каждой итерации цикла. Этот выбор часто выполняется с использованием очереди приоритетов (PQ). Для каждого ребра не более одной операции уменьшенияKey ( амортизируется в $O(1)$) выполняется, и каждая итерация цикла выполняет одну операцию deleteMin ( $O(\log n)$). Таким образом, при использовании кучи Фибоначчи общее время выполнения алгоритма Прима асимптотически составляет $O(m+n\log n)$.

Важно отметить, что цикл по своей сути является последовательным и не может быть должным образом распараллелен. Это так, поскольку самое легкое ребро с одной конечной точкой в $S$ и дальше в $V\setminus S$ может измениться с добавлением ребер к $T$. Таким образом, одновременно невозможно выполнить два выбора самой светлой кромки. Тем не менее, существуют некоторые попытки распараллеливания .

Одна из возможных идей — использовать $O(n)$ процессоры для поддержки доступа PQ в $O(1)$ на машине EREW-PRAM , тем самым снижая общее время выполнения до $O(n+m)$.

Алгоритм Краскала

Алгоритм MST Крускала использует свойство цикла MST. Представление псевдокода высокого уровня представлено ниже.

$T\gets$ forest with every vertex in its own subtree
foreach $(u,v)\in E$ in ascending order of weight
    if $u$ and $v$ in different subtrees of $T$
        $T\gets T\cup \{(u,v)\}$
return T

Поддеревья $T$ хранятся в структурах данных поиска объединения , поэтому проверка того, находятся ли две вершины в одном поддереве, возможна в амортизированных $O(\alpha (m,n))$ где $\alpha (m,n)$ – обратная функция Аккермана . Таким образом, общее время работы алгоритма составляет $O(sort(n)+\alpha (n))$. Здесь $\alpha (n)$ обозначает однозначную обратную функцию Аккермана, для которой любой реалистичный ввод дает целое число меньше пяти.

Подход 1: Распараллеливание этапа сортировки

Как и в алгоритме Прима, в подходе Краскала есть компоненты, которые невозможно распараллелить в его классическом варианте. Например, определение того, находятся ли две вершины в одном и том же поддереве, сложно распараллелить, поскольку две операции объединения могут попытаться соединить одни и те же поддеревья одновременно. На самом деле единственная возможность распараллеливания заключается в этапе сортировки. Поскольку в оптимальном случае сортировка линейна по $O(\log n)$ процессоров, общее время работы может быть сокращено до $O(m\alpha (n))$.

Подход 2: Фильтр-Краскал

Другой подход заключался бы в изменении исходного алгоритма путем увеличения $T$ более агрессивно. Эту идею высказали Осипов и др. Основная идея Filter-Kruskal состоит в том, чтобы разделить ребра аналогично быстрой сортировке и отфильтровать ребра, соединяющие вершины, принадлежащие одному и тому же дереву, чтобы снизить стоимость сортировки. Представление псевдокода высокого уровня представлено ниже.

filterKruskal($G$):
if $m<$ KruskalThreshold:
    return kruskal($G$)
pivot = chooseRandom($E$)
$(E_{\leq }$, $E_{>})\gets$partition($E$, pivot)
$A\gets$ filterKruskal($E_{\leq }$)
$E_{>}\gets$ filter($E_{>}$)
$A\gets A$ $\cup$ filterKruskal($E_{>}$)
return $A$

partition($E$, pivot):
$E_{\leq }\gets \emptyset$ 
$E_{>}\gets \emptyset$
foreach $(u,v)\in E$:
    if weight($u,v$) $\leq$ pivot:
        $E_{\leq }\gets E_{\leq }\cup {(u,v)}$ 
    else
        $E_{>}\gets E_{>}\cup {(u,v)}$
return ($E_{\leq }$, $E_{>}$)

filter($E$):
$E_{filtered}\gets \emptyset$
foreach $(u,v)\in E$:
    if find-set(u) $\neq$ find-set(v):
        $E_{filtered}\gets E_{filtered}\cup {(u,v)}$
return $E_{filtered}$

Filter-Kruskal лучше подходит для распараллеливания, поскольку сортировка, секционирование и фильтрация интуитивно легко распараллеливаются, когда ребра просто делятся между ядрами.

Алгоритм Блуберри

Основная идея алгоритма Борувки — сжатие ребер . Край $\{u,v\}$ сокращается при первом удалении $v$ из графа, а затем перенаправляя каждое ребро $\{w,v\}\in E$ к $\{w,u\}$. Эти новые ребра сохраняют свой старый вес ребер. Если цель состоит не только в определении веса MST, но и в том, какие ребра в него входят, необходимо отметить, между какими парами вершин сжималось ребро. Представление псевдокода высокого уровня представлено ниже.

$T\gets \emptyset$
while $|V|>1$
    $S\gets \emptyset$ 
    for $v\in V$
        $S\gets S$ $\cup$ lightest $\{u,v\}\in E$
    for $\{u,v\}\in S$
        contract $\{u,v\}$
    $T\gets T\cup S$
return T

Возможно, что сокращения приводят к образованию нескольких ребер между парой вершин. Интуитивный способ выбора самого легкого из них невозможен в $O(m)$. Однако, если все сокращения, имеющие общую вершину, выполняются параллельно, это выполнимо. Рекурсия останавливается, когда остается только одна вершина, что означает, что алгоритму требуется не более $\log n$ итераций, что приводит к общему времени выполнения в $O(m\log n)$.

Распараллеливание

Одно из возможных распараллеливаний этого алгоритма дает полилогарифмическую временную сложность, т.е. $T(m,n,p)\cdot p\in O(m\log n)$ и существует константа $c$ так что $T(m,n,p)\in O(\log ^{c}m)$. Здесь $T(m,n,p)$ обозначает время выполнения графа с $m$ края, $n$ вершины на машине с $p$ процессоры. Основная идея заключается в следующем:

while $|V|>1$
    find lightest incident edges // $O({\frac {m}{p}}+\log n+\log p)$
    assign the corresponding subgraph to each vertex // $O({\frac {n}{p}}+\log n)$
    contract each subgraph // $O({\frac {m}{p}}+\log n)$

Тогда MST состоит из всех найденных легчайших ребер.

Это распараллеливание использует представление графа массива смежности для $G=(V,E)$. Он состоит из трех массивов - $\Gamma$ длины $n+1$ для вершин, $\gamma$ длины $m$ для конечных точек каждого из $m$ края и $c$ длины $m$ для веса ребер. Теперь о вершине $i$ другой конец каждого ребра, инцидентного $i$ можно найти в записях между $\gamma [\Gamma [i-1]]$ и $\gamma [\Gamma [i]]$. Вес $i$-е ребро в $\Gamma$ можно найти в $c[i]$. Тогда $i$-е ребро в $\gamma$ находится между вершинами $u$ и $v$ тогда и только тогда, когда $\Gamma [u]\leq i<\Gamma [u+1]$ и $\gamma [i]=v$.

Нахождение самого легкого падающего края

Сначала ребра распределяются между каждым из $p$ процессоры. $i$-ый процессор получает ребра, хранящиеся между $\gamma [{\frac {im}{p}}]$ и $\gamma [{\frac {(i+1)m}{p}}-1]$. Кроме того, каждому процессору необходимо знать, какой вершине принадлежат эти ребра (поскольку $\gamma$ сохраняет только одну из конечных точек ребра) и сохраняет ее в массиве $pred$. Получить эту информацию можно в $O(\log n)$ с использованием $p$ двоичный поиск или в $O({\frac {n}{p}}+p)$ используя линейный поиск. На практике последний подход иногда оказывается быстрее, хотя асимптотически хуже.

Теперь каждый процессор определяет самое легкое ребро, инцидентное каждой из его вершин.

$v\gets$ find(${\frac {im}{p}}$, $\Gamma$)
for $e\gets {\frac {im}{p}};e<{\frac {(i+1)m}{p}}-1;e++$
    if $\Gamma [v+1]=e$
        $v++$
    if$c[e]<c[pred[v]]$
        $pred[v]\gets e$

Здесь возникает проблема: некоторые вершины обрабатываются более чем одним процессором. Возможное решение этой проблемы состоит в том, что каждый процессор имеет свой собственный $prev$ массив, который позже объединяется с остальными с помощью сокращения. Каждый процессор имеет не более двух вершин, которые также обрабатываются другими процессорами, и каждое сокращение находится в $O(\log p)$. Таким образом, общее время выполнения этого шага составляет $O({\frac {m}{p}}+\log n+\log p)$.

Присвоение подграфов вершинам

Посмотрите на граф, состоящий исключительно из ребер, собранных на предыдущем шаге. Эти ребра направлены от вершины, к которой они относятся самым легким ребром. Полученный граф разлагается на множество слабосвязных компонентов. Цель этого шага — назначить каждой вершине компонент, частью которого она является. Обратите внимание, что каждая вершина имеет ровно одно выходящее ребро, и поэтому каждый компонент представляет собой псевдодерево — дерево с одним дополнительным ребром, которое идет параллельно самому легкому ребру компонента, но в противоположном направлении. Следующий код преобразует это дополнительное ребро в цикл:

parallel forAll $v\in V$ 
    $w\gets pred[v]$
    if $pred[w]=v\land v<w$ 
        $pred[v]\gets v$

Теперь каждый слабосвязный компонент представляет собой ориентированное дерево, в корне которого есть цикл . Этот корень выбран в качестве представителя каждого компонента. Следующий код использует удвоение, чтобы назначить каждой вершине ее представителя:

while $\exists v\in V:pred[v]\neq pred[pred[v]]$
    forAll $v\in V$ 
        $pred[v]\gets pred[pred[v]]$

Теперь каждый подграф — это звезда . При использовании некоторых передовых методов этот шаг требует $O({\frac {n}{p}}+\log n)$ время.

Сокращение подграфов

На этом этапе каждый подграф сжимается до одной вершины.

$k\gets$ number of subgraphs
$V'\gets \{0,\dots ,k-1\}$
find a bijective function $f:$ star root $\rightarrow \{0,\dots ,k-1\}$ 
$E'\gets \{(f(pred[v]),f(pred[w]),c,e_{old}):(v,w)\in E\land pred[v]\neq pred[w]\}$

Нахождение биективной функции возможно в $O({\frac {n}{p}}+\log p)$ используя префиксную сумму. Поскольку теперь у нас есть новый набор вершин и ребер, массив смежности необходимо перестроить, что можно сделать с помощью Integersort на $E'$ в $O({\frac {m}{p}}+\log p)$ время.

Сложность

Теперь каждая итерация требует $O({\frac {m}{p}}+\log n)$ время и, как и в последовательном случае, существуют $\log n$ итераций, в результате чего общее время выполнения $O(\log n({\frac {m}{p}}+\log n))$. Если $m\in \Omega (p\log ^{2}p)$ эффективность алгоритма находится в $\Theta (1)$ и это относительно эффективно. Если $m\in O(n)$ тогда это абсолютно эффективно.

Дальнейшие алгоритмы

Существует множество других параллельных алгоритмов, которые решают задачу поиска MST. При линейном числе процессоров этого можно добиться в $O(\log n)$. Бадер и Конг представили MST-алгоритм, который на восьми ядрах был в пять раз быстрее оптимального последовательного алгоритма.

Еще одна проблема - это модель внешней памяти - существует алгоритм, предложенный Дементьевым и др. утверждается, что он всего в два-пять раз медленнее, чем алгоритм, использующий только внутреннюю память.