最小全域木のための並列アルゴリズム

グラフ理論では、およびのグラフの最小全域木(MST)は、 のすべての頂点を含み、最小の重みを持つ の木サブグラフです。${\displaystyle T}$ ${\displaystyle G=(V,E)}$ ${\displaystyle |V|=n}$ ${\displaystyle |E|=m}$ ${\displaystyle G}$

MSTは、実用的かつ理論的な幅広い分野で活用されている、有用で多用途なツールです。例えば、ある企業が単一の倉庫から複数の店舗に特定の商品を供給したい場合、倉庫を起点とするMSTを用いて、各店舗への最短経路を計算することができます。この場合、店舗と倉庫は頂点として、それらを結ぶ道路は辺として表されます。各辺には、対応する道路の長さがラベル付けされます。

が辺重みなしの場合、すべての全域木は同じ数の辺を持ち、したがって同じ重みを持ちます。辺重み付きの場合、 のすべての全域木の中で、 の辺の重みの合計が最小となる全域木は、最小全域木（MST）と呼ばれます。これは必ずしも一意ではありません。より一般的には、必ずしも連結されていないグラフには、連結成分ごとにMSTの和集合からなる最小全域木（minimum spanning forests）が存在します。 ${\displaystyle G}$ ${\displaystyle G}$

MSTの発見はグラフ理論において広く普及している問題であるため、これを解くための逐次アルゴリズムが数多く存在します。その中には、 Prim、Kruskal、Borůvkaのアルゴリズムがあり、それぞれMSTの異なる特性を利用しています。これらはすべて同様の動作をします。つまり、有効なMSTが発見されるまで、 のサブセットを反復的に拡張していくのです。しかし、実際の問題はしばしば非常に大規模であるため（道路網には数十億もの辺が存在することもあります）、パフォーマンスが重要な要素となります。パフォーマンスを向上させる一つの方法は、既知のMSTアルゴリズムを並列化することです。^[1]${\displaystyle E}$

プリムのアルゴリズム

このアルゴリズムはMSTのカット特性を利用します。以下に、シンプルな高水準擬似コード実装を示します。

${\displaystyle T\gets\emptyset }$ 
${\displaystyle S\gets \{s\}}$ 繰り返し回数のランダム頂点はどこにあるか${\displaystyle s}$ ${\displaystyle V}$ 
 ${\displaystyle |V|-1}$ 
    最も明るいエッジstを見つけてT
を返す${\displaystyle (u,v)}$ ${\displaystyle u\in S}$ ${\displaystyle v\in (V\setminus S)}$ 
    ${\displaystyle S\gets S\cup \{v\}}$ 
    ${\displaystyle T\gets T\cup \{(u,v)\}}$ 

各辺は正確に2回、つまり各端点を調べる際に観測されます。各頂点は、ループの各反復における最軽量辺の選択を除いて、合計 回の操作で正確に1回検査されます。この選択は、多くの場合、優先キュー（PQ）を用いて行われます。各辺に対して、最大1回の decreaseKey 操作（で償却）が実行され、各ループの反復で1回の deleteMin 操作（）が実行されます。したがって、フィボナッチヒープを使用すると、Prim アルゴリズムの合計実行時間は漸近的に になります。 ${\displaystyle O(n+m)}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(m+n\log n)}$

ループは本質的に逐次的であり、適切に並列化できないことに注意することが重要です。これは、 に端点を持ち に を持つ最軽量の辺が、への辺の追加によって変化する可能性があるためです。したがって、最軽量の辺を同時に2つ選択することはできません。しかしながら、 を並列化する試みはいくつか存在します。 ${\displaystyle S}$ ${\displaystyle V\setminus S}$ ${\displaystyle T}$

1つのアイデアとしては、EREW-PRAMマシン上でPQアクセスをサポートするためにプロセッサを使用し、^[2]合計実行時間を に短縮することが挙げられます。 ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(n+m)}$

クラスカルのアルゴリズム

クラスカルのMSTアルゴリズムは、 MSTの循環性を利用します。以下に高レベルの擬似コード表現を示します。

