並列幅優先探索

幅優先探索アルゴリズムは、グラフの頂点を層ごとに探索する方法です。これはグラフ理論の基本的なアルゴリズムであり、他のグラフアルゴリズムの一部として使用できます。たとえば、BFS はDinic のアルゴリズムによってグラフの最大フローを見つけるために使用されます。さらに、BFS は、データ集約型スーパーコンピューティング問題のベンチマークであるGraph500ベンチマークのカーネルアルゴリズムの 1 つでもあります。 ^{[1]この記事では、}並列コンピューティングの使用による BFS の高速化の可能性について説明します。

従来のシーケンシャル BFS アルゴリズムでは、フロンティアと次のフロンティアを格納するための 2 つのデータ構造が作成されます。フロンティアには、ソース頂点から同じ距離 (「レベル」とも呼ばれる) にあるすべての頂点が含まれます。これらの頂点は BFS で探索する必要があります。これらの頂点のすべての隣接頂点がチェックされ、まだ探索されていない隣接頂点のいくつかが発見され、次のフロンティアに配置されます。BFS アルゴリズムの開始時には、特定のソース頂点sがフロンティア内の唯一の頂点です。sのすべての直接隣接頂点は最初のステップで訪問され、次のフロンティアを形成します。各レイヤー トラバーサルの後、「次のフロンティア」はフロンティアに切り替えられ、新しい頂点は新しい次のフロンティアに格納されます。次の疑似コードは、フロンティアと次のフロンティアのデータ構造がそれぞれ FS と NS と呼ばれるという概念を概説しています。

1     bfs_sequential(graph(V,E), source s)を定義します。
2         V内のすべてのvに対して
3 d[v] = -1;
4 d[s] = 0; レベル = 1; FS = {}; NS = {};
5プッシュ(FS)
6         FSが空の場合
、7             FS内のuに対して、  
8                 uの各近傍vに対して、  
9                     d [v] = -1の場合、
10 プッシュ(v, NS);
11 d[v] = レベル;
12 FS = NS、NS = {}、レベル = レベル + 1;

シンプルで直感的なソリューションとして、古典的な並列ランダム アクセス マシン(PRAM) アプローチは、上記のシーケンシャル アルゴリズムの単なる拡張です。2 つのforループ (行 7 と行 8) は並列で実行できます。次のフロンティアの更新 (行 10) と距離の増加 (行 11) はアトミックである必要があります。アトミック操作は、中断や一時停止なしで完全に実行できるプログラム操作です。

しかし、この単純な並列化には 2 つの問題があります。まず、距離チェック (9 行目) と距離更新操作 (11 行目) によって、2 つの良性の競合が発生します。競合が発生する理由は、1 つの頂点の隣接頂点が、フロンティア内の別の頂点の隣接頂点でもある場合があるためです。その結果、この隣接頂点の距離が複数回検査され、更新される可能性があります。これらの競合はリソースを浪費し、不要なオーバーヘッドにつながりますが、同期を利用すれば、BFS の正確性には影響しないため、良性の競合です。次に、並列処理によって各レイヤーのトラバーサルが高速化されるにもかかわらず、フロンティア内のすべての隣接頂点を完全に検出するには、レイヤーごとにバリア同期が必要です。このレイヤーごとの同期は、必要な通信のステップが2 つの頂点間の最長距離O (d)に等しいことを示しています。ここで、Oは大きな O 表記法、d はグラフの直径です。

この単純な並列化の漸近的複雑さは最悪の場合、順次アルゴリズムと同じですが、より良い BFS 並列化を実現するためにいくつかの最適化を行うことができます。次に例を示します。

