SSSPベンチマーク

最近追加されたSSSPベンチマークであるが、カーネル1で生成され、カーネル2のBFSベンチマークで使われるのとまったく同じグラフを使い、サーチを開始する64個のルート頂点も同じものを使う。ただし、それぞれの辺に32bit単精度浮動小数点数の重みが追加されている。重みは(0、1)の値で、ランダムに生成される。

サーチ結果として、1つ前の頂点の頂点番号の配列と、最短の経路の長さの配列を出力する。

  • ISC 2019

    SSSPは、BFSで使ったものと同じグラフを使う。ただし、各辺は単精度浮動小数の(0,1)の乱数の重みを持ち、経路の長さは経路に含まれる辺の重みの合計とする

同じグラフを使うのであるが、SSSPはBFSよりもずっと難しい。BFSで辿る辺の数はO(V)で、頂点の数に比例するが、SSSPで辿る辺の数はO(E+VlogV)に比例し、辿る辺の数がずっと多い。従って、BFSのTEPSとSSSPのTEPSを比べるのは公平ではない。

また、SSSPでは辺に重みが付いているので、メモリから読むデータ量が多くなる。また、距離の配列を記憶するのにメモリが必要であり、より大きなメモリを必要とする。

例えば、今回のSSSPの1位はドイツのSuperMUC-NGであるが、グラフのスケールは37で、性能は1054GTEPSである。これに対して、BFSではSuperMUC-NGはスケール39のグラフを使い性能は6279.47GTEPSとなっている。

  • ISC 2019

    SSSPはO(E+VlogV)の辺をたどる必要があり、BFSよりたどる辺の数が多い。従って、SSSPとBFSのTEPSを比較しても不公平である

次の表は第4回のリストでのSSSPのTop10を示すものである。1位はドイツのライプニッツスーパーコンピューティングセンター(LRZ)のSuperMUC-NG、2位はLBNLのCori-1024、3位は韓国のNurionである。

  • ISC 2019

    SSSPベンチマークでのTop10のシステム。ドイツのSuperMUC-NGが1位、ローレンスバークレイ国立研究所のCori-1024が2位、韓国のNurionが3位となった

第4回のSSSPベンチマークの参加は22システムとなり、初めて20システムを超えた。そして、その中の8システムは複数ノードのマシンである。

SSSPのTEPS値はトップBFSのTEPS値と比べると2桁程度低い値である。そして、現在のところSSSPの結果を提出しているのは全てIntel CPUを使っているシステムである。

  • ISC 2019

    初めてSSSPリストのエントリが20システムを超えた。しかし、マルチノードのシステムは8システムである。SSSPのTEPS値はBFSのTEPS値の1/3～1/6である

SSSPリストの分析であるが、22システムの内の半分の11システムは米国の登録であり、カナダの6システムがこれに次いでいる。その他の国は1システムだけの登録である。しかし、ドイツのSuperMUC-NGはSSSPで1位になったマシンであり、各国のTEPS値の合計では米国の11システムの合計を上回る性能である。また、韓国のNurionは3位のマシンで、韓国も高いTEPS値を誇っている。その他の国はTEPS値が低く、小さなシステムでSSSPの実装を始めた段階と思われる。

  • ISC 2019

    SSSPリストの分析。システム数では米国が全体の半分の11システムで、カナダの6システムがそれに次ぐ。その他の国は1システムである。しかし、性能ではドイツのSuperMUC-NGは米国の11システムの合計より高いGTEPSを出している。韓国のNurionも大規模なシステムである

グラフ処理のエネルギー効率を競うGreenGraph

Green500がTop500のエネルギー効率を競うものであるように、「GreenGraph」はGraph500(現在はBFSだけでSSSPは入っていない)のエネルギー効率を競うものである。次の図はGreenGraphに登録されたシステムのエネルギー効率をプロットしたものである。プロットの縦軸の単位はMTEPS/Wで、横軸はグラフのスケールである。

スケールが35以上の大きなグラフを扱っているのは主に複数ノードのシステムであり、大規模から、超大規模マシンである。スケールが33以下の結果を登録しているのは主にシングルノードの小さなマシンである。

大規模マシンのエネルギー効率はゼロ付近に張り付いており、高いエネルギー効率を示しているのは小さなマシンである。スマートフォンはスケール20程度の小さなグラフを扱っているがかなり高いエネルギー効率を示している。また、32ノードのRaspberry Piのシステムは、マルチノードのマシンとしては非常に高いエネルギー効率を達成している。

  • ISC 2019

    GreenGraphに登録されたシステムのエネルギー効率を、スケールを横軸にとってプロットした図。スケールが35以上の大型のシステムでは数10MTEPS/Wと低いエネルギー効率である

これはビッグデータとスモールデータの処理は本質的に異なるものであることを示していると思われる。大きく分けると、シングルノードのシステムとマルチノードのシステムでエネルギー効率が大きく違う。

現在はGraph500は登録の最低基準は設けていない。そして、登録結果のスケール値の中央値は2014年から変わっておらず、30となっている。

GreenGraphでは、Small DataとBig Dataに分けてリストを作っているが、Big Dateの上位のシステムはスケール30というビッグの中では小規模なシステムが大部分であり、Graph処理にエネルギー効率を持ちこむと小規模の方が有利であり、規模の大きいスパコンは上位に出られないように見える。

大規模なグラフ処理を後押しするためには、GreenGraphのランキング方法を工夫することが必要と思われる。

  • ISC 2019

    スモールデータとビッグデータで本質的な違いがあるように見える。シングルノードのシステムとマルチノードのシステムの違いであることが多い

ということで、GreenGraphの登録結果のMTEPS/W値のランキングリストを作ったとすると、スマートフォンなどの小規模なシステムが上位に集まってしまう。しかし、それはGreenGraphが目指すものかというと疑問がある。

しかし、どうようにすべきかについては、まだまだ、BoFでユーザの声を集める必要があるように思われる。