Algoritmos paralelos para árvores geradoras mínimas - Parallel algorithms for minimum spanning trees

Na teoria dos grafos, uma árvore geradora mínima (MST) de um gráfico com e é um subgrafo de árvore que contém todos os seus vértices e tem peso mínimo. ${\ displaystyle T}$ ${\ displaystyle G = (V, E)}$${\ displaystyle | V | = n}$${\ displaystyle | E | = m}$ ${\ displaystyle G}$

MSTs são ferramentas úteis e versáteis utilizadas em uma ampla variedade de campos práticos e teóricos. Por exemplo, uma empresa que deseja fornecer a várias lojas um determinado produto de um único depósito pode usar um MST originado no depósito para calcular os caminhos mais curtos para cada loja da empresa. Neste caso, as lojas e o armazém são representados como vértices e as ligações rodoviárias entre eles - como bordas. Cada borda é identificada com o comprimento da conexão rodoviária correspondente.

Se é ponta-não ponderada cada árvore estendida possui o mesmo número de arestas e, portanto, o mesmo peso. No caso de arestas ponderadas , a árvore geradora, cuja soma dos pesos das arestas é a menor entre todas as árvores abrangentes de , é chamada de árvore geradora mínima (MST). Não é necessariamente único. De maneira mais geral, os gráficos que não estão necessariamente conectados têm florestas abrangentes mínimas , que consistem em uma união de MSTs para cada componente conectado . ${\ displaystyle G}$${\ displaystyle G}$

Como encontrar MSTs é um problema difundido na teoria dos grafos, existem muitos algoritmos sequenciais para resolvê-lo. Entre eles estão os algoritmos de Prim , Kruskal e Borůvka , cada um utilizando propriedades diferentes de MSTs. Todos eles operam de maneira semelhante - um subconjunto de é crescido iterativamente até que um MST válido seja descoberto. No entanto, como os problemas práticos geralmente são muito grandes (as redes rodoviárias às vezes têm bilhões de bordas), o desempenho é um fator chave. Uma opção para melhorá-lo é paralelizar algoritmos MST conhecidos . ${\ displaystyle E}$

Algoritmo de Prim

Este algoritmo utiliza a propriedade cut de MSTs. Uma implementação simples de pseudocódigo de alto nível é fornecida abaixo:

${\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

Cada aresta é observada exatamente duas vezes - ou seja, ao examinar cada um de seus pontos finais. Cada vértice é examinado exatamente uma vez para um total de operações além da seleção da aresta mais leve em cada iteração do loop. Essa seleção geralmente é realizada usando uma fila de prioridade (PQ). Para cada borda, no máximo, uma operação diminuiKey ( amortizada em ) é realizada e cada iteração de loop realiza uma operação deleteMin ( ). Assim, usando pilhas de Fibonacci, o tempo de execução total do algoritmo de Prim é assintoticamente em . ${\ displaystyle O (n + m)}$${\ displaystyle O (1)}$${\ displaystyle O (\ log n)}$${\ displaystyle O (m + n \ log n)}$

É importante observar que o loop é inerentemente sequencial e não pode ser devidamente paralelizado. Este é o caso, uma vez que a aresta mais clara com um ponto final dentro e dentro pode mudar com a adição de arestas a . Assim, duas seleções de uma aresta mais clara não podem ser executadas ao mesmo tempo. No entanto, existem algumas tentativas de paralelização . ${\ displaystyle S}$${\ displaystyle V \ setminus S}$${\ displaystyle T}$

Uma ideia possível é usar processadores para suportar o acesso PQ em uma máquina EREW-PRAM , reduzindo assim o tempo de execução total para . ${\ displaystyle O (n)}$${\ displaystyle O (1)}$${\ displaystyle O (n + m)}$

Algoritmo de Kruskal

O algoritmo MST de Kruskal utiliza a propriedade de ciclo dos MSTs. Uma representação de pseudocódigo de alto nível é fornecida abaixo.

${\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

As subárvores de são armazenadas em estruturas de dados union-find , e é por isso que verificar se dois vértices estão ou não na mesma subárvore é possível em amortizado onde está a função de Ackermann inversa . Portanto, o tempo de execução total do algoritmo está em . Aqui denota a função de Ackermann inversa de valor único, para a qual qualquer entrada realista produz um número inteiro menor que cinco. ${\ displaystyle T}$${\ displaystyle O (\ alpha (m, n))}$${\ displaystyle \ alpha (m, n)}$${\ displaystyle O (sort (n) + \ alpha (n))}$${\ displaystyle \ alpha (n)}$

Abordagem 1: paralelizando a etapa de classificação

Similarmente ao algoritmo de Prim, existem componentes na abordagem de Kruskal que não podem ser paralelizados em sua variante clássica. Por exemplo, determinar se dois vértices estão ou não na mesma subárvore é difícil de paralelizar, pois duas operações de união podem tentar unir as mesmas subárvores ao mesmo tempo. Na verdade, a única oportunidade para paralelização está na etapa de classificação. Como a classificação é linear no caso ideal dos processadores, o tempo de execução total pode ser reduzido para . ${\ displaystyle O (\ log n)}$${\ displaystyle O (m \ alpha (n))}$

Abordagem 2: Filtro-Kruskal

Outra abordagem seria modificar o algoritmo original crescendo de forma mais agressiva. Essa ideia foi apresentada por Osipov et al. A ideia básica por trás do Filter-Kruskal é particionar as arestas de maneira semelhante ao quicksort e filtrar as arestas que conectam vértices que pertencem à mesma árvore, a fim de reduzir o custo de classificação. Uma representação de pseudocódigo de alto nível é fornecida abaixo. ${\ 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}}$

O Filter-Kruskal é mais adequado para paralelização, uma vez que a classificação, particionamento e filtragem têm paralelizações intuitivamente fáceis, onde as bordas são simplesmente divididas entre os núcleos.

Algoritmo de Borůvka

A ideia principal por trás do algoritmo de Borůvka é a contração da borda . Uma aresta é contraída removendo primeiro do gráfico e, em seguida, redirecionando cada aresta para . Essas novas arestas mantêm seus antigos pesos de aresta. Se o objetivo não é apenas determinar o peso de um MST, mas também quais arestas ele compreende, deve-se notar entre quais pares de vértices uma aresta foi contraída. Uma representação de pseudocódigo de alto nível é apresentada a seguir. ${\ displaystyle \ {u, v \}}$${\ displaystyle v}$${\ displaystyle \ {w, v \} \ in E}$${\ displaystyle \ {w, u \}}$

${\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

É possível que as contrações levem a várias arestas entre um par de vértices. A forma intuitiva de escolher o mais leve deles não é possível em . No entanto, se todas as contrações que compartilham um vértice forem executadas em paralelo, isso é factível. A recursão para quando há apenas um único vértice restante, o que significa que o algoritmo precisa de no máximo iterações, levando a um tempo de execução total em . ${\ displaystyle O (m)}$${\ displaystyle \ log n}$${\ displaystyle O (m \ log n)}$

Paralelização

Uma possível paralelização desse algoritmo resulta em uma complexidade de tempo polilogarítmica , ou seja, e existe uma constante para que . Aqui denota o tempo de execução de um gráfico com arestas, vértices em uma máquina com processadores. A ideia básica é a seguinte: ${\ displaystyle T (m, n, p) \ cdot p \ in O (m \ log n)}$${\ displaystyle c}$${\ displaystyle T (m, n, p) \ in O (\ log ^ {c} m)}$${\ displaystyle T (m, n, p)}$${\ 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)}$

O MST, então, consiste em todas as arestas mais claras encontradas.

Esta paralelização utiliza a representação gráfica de matriz de adjacência para . Este consiste em três matrizes - de comprimento para os vértices, de comprimento para os pontos finais de cada uma das arestas e de comprimento para os pesos das arestas. Agora, para o vértice, a outra extremidade de cada incidente de aresta a pode ser encontrada nas entradas entre e . O peso da -ésima aresta em pode ser encontrado em . Então a -ésima aresta está entre os vértices e se e somente se e . ${\ displaystyle G = (V, E)}$${\ displaystyle \ Gamma}$${\ displaystyle n + 1}$${\ displaystyle \ gamma}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle m}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle \ gamma [\ Gamma [i-1]]}$${\ displaystyle \ gamma [\ Gamma [i]]}$${\ displaystyle i}$${\ displaystyle \ Gamma}$${\ displaystyle c [i]}$${\ displaystyle i}$${\ displaystyle \ gamma}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle \ Gamma [u] \ leq i <\ Gamma [u + 1]}$${\ displaystyle \ gamma [i] = v}$