1. バリア同期の緩和。並列 BFS の正確性を保証するために、各レイヤー トラバーサルの後にバリア同期が必要です。結果として、バリア同期のコストを削減することは、並列 BFS を高速化する効果的な方法です。
2. 近隣探索の負荷分散。各レイヤーのトラバーサルの後にバリア同期が行われるため、すべての処理エンティティは最後のエンティティが作業を完了するまで待機する必要があります。したがって、最も多くの近隣を持つ並列エンティティがこのレイヤーの時間消費を決定します。負荷分散の最適化により、レイヤーのトラバーサルの時間を短縮できます。
3. メモリ参照の局所性の向上。分散メモリを備えた並列システムでは、リモート メモリ参照は他の処理エンティティからデータを取得するため、通常、ローカル メモリ参照に比べて余分な通信コストがかかります。したがって、ローカル メモリ参照はリモート メモリ参照よりも高速です。より優れたデータ構造を設計するか、データの構成を改善することで、ローカル メモリ参照を増やし、リモート メモリ参照に必要な通信を削減できます。

分散メモリを使用した並列 BFS と比較すると、共有メモリはより高いメモリ帯域幅とより低いレイテンシを提供します。すべてのプロセッサがメモリを共有するため、すべてのプロセッサがメモリに直接アクセスできます。したがって、開発者は、分散メモリがリモートのローカル メモリからデータを取得するために必要なメッセージ パッシング プロセスをプログラムする必要がありません。したがって、メッセージのオーバーヘッドが回避されます。^[2]

しかし、各層の頂点の数と各頂点の隣接数は非常に不規則であることが示されており、これは BFS のメモリ アクセスと作業分散を非常に不規則にします。並列 BFS では、この機能により負荷の不均衡により並列化の利点が減少します。結果として、共有メモリ上の並列 BFS を負荷分散することが非常に重要です。さらに、データ局所性を調査することで並列処理を高速化することもできます。

共有メモリ上の多くの並列 BFS アルゴリズムは、コンテナ中心のアプローチと頂点中心のアプローチの 2 つのタイプに分けられます。^[3]コンテナ中心のアプローチでは、現在のフロンティアと次の頂点フロンティアを格納するための 2 つのデータ構造が作成されます。次の頂点フロンティアは、各ステップの最後に現在のフロンティアに切り替えられます。データが格納される場所に応じて、同期のコストとデータ局所性の間にはトレードオフがあります。これらの 2 つのデータ構造は、データ局所性をサポートするが追加の負荷分散メカニズムを必要とするすべての処理エンティティ (スレッドなど) で保持できます。または、暗黙的な負荷分散を提供するためにグローバルにすることもできます。その場合、処理エンティティからの同時アクセスには特別なデータ構造が使用されます。ただし、その場合、それらの処理エンティティは同時に動作し、同期にさらに多くの労力が必要になります。

さらに、コンテナのデータ構成も最適化できます。シリアル BFS および一部のパラレル BFS の一般的なデータ構造はFIFO キューです。これは、挿入と削除の操作に一定の時間がかかるシンプルで高速なためです。

もう一つの選択肢はバッグ構造です。^[4]バッグへの挿入操作は最悪の場合O(logn)時間がかかりますが、 FIFO と同じくらい高速な一定の償却時間しかかかりません。さらに、2 つのバッグの結合にはΘ(lgn)時間がかかります (n は小さい方のバッグの要素数)。バッグ分割操作にもΘ(lgn)時間がかかります。バッグ構造の助けを借りて、一定数の頂点 (粒度パラメータによる) が 1 つのバッグに格納され、バッグ構造が基本的な並列エンティティになります。さらに、リデューサーをバッグ構造と組み合わせて、頂点を並列に書き込み、効率的にトラバースすることができます。

頂点中心アプローチは、頂点を並列エンティティとして扱い、並列反復を可能にします。各頂点は並列エンティティに割り当てられます。この頂点中心アプローチは、グラフの深さが非常に低い場合にのみうまく機能する可能性があります。BFSのグラフの深さは、グラフ内の任意の頂点からソース頂点までの最大距離として定義されます。したがって、すべてのスレッドが正確に1つの頂点にマップされている場合、頂点中心アプローチはGPUに適しています。^[3]

分散メモリ モデルでは、各処理エンティティが独自のメモリを持ちます。このため、処理エンティティは、ローカル データを共有したり、リモート データにアクセスしたりするために、互いにメッセージを送受信する必要があります。