${\displaystyle T\gets }$ 各頂点が自身のサブツリーにあるフォレスト。
重みの昇順で
    foreachを実行し 、異なるサブツリーでT
を返す。${\displaystyle (u,v)\in E}$  ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle T}$ 
        ${\displaystyle T\gets T\cup \{(u,v)\}}$ 

のサブツリーはunion-findデータ構造に格納されるため、2つの頂点が同じサブツリー内にあるかどうかの確認は、amortised で可能です。ここで、は逆アッカーマン関数です。したがって、アルゴリズムの合計実行時間は です。ここで、は単値逆アッカーマン関数を表します。この関数に対しては、任意の現実的な入力が5未満の整数を生成します。 ${\displaystyle T}$ ${\displaystyle O(\alpha (m,n))}$ ${\displaystyle \alpha (m,n)}$ ${\displaystyle O(sort(n)+\alpha (n))}$ ${\displaystyle \alpha (n)}$

アプローチ1：ソートステップの並列化

プリムのアルゴリズムと同様に、クラスカルのアプローチにも、その古典的な変種では並列化できない要素があります。例えば、2つの頂点が同じサブツリー内にあるかどうかを判定する処理は、2つの和集合演算が同時に同じサブツリーを結合しようとする可能性があるため、並列化が困難です。実際に並列化が可能なのはソート処理のみです。ソートはプロセッサ上で最適な場合、線形であるため、全体の実行時間は まで短縮できます。 ${\displaystyle O(\log n)}$ ${\displaystyle O(m\alpha (n))}$

アプローチ2：フィルター・クラスカル

もう一つのアプローチは、元のアルゴリズムをより積極的に成長させることです。このアイデアはOsipovらによって提唱されました。^{[3] [4] Filter-Kruskalの基本的な考え方は、}クイックソートと同様に辺を分割し、同じ木に属する頂点を結ぶ辺を除外することでソートコストを削減することです。以下に高レベルの擬似コード表現を示します。 ${\displaystyle T}$

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

パーティション( , ピボット):
 foreach :
     if weight( )ピボット:
         else return ( , )${\displaystyle E}$ ${\displaystyle E_{\leq }\gets \emptyset }$  
${\displaystyle E_{>}\gets \emptyset }$ 
 ${\displaystyle (u,v)\in E}$ ${\displaystyle u,v}$ ${\displaystyle \leq }$ ${\displaystyle E_{\leq }\gets E_{\leq }\cup {(u,v)}}$  
    
        ${\displaystyle E_{>}\gets E_{>}\cup {(u,v)}}$ 
${\displaystyle E_{\leq }}$ ${\displaystyle E_{>}}$ 

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

Filter-Kruskal は、ソート、パーティショニング、フィルタリングにおいて、エッジがコア間で単純に分割される直感的に簡単な並列化を備えているため、並列化に適しています。

ボルフカのアルゴリズム

Borůvka アルゴリズムの根底にある考え方は、辺の縮約です。辺は、まずグラフから を削除し、次にすべての辺を にリダイレクトすることで縮約されます。これらの新しい辺は、以前の辺の重みを保持します。MST の重みだけでなく、それがどの辺で構成されているかを決定することが目的である場合、どの頂点ペア間で辺が縮約されたかを記録する必要があります。以下に、高レベルの擬似コード表現を示します。 ${\displaystyle \{u,v\}}$ ${\displaystyle v}$ ${\displaystyle \{w,v\}\in E}$ ${\displaystyle \{w,u\}}$

${\displaystyle T\gets \emptyset }$ 
 
        契約の戻りT
の最も軽いもの${\displaystyle |V|>1}$ 
    ${\displaystyle S\gets \emptyset }$  
     ${\displaystyle v\in V}$ 
        ${\displaystyle S\gets S}$  ${\displaystyle \cup }$ ${\displaystyle \{u,v\}\in E}$ 
     ${\displaystyle \{u,v\}\in S}$ ${\displaystyle \{u,v\}}$ 
    ${\displaystyle T\gets T\cup S}$ 

