GAP Benchmarkの各プログラムの中身を調べている。sssp.ccについて調べた。

sssp: Single source shortest path

いわゆる一般的なグラフ問題で、あるノード(1点：single)からすべてのノードに対する最短距離を検出するためのアルゴリズムを総じてSSSPと呼ぶ。これのもっとも有名なものにダイクストラ法があり、発展形としてすべてのノードからの最短距離を検出するワーシャル・フロイド法が有名である。

GAPでは、SSSPのベンチマークとしてDelta Stepping法というものが使われている。 Delta Stepping法はダイクストラ法と似ているが、よりマルチスレッドでの動作に適しているという特徴がある。

./sssp -f benchmark/graphs/twitter.wsg -n64 -d2 > benchmark/out/sssp-twitter.out
./sssp -f benchmark/graphs/web.wsg -n64 -d2 > benchmark/out/sssp-web.out
./sssp -f benchmark/graphs/road.wsg -n64 -d50000 > benchmark/out/sssp-road.out
./sssp -f benchmark/graphs/kron.wsg -n64 -d2 > benchmark/out/sssp-kron.out
./sssp -f benchmark/graphs/urand.wsg -n64 -d2 > benchmark/out/sssp-urand.out

また、このSSSPはGraph 500のベンチマークとしても使用されているらしい。

news.mynavi.jp

Graph処理のベンチマークであるが、まずは巨大なグラフを作る必要があり、この部分がカーネル1である。そして、BFS(Breadth First Search)という処理がカーネル2、SSSP(Single Source Shortest Path)という処理がカーネル3と呼ばれている。

まずは、Delta Steppingの基本的なアルゴリズムについて。これはWikipediaとか、ChatGPTに聞きながらいろいろ勉強した。

バケットと呼ばれるデータ構造をもとにアルゴリズムが進んでいく。バケットは複数に分かれており、δステップ毎に区間が区切られており、その区間に所属するノードが入る仕組みになっている。つまり、最大ノード間距離がLの場合、L/δ個のバケットが用意されることになる。

まず、各頂点vについて、始点sのノードからの最短距離d[v]を無限大に設定する状態からスタートする。この時、最初のバケット(bucket[0])に、始点sを挿入する。

アルゴリズムが終了するまで以下の手順を繰り返します：

空でない最小のバケットBを見つける
Bから頂点vを取り出し、vを「訪問済み」とする
vから直接到達可能な全ての頂点uについて、以下のステップを実行する：
1. 頂点uまでの新しい予想距離を計算する：d_new = d[v] + w(v, u)。ここで、w(v, u)は頂点vとuの間のエッジの重みである
2. d_newがd[u]より小さい場合、d[u]をd_newに更新し、頂点uを対応するバケットに挿入する。この挿入は、uが既に別のバケットに存在している場合でも行う。
全ての頂点が訪問済みになったらアルゴリズムを終了する

以下の資料を見ながら、具体的に考えてみる。

cs.iupui.edu

以下では、わかりやすくするために各ステップでノードの名前と距離を表示している（PowerPointで編集するの疲れた...）

１. この例では、各バケットのδ値は3で、B[1]=[3, 6)を保持している。中央のSourceノードはB[0]に格納されており、そこから接続されているノードに対して探索を行う。