1D パーティショニングは、並列 BFS と分散メモリを組み合わせる最も簡単な方法です。これは頂点パーティションに基づいています。負荷分散は、データ パーティションにとって依然として重要な問題であり、並列化からどのようなメリットが得られるかを決定します。言い換えると、分散メモリを持つ各プロセッサ (例: プロセッサ) は、ほぼ同じ数の頂点とその出力エッジを担当する必要があります。データ ストレージの実装では、各プロセッサはローカル頂点の隣接行列を格納できます。この行列では、各頂点の各行は、宛先頂点インデックスによって表される出力エッジの行です。

共有メモリ BFS とは異なり、あるプロセッサの隣接頂点は別のプロセッサに格納される場合があります。その結果、各プロセッサは、メッセージを送信してそれらのプロセッサにトラバーサル ステータスを伝える責任があります。さらに、各プロセッサは、ローカルの次の頂点フロンティアを構築するために、他のすべてのプロセッサからのメッセージも処理する必要があります。明らかに、現在のフロンティアと次の頂点フロンティアを交換する各ステップで、1 つの全対全通信(つまり、各エンティティは他のすべてのエンティティに対して異なるメッセージを持つ) が必要です。

1次元分散メモリBFSの次の疑似コード^[5]は、もともと3次元ト​​ーラスネットワークアーキテクチャを持つIBM BlueGene/Lシステム用に設計されたものです。同期は並列化BFSの主な追加コストであるため、本論文の著者らはポイントツーポイント通信に基づくスケーラブルな全対全通信も開発しました。その後、高帯域幅トーラスネットワークを利用してポイントツーポイント通信の数も削減しました。

次のアルゴリズムにおける BFS トラバーサルの主な手順は次のとおりです。

1. プロセッサビュー（8行目）：ローカルストレージの頂点を使用してフロンティアFSを構築する
2. グローバルビュー（10～11行目）：すべてのプロセッサのFSが空の場合、トラバーサルを終了する
3. プロセッサビュー（13行目）：FSの隣接頂点に基づいて次のフロンティアを構築します。ただし、隣接頂点の一部は他のプロセッサに格納されている可能性があります。
4. グローバルビュー（15～18行目）：全対全通信を実行して、各プロセッサに、どのローカル頂点をローカルの次のフロンティアNSに配置するかを知らせます。
5. プロセッサビュー（20～22行目）：他のすべてのプロセッサからメッセージを受信し、現在のフロンティア内のローカル頂点の距離値を更新し、NSをFSに変更する

1     1_D_distributed_memory_BFS(グラフ(V,E),ソースs)を定義します。
2         //通常の初期化
3         V内のすべてのvに対して実行
4 d[v] = -1;
5 d[s] = 0; レベル = 0; FS = {}; NS = {};
6         //BFSトラバーサルを開始
7         Trueの間、以下を実行します。
8 FS = {レベルを持つローカル頂点の集合}
9             //すべての頂点を走査10
すべて           のプロセッサで FS = {} の場合:
11 whileループを終了する
12            //現在のフロンティアのローカル頂点に基づいてNSを構築する
13 NS = {FS 内の頂点の隣接点、ローカル頂点と非ローカル頂点の両方}
14            //同期: 全員対全員通信
15            0 <= j < pの場合、次のようにします:
16 N_j = {プロセッサjが所有するNS内の頂点}
17                N_jをプロセッサjに送信する
18               プロセッサjからN_j_rcvを受信する
19            //受信したメッセージを組み合わせてローカルの次の頂点境界を形成し、それらのレベルを更新します
20 NS_rcv = ユニオン(N_j_rcv)
21            NS_rcvのvとd[v] == -1の場合
22 d[v] = レベル + 1

マルチスレッドと組み合わせた1D分散メモリBFSの次の疑似コードでは、論文^{[6]から引用したスレッドスタックとスレッドバリアも指定されています。}