縮約によって、頂点ペア間に複数の辺が生じる可能性があります。最も軽い辺を選択するという直感的な方法は、 では不可能です。しかし、頂点を共有するすべての縮約を並列に実行すれば、これは可能です。再帰は頂点が1つだけになった時点で停止します。つまり、アルゴリズムは最大で回反復する必要があり、合計実行時間は で済みます。 ${\displaystyle O(m)}$ ${\displaystyle \log n}$ ${\displaystyle O(m\log n)}$

並列化

このアルゴリズムの並列化の一つの可能​​性^{[5] [6] [7]は、}多重対数的な時間計算量、すなわち となり、定数 が存在するという結果になる。ここで は、プロセッサ数台を持つマシン上で、辺と 頂点 を持つグラフの実行時間を表す。基本的な考え方は以下の通りである。 ${\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}$

 
    最も軽い接続辺を見つける //対応
    するサブグラフを各頂点に割り当てる //
    各サブグラフを縮小する //${\displaystyle |V|>1}$ ${\displaystyle O({\frac {m}{p}}+\log n+\log p)}$ ${\displaystyle O({\frac {n}{p}}+\log n)}$ ${\displaystyle O({\frac {m}{p}}+\log n)}$ 

MST は、見つかった最も明るいエッジすべてから構成されます。

この並列化では、 の隣接配列グラフ表現を利用します。これは、頂点の長さ、各辺の端点の長さ、そして辺の重みの長さの3つの配列で構成されます。頂点 について、に接続する各辺のもう一方の端点は、との間のエントリで見つけることができます。の 番目の辺の重みは にあります。そして、の 番目の辺が頂点との間にある場合、かつ の場合に限ります。 ${\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}$

最も明るい入射エッジを見つける

まず、辺は各プロセッサに分配されます。-番目のプロセッサは、との間に格納されている辺を受け取ります。さらに、各プロセッサは、これらの辺がどの頂点に属しているかを知る必要があり（は辺の端点の1つしか格納していないため）、これを配列 に格納します。この情報は、二分探索または線形探索を用いて取得できます。実際には、後者のアプローチの方が漸近的には劣るものの、より高速な場合があります。 ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle \gamma [{\frac {im}{p}}]}$ ${\displaystyle \gamma [{\frac {(i+1)m}{p}}-1]}$ ${\displaystyle \gamma }$ ${\displaystyle pred}$ ${\displaystyle O(\log n)}$ ${\displaystyle p}$ ${\displaystyle O({\frac {n}{p}}+p)}$

ここで、各プロセッサは、それぞれの頂点に接する最も明るいエッジを決定します。

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

ここで問題となるのは、一部の頂点が複数のプロセッサで処理されることです。この問題の解決策として、各プロセッサが独自の配列を持ち、後で縮約法を用いて他のプロセッサの配列と結合するという方法があります。各プロセッサは最大2つの頂点を持ち、それらは他のプロセッサでも処理され、各縮約は 単位 です。したがって、このステップの合計実行時間は 単位 です。 ${\displaystyle prev}$ ${\displaystyle O(\log p)}$ ${\displaystyle O({\frac {m}{p}}+\log n+\log p)}$

頂点へのサブグラフの割り当て

前のステップで収集された辺のみで構成されるグラフを観察してください。これらの辺は、最も軽い入射辺である頂点から遠ざかるように向いています。結果として得られるグラフは、複数の弱連結成分に分解されます。このステップの目的は、各頂点に、それが属する成分を割り当てることです。すべての頂点にはちょうど1つの出力辺があるため、各成分は擬似木、つまり成分内の最も軽い辺と平行に、かつ反対方向に走る1つの追加辺を持つ木であることに注意してください。次のコードは、この追加辺をループに変換します。

並列forAllの 場合${\displaystyle v\in V}$  
    ${\displaystyle w\gets pred[v]}$ 
     ${\displaystyle pred[w]=v\land v<w}$  
        ${\displaystyle pred[v]\gets v}$ 

これで、すべての弱連結成分は、根にループを持つ有向木になります。この根が各成分の代表として選択されます。次のコードは、倍加法を用いて各頂点に代表を割り当てています。

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

これで、すべてのサブグラフがスターになりました。高度な技術を使うと、このステップには時間がかかります。 ${\displaystyle O({\frac {n}{p}}+\log n)}$

サブグラフの縮小