Encontrando a borda do incidente mais leve

Primeiro, as bordas são distribuídas entre cada um dos processadores. O -ésimo processador recebe as bordas armazenadas entre e . Além disso, cada processador precisa saber a qual vértice essas arestas pertencem (uma vez que armazena apenas um dos pontos finais da aresta) e armazena isso no array . A obtenção dessas informações é possível usando pesquisas binárias ou usando uma pesquisa linear. Na prática, a última abordagem às vezes é mais rápida, embora seja assintoticamente pior. ${\ displaystyle p}$${\ displaystyle i}$${\ displaystyle \ gamma [{\ frac {im} {p}}]}$${\ displaystyle \ gamma [{\ frac {(i + 1) m} {p}} - 1]}$${\ displaystyle \ gamma}$${\ pred displaystyle}$${\ displaystyle O (\ log n)}$${\ displaystyle p}$${\ displaystyle O ({\ frac {n} {p}} + p)}$

Agora, cada processador determina a borda mais leve incidente em cada um de seus vértices.

${\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}$

Aqui surge o problema: alguns vértices são tratados por mais de um processador. Uma possível solução para isso é que cada processador tem seu próprio array que é posteriormente combinado com os dos outros usando uma redução. Cada processador tem no máximo dois vértices que também são tratados por outros processadores e cada redução está em . Portanto, o tempo de execução total desta etapa está em . ${\ displaystyle prev}$${\ displaystyle O (\ log p)}$${\ displaystyle O ({\ frac {m} {p}} + \ log n + \ log p)}$

Atribuição de subgráficos a vértices

Observe o gráfico que consiste apenas em arestas coletadas na etapa anterior. Essas arestas são direcionadas para longe do vértice para o qual são a aresta incidente mais leve. O gráfico resultante se decompõe em vários componentes fracamente conectados. O objetivo desta etapa é atribuir a cada vértice o componente do qual faz parte. Observe que cada vértice tem exatamente uma aresta de saída e, portanto, cada componente é uma pseudo-árvore - uma árvore com uma única aresta extra que corre paralelamente à aresta mais leve do componente, mas na direção oposta. O código a seguir transforma essa borda extra em um loop:

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

Agora, cada componente fracamente conectado é uma árvore direcionada onde a raiz tem um loop . Essa raiz é escolhida como representante de cada componente. O código a seguir usa duplicação para atribuir a cada vértice seu representante:

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

Agora, cada subgrafo é uma estrela . Com algumas técnicas avançadas, esta etapa requer tempo. ${\ displaystyle O ({\ frac {n} {p}} + \ log n)}$

Contraindo os subgráficos

Nesta etapa, cada subgrafo é contraído a um único vértice.

${\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]\}}$

Encontrar a função bijetiva é possível usando uma soma de prefixo. Como agora temos um novo conjunto de vértices e arestas a matriz de adjacência deve ser reconstruída, o que pode ser feito usando Integersort em no tempo. ${\ displaystyle O ({\ frac {n} {p}} + \ log p)}$${\ displaystyle E '}$${\ displaystyle O ({\ frac {m} {p}} + \ log p)}$

Complexidade

Cada iteração agora precisa de tempo e, assim como no caso sequencial, há iterações, resultando em um tempo de execução total de . Se a eficiência do algoritmo está em e é relativamente eficiente. Nesse caso , é absolutamente eficiente. ${\ displaystyle O ({\ frac {m} {p}} + \ log n)}$${\ displaystyle \ log n}$${\ displaystyle O (\ log n ({\ frac {m} {p}} + \ log n))}$${\ displaystyle m \ in \ Omega (p \ log ^ {2} p)}$${\ displaystyle \ Theta (1)}$${\ displaystyle m \ in O (n)}$

Algoritmos adicionais

Existem vários outros algoritmos paralelos que lidam com a questão de encontrar um MST. Com um número linear de processadores, é possível conseguir isso em . Bader e Cong apresentaram um algoritmo MST, que era cinco vezes mais rápido em oito núcleos do que um algoritmo sequencial ideal. ${\ displaystyle O (\ log n)}$

Outro desafio é o modelo de Memória Externa - existe um algoritmo proposto por Dementiev et al. que é afirmado ser apenas duas a cinco vezes mais lento do que um algoritmo que só faz uso da memória interna

Referências