マルチスレッドでは、フロンティア FS のローカル頂点を分割して 1 つのプロセッサ内の異なるスレッドに割り当てることができるため、BFS トラバーサルがさらに並列化されます。ただし、上記の方法とは異なり、個々のスレッドごとにさらにデータ構造が必要になります。たとえば、このスレッドの頂点から隣接頂点を保存するために用意されるスレッド スタックです。各スレッドには p-1 個のローカル ストレージがあり、p はプロセッサの数です。これは、各スレッドが他のすべてのプロセッサのメッセージを分離する必要があるためです。たとえば、j 番目のプロセッサがそれらの頂点の所有者である場合、j 番目のスタックに隣接頂点を配置して、j 番目のプロセッサに送信するメッセージを形成します。さらに、スレッド バリアも同期に必要です。結果として、マルチスレッドによる分散メモリは並列化の改善から恩恵を受ける可能性がありますが、スレッドに追加の同期コストも生じます。

次のアルゴリズムにおける BFS トラバーサルの主な手順は次のとおりです。

1. スレッド ビュー (行 19 ～ 22): 自身に割り当てられた頂点に基づいて、隣接頂点の所有者プロセッサを見つけ、所有者に基づいてそれらをスレッド スタックに配置します。
2. プロセッサ ビュー (行 23): スレッド バリアを実行し、すべてのスレッド (同じプロセッサの) がジョブを完了するまで待機します。
3. プロセッサ ビュー (25 行目～ 26 行目): 同じ所有者を持つすべてのスレッドのすべてのスレッド スタックをマージします (次のステップの宛先を持つスレッド スタック)。
4. グローバル ビュー (行 28 ～ 30): マスター スレッドとの全対全通信を実行して、どのローカル頂点を次のフロンティアに配置するかを各プロセッサに通知します。
5. プロセッサ ビュー (行 31): スレッド バリアを実行し、通信が完了するまで待機します (マスター スレッドの)。
6. プロセッサ ビュー (行 33): 次のフロンティアからの頂点を各スレッドに割り当てます。
7. スレッド ビュー (行 34 ～ 36): 頂点が訪問されていない場合は、その頂点の距離値を更新し、次のフロンティア NS のスレッド スタックに配置します。
8. プロセッサ ビュー (行 37): スレッド バリアを実行し、すべてのスレッド (同じプロセッサの) がジョブを完了するまで待機します。
9. プロセッサビュー（39行目）：各スレッドから次のフロンティアのスレッドスタックを集約する
10. プロセッサ ビュー (行 40): スレッド バリアを実行し、すべてのスレッドがスタック内のすべての頂点を送信するまで待機します。

1     1_D_distributed_memory_BFS_with_threads(graph(V,E), source s)を定義します。
2         // 通常の初期化
3         for all v in V do
4 d[v] = -1;
5 レベル = 1; FS = {}; NS = {};
6         // ソース頂点sの所有者プロセッサのインデックスを見つける
7 pu_s = find_owner(s);
8         pu_s = index_puの場合
9 プッシュ(s,FS);
10 d[s] = 0;
11        // メッセージの初期化
12        0 <= j < pの場合
13 sendBuffer_j = {} // p 共有メッセージバッファ
14 recvBuffer_j = {} // MPI通信用
15 thrdBuffer_i_j = {} //スレッドiのスレッドローカルスタック
16        // BFS の走査を開始
17        while FS != {}実行
18            // 頂点を走査し、隣接頂点の所有者を検索
19            FS 内の各 uに対して並列に実行
20                u の各隣接 vに対して実行
21 pu_v = find_owner(v)
22 プッシュ(v, thrdBuffer_i_(pu_v))
23           スレッドバリア
24            // スレッドスタックを結合してsendBufferを形成する
25            for 0 <= j < p do
26 thrdBuffer_i_jを並列にマージする
27            // 全員へのコミュニケーション 
28 マスタースレッドを使用した全員集合ステップ:
29 1. sendBufferでデータを送信する
30 2. 新しく訪問した頂点を受信して​​recvBufferに集約する
31           スレッドバリア
32            // 新しく訪れた頂点のレベルを更新 
33            recvBuffer 内の各 u を並列に実行34 
d                [u] == -1の場合
35 d[u] = レベル
36 プッシュ(u, NS_i)
37           スレッドバリア
38            // NSを集約して新しいFSを形成する 
39 FS = ユニオン(NS_i)
40           スレッドバリア
41 レベル = レベル + 1f

