並列全ペア最短経路アルゴリズム

アルゴリズムグラフ理論の中心的な問題は、最短経路問題です。これにより、すべてのノードペア間の最短経路を見つける問題は、全ペア最短経路 (APSP)問題として知られています。この問題の順次アルゴリズムは実行時間が長くなることが多いため、この分野では並列化が有益であることがわかっています。この記事では、この問題を解決する 2 つの効率的なアルゴリズムを紹介します。

この問題の別のバリエーションは、単一ソース最短経路 (SSSP) 問題であり、これにも並列アプローチがあります:並列単一ソース最短経路アルゴリズム。

をノードの集合とエッジの集合を持つ有向グラフとします。各エッジには重みが割り当てられています。全ペア最短経路問題の目的は、グラフのすべてのノードのペア間の最短経路を見つけることです。この経路が一意であるためには、グラフに負の重みを持つサイクルが含まれていないことが必要です。 ${\displaystyle G=(V,E,w)}$${\displaystyle V}$${\displaystyle E\subseteq V\times V}$${\displaystyle e\in E}$${\displaystyle w(e)}$

この記事の残りの部分では、グラフが隣接行列を使用して表現されているものと仮定します。アルゴリズムの出力は距離行列になると予想されます。 では、各エントリはノードからノードへの最短経路の重みです。 ${\displaystyle D}$${\displaystyle D}$${\displaystyle d_{i,j}}$${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$

後ほど説明するFloyd アルゴリズムは負のエッジ重みを処理できますが、Dijkstra アルゴリズムではすべてのエッジに正の重みが必要です。

ダイクストラ アルゴリズムは、もともと単一ソース最短経路問題の解決法として提案されました。ただし、各ノードをルート ノードの役割を果たす単一ソース バリアントを実行することで、このアルゴリズムを使用して全ペア最短経路問題を簡単に解決できます。

疑似コードでは、このような実装は次のようになります。

1     func DijkstraSSSP( G , v ) {
 2 ... //ここで標準SSSP実装
 3 return d v ;
 4 }
 5    
 6    関数DijkstraAPSP( G ) {
 7         D  := | V |x| V |-行列
 8         1から| V | {までのiについて  
 9 // D[v]はDのv行目を表す
 10           D [ v ] := DijkstraSSP( G , i )
 11 }
 12 }

この例では、 がDijkstraSSSPグラフとルート ノードを入力として受け取ると仮定します。 実行の結果は、距離リスト になります。 では、- 番目の要素にルート ノードからノードまでの距離が格納されます。したがって、リストはAPSP 距離マトリックス の - 番目の行に正確に対応します。このため、はグラフのすべてのノードを反復処理し、各ノードをルート ノードとして を実行し、結果を に格納します。 ${\displaystyle G}$${\displaystyle v}$${\displaystyle d_{v}}$${\displaystyle d_{v}}$${\displaystyle i}$${\displaystyle v}$${\displaystyle i}$${\displaystyle d_{v}}$${\displaystyle v}$${\displaystyle D}$DijkstraAPSP${\displaystyle G}$DijkstraSSSP${\displaystyle D}$

の実行時間は、グラフが隣接行列をDijkstraSSSP使用して表現されると予想されるとおりです。したがって、の合計順次実行時間は です。 ${\displaystyle O(|V|^{2})}$DijkstraAPSP${\displaystyle O(|V|^{3})}$

8DijkstraAPSP行目のループを並列化することで、簡単な並列化を実現できます。ただし、シーケンシャルを使用すると、ループ内で実行される反復回数によって、使用するプロセッサの数が制限されます。したがって、この簡単な並列化では、プロセッサの数に上限があります。 DijkstraSSSP${\displaystyle |V|}$

たとえば、プロセッサの数をノードの数と等しくします。これにより、各プロセッサは並列で正確に 1 回実行されます。ただし、使用可能なプロセッサがたとえば 個しかない場合は、各プロセッサは 2 回実行する必要があります。 ${\displaystyle p}$${\displaystyle |V|}$DijkstraSSSP${\displaystyle p={\frac {|V|}{2}}}$DijkstraSSSP

合計すると、 がの倍数のとき、実行時間は になります。したがって、この並列化の効率は完璧です。プロセッサを使用すると、実行時間が 倍短縮されます。 ${\displaystyle O(|V|^{2}\cdot {\frac {|V|}{p}})}$${\displaystyle |V|}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

この並列化のもう 1 つの利点は、プロセッサ間の通信が不要になることです。ただし、各プロセッサにはグラフの隣接行列全体を保存できる十分なローカル メモリが必要です。

並列化に100 台以上のプロセッサを使用する場合は、複数のプロセッサが計算に参加する必要があります。このため、並列化は 2 つのレベルに分割されます。 ${\displaystyle |V|}$DijkstraSSSP

最初のレベルでは、プロセッサはパーティションに分割されます。各パーティションは、距離行列の 1 行の計算を担当します。つまり、各パーティションは、固定ルート ノードを使用して 1 回の実行を評価する必要があります。この定義では、各パーティションのサイズは プロセッサになります。各パーティションの結果は互いに独立しているため、パーティションは計算を並列に実行できます。したがって、前のセクションで示した並列化は、プロセッサを使用したパーティション サイズ 1 に相当します。 ${\displaystyle |V|}$${\displaystyle D}$DijkstraSSSP${\displaystyle k={\frac {p}{|V|}}}$${\displaystyle p=|V|}$

主な難しさは、DijkstraSSSP単一のルート ノードに対して複数のプロセッサを実行する並列化です。この並列化の考え方は、パーティション内の DijkstraSSSP の距離リストの管理を分散することです。したがって、パーティション内の各プロセッサは、の要素に対して排他的に責任を負います。たとえば、と を考えます。これにより、パーティション サイズは になります。この場合、各パーティションの最初のプロセッサは を担当し、 2 番目のプロセッサはとを担当します。これにより、合計距離リストは になります。 ${\displaystyle d_{v}}$${\displaystyle {\frac {|V|}{k}}}$${\displaystyle d_{v}}$${\displaystyle |V|=4}$${\displaystyle p=8}$${\displaystyle k=2}$${\displaystyle d_{v,1}}$${\displaystyle d_{v,2}}$${\displaystyle d_{v,3}}$${\displaystyle d_{v,4}}$${\displaystyle d_{v}=[d_{v,1},d_{v,2},d_{v,3},d_{v,4}]}$

アルゴリズムDijkstraSSSPは主に 2 つのステップの繰り返しから構成されます。まず、距離リスト内の最も近いノードを見つける必要があります。このノードの最短経路はすでに見つかります。その後、 のすべての隣接ノードの距離を で調整する必要があります。 ${\displaystyle x}$${\displaystyle d_{v}}$${\displaystyle x}$${\displaystyle d_{v}}$

並列化がパーティション全体に分散されている ため、これらの手順は次のように変更する必要があります。${\displaystyle d_{v}}$

1. 最短距離のノードを見つけます。 ${\displaystyle x}$${\displaystyle d_{v}}$
   • 各プロセッサは の一部を所有します。各プロセッサは、たとえば線形検索を使用して、自分の部分で局所最小値をスキャンします。${\displaystyle d_{v}}$${\displaystyle {\tilde {x}}}$
   • すべての に対して削減操作を実行して、における大域的最小値を計算します。${\displaystyle x}$${\displaystyle d_{v}}$${\displaystyle {\tilde {x}}}$
   • グローバル最小値をパーティション内のすべてのノードにブロードキャストします。${\displaystyle x}$
2. 内のすべての隣接要素の距離を調整する${\displaystyle x}$${\displaystyle d_{v}}$
   • すべてのプロセッサは、グローバルに最も近いノードとその距離を認識しています。この情報に基づいて、対応するプロセッサによって管理されるの隣接ノードを調整します。${\displaystyle x}$${\displaystyle x}$${\displaystyle d_{v}}$

DijkstraSSSPサイズのパーティションによって実行されるこのような反復の合計実行時間は、実行されたサブタスクに基づいて導出できます。 ${\displaystyle k}$

• の線形探索:${\displaystyle {\tilde {x}}}$${\displaystyle O({\frac {|V|}{k}})}$
• ブロードキャスト操作とリデュース操作: これらは、たとえば二項ツリーを使用して効率的に実装できます。これにより、通信オーバーヘッドが発生します。${\displaystyle O(\log k)}$

反復回数の場合、合計実行時間は になります。 の定義を代入すると、の 合計実行時間は次のようになります。${\displaystyle |V|}$${\displaystyle O(|V|({\frac {|V|}{k}}+\log k))}$${\displaystyle k}$DijkstraAPSP${\displaystyle O({\frac {|V|^{3}}{p}}+\log p)}$

この並列化の主な利点は、すべてのプロセッサが隣接行列全体を保存する必要がなくなったことです。代わりに、パーティション内の各プロセッサが、担当するノードの隣接行列の列のみを保存すれば十分です。パーティション サイズが の場合、各プロセッサは隣接行列の列のみを保存する必要があります。ただし、この並列化の欠点は、削減操作とブロードキャスト操作による通信オーバーヘッドが伴うことです。 ${\displaystyle k}$${\displaystyle {\frac {|V|}{k}}}$

この例で使用されるグラフは、画像に示されている 4 つのノードを持つグラフです。

目標は、プロセッサを使用して距離行列を計算することです。このため、プロセッサはそれぞれ 2 つのプロセッサを持つ 4 つのパーティションに分割されます。図では、ノードAから他のすべてのノードへの最短パスの計算を担当するパーティションに焦点を当てます。このパーティションのプロセッサをp1とp2と名付けます。 ${\displaystyle p=8}$

異なる反復にわたる距離リストの計算は、2 番目の画像に視覚化されています。

画像の上段は初期化後、下段はアルゴリズムの終了後に対応しています。ノードは、p1がノードAとBを担当し、p2 がノード CとDを担当するように分散されています。距離リストはこれに従って分散されます。2 回目の反復では、実行されるサブタスクが画像に明示的に表示されます。 ${\displaystyle d_{A}}$${\displaystyle d_{A}}$${\displaystyle d_{A}}$

1. 局所最小値ノードの計算${\displaystyle d_{A}}$
2. 縮小操作によるグローバル最小値ノードの計算${\displaystyle d_{A}}$
3. グローバル最小ノードのブロードキャスト${\displaystyle d_{A}}$
4. グローバル最も近いノードを「完了」としてマークし、その隣接ノードとの距離を調整する

フロイド・ワーシャル アルゴリズムは、有向グラフの全ペア最短経路問題を解決します。グラフの隣接行列を入力として、より短い経路を反復的に計算します。| V | 回の反復後、距離行列にはすべての最短経路が含まれます。次に、疑似コードでアルゴリズムの順次バージョンを示します。

1    関数Floyd_All_Pairs_SP( A ) {
 2         = ;​${\displaystyle D^{(0)}}$
 3         k  := 1 to nの場合 4 
 i             :  = 1 to nの場合
 5                 j  := 1 to nの場合
 6                            ${\displaystyle d_{i,j}^{(k)}:=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})}$
 7 }