このステップでは、各サブグラフが 1 つの頂点に縮小されます。

${\displaystyle k\gets }$ 部分グラフの数、

一対一関数のスタールートを見つける${\displaystyle V'\gets \{0,\dots ,k-1\}}$ ${\displaystyle f:}$ ${\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 をin time で使用することで実行できます。 ${\displaystyle O({\frac {n}{p}}+\log p)}$ ${\displaystyle E'}$ ${\displaystyle O({\frac {m}{p}}+\log p)}$

複雑

各反復には時間がかかり、逐次的な場合と同様に反復が繰り返されるため、合計実行時間は になります。アルゴリズムの効率が の場合、相対的に効率的です。の場合、絶対的に効率的です。 ${\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)}$

さらなるアルゴリズム

MSTを求める問題を扱う並列アルゴリズムは他にも複数存在します。プロセッサ数が線形であれば、この処理は^{[8] [9]}で実現可能です。BaderとCongは、8コアで最適な逐次アルゴリズムよりも5倍高速なMSTアルゴリズムを発表しました。^[10]${\displaystyle O(\log n)}$

もう一つの課題は外部メモリモデルです。Dementievらが提案したアルゴリズムは、内部メモリのみを使用するアルゴリズムに比べて2～5倍しか遅くないと言われています^[11]

参考文献

1. サンダース;ディーツフェルビンガー。マーティン;メルホルン。カート。ピーター (2014-06-10)。アルゴリズムとデータ構造、Grundwerkzeuge。スプリンガービューeg。ISBN 978-3-642-05472-3。
2. ブローダル、ガース・ストルティング;トラフ、ジェスパー・ラーソン。 Zaroliagis、Christos D. (1998)、「A Parallel Priority Queue with Constant Time Operations」、Journal of Parallel and Distributed Computing、49 (1): 4–21、CiteSeerX 10.1.1.48.3272、doi :10.1006/jpdc.1998.1425 
3. Osipov, Vitaly; Sanders, Peter; Singler, Johannes (2009), 「フィルタ-クラスカル最小全域木アルゴリズム」,第11回アルゴリズム工学実験ワークショップ (ALENEX) の議事録. Society for Industrial and Applied Mathematics : 52– 61, CiteSeerX 10.1.1.218.2574 
4. サンダース、ピーター. 「アルゴリズムエンジニアリングスクリプト」(PDF) .アルゴリズムエンジニアリングKITホームページ. 2019年2月25日閲覧。
5. Sanders, Peter. 「並列アルゴリズムスクリプト」（PDF） .並列アルゴリズムKITホームページ. 2019年2月25日閲覧。
6. Zadeh, Reza. 「分散アルゴリズムと最適化」(PDF) .分散アルゴリズムと最適化 スタンフォード大学ホームページ. 2019年2月25日閲覧。
7. Chun, Sun; Condon, Anne (1996). 「Bouvkaの最小全域木アルゴリズムの並列実装」.国際並列処理会議論文集. pp.  302– 308. doi :10.1109/IPPS.1996.508073. ISBN 0-8186-7255-2. S2CID  12710022。
8. Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001)、「並行スレッドと最適な並列最小スパニングツリーアルゴリズム」、Journal of the Association for Computing Machinery、48 (2): 297– 323、CiteSeerX 10.1.1.32.1554、doi :10.1145/375827.375847、MR  1868718、S2CID  1778676 
9. ペティ、セス、ラマチャンドラン、ヴィジャヤ (2002)、「最小全域森林を見つけるためのランダム化時間作業最適並列アルゴリズム」(PDF)、SIAM Journal on Computing、31 (6): 1879– 1895、doi :10.1137/S0097539700371065、MR  1954882
10. Bader, David A. ; Cong, Guojing (2006)、「疎グラフの最小全域森を計算するための高速共有メモリアルゴリズム」、Journal of Parallel and Distributed Computing、66 (11): 1366– 1378、doi :10.1016/j.jpdc.2006.06.001
11. Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Engineering an external memory minimum spanning tree algorithm", Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF) , pp.  195– 208, 2011-08-09にオリジナル(PDF)からアーカイブ, 2019-05-24取得。