BFS アルゴリズムは、グラフの表現として常に隣接行列を使用するため、行列の自然な 2D 分解も検討すべきオプションです。2D パーティショニングでは、各プロセッサに 2D インデックス (i,j) があります。エッジと頂点は、サブ隣接行列が格納されている 2D ブロック分解を使用してすべてのプロセッサに割り当てられます。

合計で P=R·C 個のプロセッサがある場合、隣接行列は以下のように分割されます。

この分割後、C列とR·Cブロック行が存在する。各プロセッサはCブロックを担当し、つまりプロセッサ(i,j)はA _i,j ⁽¹⁾からA _i,j ^(C)ブロックを格納する。従来の1D分割は、R=1またはC=1の2D分割と同等である。

一般的に、2Dパーティショニングに基づく並列エッジ処理は、「拡張」フェーズと「折りたたみ」フェーズの2つの通信フェーズで構成できます。^[6]

「拡張」フェーズでは、与えられた頂点のエッジ リストが隣接行列の列である場合、フロンティア内の各頂点 v について、v の所有者は、そのプロセッサ列内の他のプロセッサに v が訪問されたことを伝える責任があります。これは、各プロセッサが頂点の部分的なエッジ リストのみを格納するためです。この通信の後、各プロセッサは頂点に従って列をトラバースし、次のフロンティアを形成するために隣接する頂点を見つけることができます。^[5]

「フォールド」フェーズでは、結果として得られる次のフロンティアの頂点が、その所有者のプロセッサに送信され、ローカルで新しいフロンティアを形成します。2Dパーティショニングでは、これらのプロセッサは同じプロセッサ行にあります。^[5]

この 2D パーティショニング アルゴリズムにおける BFS トラバーサルの主な手順は次のとおりです (プロセッサごとに):

1. 拡張フェーズ (行 13 ～ 15): ローカル頂点に基づいて、プロセッサ列のプロセッサにのみメッセージを送信し、これらの頂点がフロンティア内にあることを通知し、これらのプロセッサからメッセージを受信します。
2. (行 17 ～ 18): すべての受信メッセージをマージし、ネット フロンティア N を形成します。受信メッセージの頂点すべてを次のフロンティアに配置する必要はなく、すでにいくつかは訪問済みである可能性があることに注意してください。次のフロンティアには、距離値が -1 である頂点のみが含まれます。
3. フォールドフェーズ（20～23行目）：次のフロンティアのローカル頂点に基づいて、プロセッサ行内のこれらの頂点の所有者プロセッサにメッセージを送信します。
4. (行 25 ～ 28): すべての受信メッセージをマージし、次のフロンティアの頂点の距離値を更新します。

以下の疑似コードは、論文^{[5]から引用した2D BFSアルゴリズムの詳細を説明しています。}

1     2_D_distributed_memory_BFS(グラフ(V,E),ソースs)を定義します。
2         // 通常の初期化
3         for all v in V do
4 d[v] = -1;
5 d[s] = 0;
6         // BFSトラバーサルを開始
7         l = 0から無限大まで実行:
8 F = {レベル l のローカル頂点の集合}
9             // すべての頂点を走査
10           すべてのプロセッサに対して F = {}の場合、次のようになります。
11 whileループを終了する
12            // 選択したプロセッサにメッセージを送信して頂点をトラバースします
13           このプロセッサ列のすべてのプロセッサ qに対して、次の操作を実行します。
14                Fをプロセッサqに送信する
15                qからF q rを受け取る
16            // フロンティア通過後の受信情報の処理
17 F r = Union{F q r } for all q18 N = {このプロセッサ上のエッジリストを使用したF r
内の頂点の隣接}
19            // メッセージをその所有者プロセッサに送信して隣接頂点をブロードキャストします
20           このプロセッサ行のすべてのプロセッサ qに対して以下を実行します。
21 N q = {プロセッサqが所有するN内の頂点}
22                N qをプロセッサqに送信する
23                qからN q rを受け取る
24            // 次の層のトラバーサルに使用する次のフロンティアを形成する
25 N r = Union{N q r } for all q
26            // レイヤー距離更新
27            v in N rかつ d(v) = -1の場合、以下を実行します。
28 レベル = l + 1

