Параллельные алгоритмы для минимальных остовных деревьев - Parallel algorithms for minimum spanning trees

В теории графов минимальное покрывающее дерево (MST) из графа с и представляет собой дерево подграф из который содержит все его вершины и имеет минимальный вес. ${\ displaystyle T}$ ${\ Displaystyle G = (V, E)}$${\ Displaystyle | V | = п}$${\ displaystyle | E | = m}$ ${\ displaystyle G}$

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

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

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

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

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

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

Каждое ребро наблюдается ровно дважды, а именно при проверке каждой из его конечных точек. Каждая вершина проверяется ровно один раз для общего количества операций, не считая выбора самого светлого ребра на каждой итерации цикла. Этот выбор часто выполняется с использованием очереди приоритетов (PQ). Для каждого ребра при более одной операции decreaseKey ( амортизируется в ) выполняется , и каждый цикл итерации выполняет одну операцию deleteMin ( ). Таким образом , с помощью чисел Фибоначчи осыпает общее время выполнения алгоритма Прима является асимптотически в . ${\ Displaystyle О (п + т)}$${\ displaystyle O (1)}$${\ Displaystyle О (\ журнал п)}$${\ Displaystyle О (т + п \ журнал п)}$

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

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

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

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

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

Поддеревья хранятся в структурах данных union-find , поэтому проверка того, находятся ли две вершины в одном поддереве, возможна в амортизированной, где - обратная функция Аккермана . Таким образом, общее время выполнения алгоритма составляет . Здесь обозначает однозначную обратную функцию Аккермана, для которой любой реалистичный ввод дает целое число меньше пяти. ${\ displaystyle T}$${\ Displaystyle О (\ альфа (т, п))}$${\ Displaystyle \ альфа (м, п)}$${\ Displaystyle О (сортировка (п) + \ альфа (п))}$${\ Displaystyle \ альфа (п)}$

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

Как и в алгоритме Прима, в подходе Крускала есть компоненты, которые нельзя распараллелить в его классическом варианте. Например, определение того, находятся ли две вершины в одном поддереве, трудно распараллелить, поскольку две операции объединения могут попытаться объединить одни и те же поддеревья одновременно. На самом деле единственная возможность распараллеливания - это этап сортировки. Поскольку сортировка в оптимальном случае на процессорах линейна , общее время работы может быть уменьшено до . ${\ Displaystyle О (\ журнал п)}$${\ Displaystyle О (м \ альфа (п))}$

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

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

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

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

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

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

Алгоритм Борувки

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

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

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

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

Одно возможное распараллеливание этого алгоритма дает полилогарифмическую временную сложность, т. Е. Существует константа, так что . Здесь обозначает время выполнения графа с ребрами, вершинами на машине с процессорами. Основная идея заключается в следующем: ${\ Displaystyle Т (т, п, р) \ CDOT р \ в О (м \ журнал п)}$${\ displaystyle c}$${\ Displaystyle Т (т, п, р) \ в О (\ журнал ^ {с} м)}$${\ Displaystyle Т (т, п, р)}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle p}$

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

Затем MST состоит из всех найденных самых светлых ребер.

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

Поиск самого легкого края инцидента

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

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

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

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

Назначение подграфов вершинам

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

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

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

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

Теперь каждый подграф - это звезда . С некоторыми продвинутыми техниками этот шаг требует времени. ${\ Displaystyle О ({\ гидроразрыва {п} {p}} + \ log п)}$

Сужение подграфов

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

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

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

Сложность

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

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

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

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

Рекомендации