ここで、Aは隣接行列、n = | V | はノード数、D は距離行列 です。

アルゴリズムを並列化する基本的な考え方は、行列を分割し、計算をプロセス間で分割することです。各プロセスは、行列の特定の部分に割り当てられます。これを実現する一般的な方法は、2-D ブロック マッピングです。ここでは、行列は同じサイズの正方形に分割され、各正方形がプロセスに割り当てられます。行列が p 個でプロセスがp個の場合、各プロセスは 距離行列の指定されたサイズの部分を計算します。プロセスの場合、各プロセスは行列の 1 つの要素に割り当てられます。そのため、並列化は最大プロセスまでしか拡張できません。以下では、i 行目の j 列目の正方形に割り当てられたプロセスを と呼んでいます。 ${\displaystyle n\times n}$${\displaystyle n/{\sqrt {p}}\times n/{\sqrt {p}}}$${\displaystyle p=n^{2}}$${\displaystyle n^{2}}$${\displaystyle p_{i,j}}$

距離行列の各部分の計算は他の部分の結果に依存するため、プロセスは相互に通信し、データを交換する必要があります。以下では、k 回目の反復後の距離行列の i 行目および j 列目の要素を と称します。計算するには、アルゴリズムの 6 行目に指定されている要素、およびが必要です。は、前回の反復で独自に計算されているため、各プロセスで使用できます。 ${\displaystyle d_{i,j}^{(k)}}$${\displaystyle d_{i,j}^{(k)}}$${\displaystyle d_{i,j}^{(k-1)}}$${\displaystyle d_{i,k}^{(k-1)}}$${\displaystyle d_{k,j}^{(k-1)}}$${\displaystyle d_{i,j}^{(k-1)}}$