2Dパーティショニングでは、プロセッサの列または行のみがそれぞれ「拡張」フェーズまたは「フォールド」フェーズで通信に参加します。^[5]これは、1Dパーティショニングよりも2Dパーティショニングが優れている点です。1Dパーティショニングではすべてのプロセッサが全対全の通信操作に関与するためです。さらに、2Dパーティショニングはより柔軟で負荷分散も優れているため、よりスケーラブルでストレージ効率の高いアプローチがはるかに簡単になります。

並列 BFS の基本的な考え方とは別に、いくつかの最適化戦略を使用して並列 BFS アルゴリズムを高速化し、効率を向上させることができます。並列 BFS には、方向の最適化、負荷分散メカニズム、データ構造の改善など、すでにいくつかの最適化が存在します。

オリジナルのトップダウン BFS では、各頂点はフロンティアにあるすべての隣接頂点を調べる必要があります。グラフの直径が小さい場合、これは効果的でない場合があります。 [ ^{7]しかし、}スモールワールド グラフなど、内部の一部の頂点の次数は平均よりもはるかに高くなります。^[8]前述のように、並列 BFS の無害な競合の 1 つは、フロンティア内の複数の頂点が共通の隣接頂点を持つ場合、隣接頂点の距離が何度もチェックされることです。同期の助けを借りて距離の更新は依然として正確ですが、リソースが無駄になります。実際、次のフロンティアの頂点を見つけるために、訪問されていない各頂点は、隣接頂点がフロンティアにあるかどうかを確認するだけで済みます。これは、方向最適化の中心的なアイデアでもあります。さらに良いことに、相当数の隣接頂点がフロンティアにある場合、各頂点は入ってくるエッジをチェックすることで親をすばやく見つけることができます。

論文^[8]では、各頂点は親のいずれかがフロンティア内にあるかどうかをチェックするだけでよいボトムアップBFSが紹介されている。フロンティアがビットマップで表される場合、これは効率的であると判断できる。トップダウンBFSと比較して、ボトムアップBFSは競合を防ぐために親を自己検査することで、失敗のチェックを削減する。

しかし、ボトムアップBFSは1つの頂点をシリアル化する作業を必要とし、頂点の大部分がフロンティアにある場合にのみうまく機能します。その結果、方向最適化されたBFSはトップダウンBFSとボトムアップBFSを組み合わせる必要があります。より正確には、BFSはトップダウン方向から開始し、頂点の数が特定のしきい値を超えたときにボトムアップBFSに切り替え、その逆も同様に行う必要があります。^[8]

負荷分散は並列 BFS だけでなく、すべての並列アルゴリズムにおいて非常に重要です。バランスの取れた作業によって並列化の利点が向上するためです。実際、ほぼすべての並列 BFS アルゴリズム設計者は、アルゴリズムの作業分割を観察して分析し、そのための負荷分散メカニズムを提供する必要があります。

ランダム化は負荷分散を実現するための便利で簡単な方法の1つです。例えば、論文^[6]では、グラフを分割する前にすべての頂点識別子をランダムにシャッフルしてグラフを走査します。

CSR (Compressed Sparse Row)、バッグ構造、ビットマップなど、並列 BFS が恩恵を受けることができる特殊なデータ構造がいくつかあります。