さらに、各プロセスには、行列の k 行目と k 列目の一部が必要です。要素は、計算するプロセスと同じ行のプロセスを保持し、要素は、計算するプロセスと同じ列のプロセスを保持します。行列の k 行目の一部を計算した各プロセスは、この部分をその列のすべてのプロセスに送信する必要があります。行列の k 列目の一部を計算した各プロセスは、この部分をその行のすべてのプロセスに送信する必要があります。これらのプロセスはすべて、行または列に沿って 1 対全ブロードキャスト操作を実行する必要があります。データの依存関係は、下の図に示されています。 ${\displaystyle D^{k-1}}$${\displaystyle d_{i,k}^{(k-1)}}$${\displaystyle d_{k,j}^{(k-1)}}$${\displaystyle d_{i,j}^{(k)}}$${\displaystyle D^{k-1}}$${\displaystyle D^{k-1}}$

2D ブロック マッピングの場合、アルゴリズムを次のように変更する必要があります。

1    関数Floyd_All_Pairs_Parallel( ) {${\displaystyle D^{(0)}}$
 2         k :  =  1から n まで{3 のk行目のセグメントを持つ
 各プロセスは、${\displaystyle p_{i,j}}$${\displaystyle D^{(k-1)}}$
              それをプロセスにブロードキャストします。${\displaystyle p_{*,j}}$4 のk列目のセグメントを持つ
 各プロセスは、${\displaystyle p_{i,j}}$${\displaystyle D^{(k-1)}}$
              それをプロセスにブロードキャストします。${\displaystyle p_{i,*}}$
 5 各プロセスは必要なセグメントを受信するまで待機します。
 6 各プロセスは行列のそれぞれの部分を計算します。${\displaystyle D^{(k)}}$
 7 }
 8 }

アルゴリズムの 5 行目には、すべてのプロセスが次の反復を計算するために必要なデータを持っていることを確認するための同期ステップがあります。アルゴリズムの実行時間を改善するために、アルゴリズムの正確さに影響を与えずに同期ステップを削除できます。これを実現するには、各プロセスがマトリックスのその部分の計算に必要なデータを取得するとすぐに計算を開始します。このバージョンのアルゴリズムは、パイプライン化された 2-D ブロック マッピングと呼ばれます。

シーケンシャルアルゴリズムの実行時間は、3 重にネストされた for ループによって決まります。6 行目の計算は定数時間 ( ) で実行できます。したがって、シーケンシャルアルゴリズムの実行時間は です。 ${\displaystyle O(1)}$${\displaystyle O(n^{3})}$

並列化アルゴリズムの実行時間は、計算時間とプロセス間の通信およびデータ転送の 2 つの部分で構成されます。

アルゴリズムには追加の計算はなく、計算はp 個のプロセス間で均等に分割されるため、計算部分の 実行時間は になります。${\displaystyle O(n^{3}/p)}$

アルゴリズムの各反復では、プロセスの行と列に沿って 1 対すべてのブロードキャスト操作が実行されます。要素がブロードキャストされます。その後、同期ステップが実行されます。これらの操作にかかる時間は、使用する並列システムのアーキテクチャに大きく依存します。したがって、アルゴリズムでの通信とデータ転送に必要な時間は です。 ${\displaystyle n/{\sqrt {p}}}$${\displaystyle T_{\text{comm}}=n(T_{\text{synch}}+T_{\text{broadcast}})}$

アルゴリズム全体の実行時間は次のようになります。

${\displaystyle T=O\left({\frac {n^{3}}{p}}\right)+n(T_{\text{synch}}+T_{\text{broadcast}})}$

アルゴリズムのパイプライン バージョンにおけるプロセス間のデータ転送の実行時間については、プロセスが時間内にk 個の要素を隣接プロセスに転送できるものと想定します。各ステップで、行または列の要素が隣接プロセスに送信されます。このようなステップには時間がかかります。ステップの後、最初の行と列の関連データが(時間内に) プロセスに到着します。 ${\displaystyle O(k)}$${\displaystyle n/{\sqrt {p}}}$${\displaystyle O(n/{\sqrt {p}})}$${\displaystyle {\sqrt {p}}}$${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$${\displaystyle O(n)}$

パイプラインモードでは、後続の行と列の値は時間後に続きます。プロセスは O( ) + O( ) 時間後に最後の計算を終了します。したがって、パイプラインバージョンで通信に必要な追加時間は です。 ${\displaystyle O(n^{2}/p)}$${\displaystyle p_{{\sqrt {p}},{\sqrt {p}}}}$${\displaystyle n^{3}/p}$${\displaystyle n}$${\displaystyle O(n)}$

アルゴリズムのパイプライン バージョンの全体的な実行時間は次のとおりです。

${\displaystyle T=O\left({\frac {n^{3}}{p}}\right)+O(n)}$

• Grama, A.:並列コンピューティング入門。Pearson Education、2003 年。
• Kumar, V.:全ペア最短経路問題に対する並列アルゴリズムのスケーラビリティ^{[リンク切れ‍ ]}。Journal of Parallel and Distributed Programming 13、1991 年。
• Foster, I.:並列プログラムの設計と構築(オンライン)。
• Bindell、Fall:並列コンピュータの並列全ペア最短経路アプリケーション、2011 年。