CSR では、頂点のすべての隣接関係がソートされ、連続したメモリ チャンクにコンパクトに格納されます。頂点 i+1 の隣接関係は i の隣接関係の次に配置されます。左側の例では、C と R の 2 つの配列があります。配列 C にはすべてのノードの隣接関係リストが格納されます。配列 R には C のインデックスが格納され、エントリ R[i] は配列 C 内の頂点 i の隣接関係リストの開始インデックスを指します。CSR は、頂点の隣接関係へのアクセスに一定時間しかかからないため、非常に高速です。ただし、1D パーティショニングの場合のみ、スペース効率が優れています。^[6] CSR の詳細については、を参照してください。^[9] 2D パーティショニングの場合、超疎行列用の DCSC (二重圧縮スパース列) の方が適しています。^[10]

論文^[4]では、著者らはバッグ構造と呼ばれる新しいデータ構造を開発しています。バッグ構造はペナントデータ構造から構築されます。ペナントは2k^ノードxのツリ​​ーです。ここでkは非負の整数です。このツリーの各ルートxには、その子への2つのポインタx.leftとx.rightが含まれています。ツリーのルートには左の子のみがあり、残りの要素の完全な二分木です。 ^[4]

バッグ構造は、バックボーン配列 S を持つペナントのコレクションです。S 内の各エントリ S[i] は、ヌルポインターまたはサイズ s ⁱのペナントへのポインターのいずれかです。バッグへの挿入操作には⁠ ⁠${\displaystyle O(1)}$償却時間がかかり、2 つのバッグの結合には⁠ ⁠${\displaystyle \theta (\lg n)}$時間がかかります。バッグの分割にも⁠ ⁠${\displaystyle \theta (\lg n)}$時間がかかります。このバッグ構造により、並列 BFS はレイヤーの頂点を単一のデータ構造に並列に書き込み、後で効率的に並列に走査することができます。^[4]

さらに、ビットマップは、ボトムアップBFSに関係なく、どの頂点がすでに訪問されたかを記憶するのに非常に便利なデータ構造でもあります。^[11]またはトップダウンBFSで頂点が訪問されたかどうかを確認するだけです^[9]

Graph500 は、データ集約型スーパーコンピューティング問題の最初のベンチマークです。^[1]このベンチマークは、最初に 2 つのエンドポイントを持つエッジ タプルを生成します。次に、カーネル 1 は無向グラフを構築します。このグラフでは、カーネル 2 のみが後で実行される場合、エッジの重みは割り当てられません。ユーザーは、構築されたグラフに対して、カーネル 2 で BFS を実行するか、カーネル 3 で Single-Source-Shortest-Path を実行するかを選択できます。これらのカーネルの結果が検証され、実行時間が測定されます。

Graph500 は、カーネル 2 と 3 の 2 つのリファレンス実装も提供します。参照 BFS では、頂点の探索は、訪問した隣接頂点を通知するためにターゲット プロセッサにメッセージを送信するだけです。追加の負荷分散方法はありません。同期については、AML ( MPI3上に構築された SPMD 通信ライブラリである Active Messages Library 、Graph500 のような細粒度アプリケーションで使用することを意図した、MPI3 上に構築された SPMD 通信ライブラリ) バリアによって、各レイヤーの後の一貫したトラバーサルが保証されます。参照 BFS は、結果の正確性の検証にのみ使用されます。したがって、ユーザーはハードウェアに基づいて独自の BFS アルゴリズムを実装する必要があります。出力 BFS ツリーが正しい限り、BFS の選択に制約はありません。

結果の正確さは、参照された BFS からの結果との比較に基づいています。カーネル 2 および/またはカーネル 3 を実行するために 64 個の検索キーのみがサンプリングされるため、検索キーがサンプルに含まれていないためにこの結果が参照された結果と異なる場合でも、結果は正しいと見なされます。これらの 64 個の検索キーはカーネルを順番に実行して平均と分散を計算し、単一の検索のパフォーマンスを測定します。

TOP500とは異なり、Graph500 のパフォーマンス メトリックは1 秒あたりの走査エッジ数(TEPS) です。

• 並列アルゴリズム
• 分散アルゴリズム