SC16 - 京コンピュータが1位を堅持したGraph500

TOP500は、スパコンの浮動小数点演算性能を測ってランキングを行っている。浮動小数点演算の性能は重要であるが、スパコンに求められる能力はそれだけではない。大規模なグラフの処理も、次の図に示すように、色々な分野で重要になってきている。ということで、グラフを処理する性能を競うGraph500が始まった。

ここで言うグラフは、多数の点とそれらの間を繋ぐ線の集まりで、例えば、交差点を点、交差点を繋ぐ道路を線とすると、道路網を表すグラフとなる。それ以外にも色々なものがグラフとして表すことができ、グラフ処理が重要になると考えられるビジネス分野としては、サイバーセキュリティ、患者の医療情報、人と人のつながりを表すソーシャルネットワーク、海運などの荷物の移動データの整理、例えば人間の脳のようなニューロンのネットワークなどの分野が挙げられる。

今回のGraph500は、第13回目である。最初は9件しかエントリが無かったが、今回は216エントリまでになった。しかし、まだ、500には届いてない。

今回の216エントリを国別にみると、米国が94エントリと43.5%を占め、日本が57エントリで26.4%を占める。それに続くのが、中国、ロシア、カナダ、スイス、台湾といった国々である。

次の図に、今回のGraph500の上位10エントリを示す。Graph500は同じスパコンでも問題の規模やマシンの規模が違う測定結果を別々のエントリとして登録できることになっているので、216件のエントリが216台のスパコンとは限らない。例えば、Miraは上位10エントリの中に3つのコア数の異なるエントリがある。

第13回となった今回のGraph500では、引き続き、京コンピュータが1位を守った。そして、2位が神威太湖之光、3位がローレンスリバモア国立研究所のSequoia、4位がアルゴンヌ国立研究所のMiraで、この部分は前回から変わっていない。

今回のGraph500で新しいのは、6位と9位にMiraの新しい測定結果が入ったことである。

Graph500は、3種類の問題を想定しているが、現在、ランキングに使われているのは、幅優先探索(Breadth First Search:BFS)という問題の処理性能である。BFSで使われるグラフは、それぞれの点(頂点と呼ぶ)に繋がる線(辺と呼ぶ)の本数は、平均16本で、頂点の数は、ランキングの表の右から2番目に書かれている。京コンピュータと太湖之光は40と書いてあり、頂点の数は2の40乗(約1兆頂点)である。3位のSequoiaは41であるので、約2兆頂点のグラフを扱っている。

このグラフは、Kroneckerグラフという種類のグラフで、人のつながりのように、グループの中の繋がりが多いが、他のグループともある程度繋がっており、大きなグループを単位としても同様に、同じ上位のグループに属するグループ間の接続が多いが、他の上位グループへもある程度の接続があるという、どのスケールで見ても同じような接続パターンが見えるというグラフになっている。

なお、BFSプログラムへの入力は、両端の頂点番号が書かれた辺のデータだけであり、グラフの頂点の数はBFSプログラムには与えられない。また、頂点や辺に付けられる番号もランダムに入れ替えられており、番号やデータの順番は手がかりにならないようになっている。

BFSは、スタートの頂点を選び、そこから辺で直接繋がっているすべての頂点を見つける。その次は、見つかった頂点から、辺で直接繋がっているすべての頂点を見つけるという作業を繰り返し、グラフのすべての頂点を見つけるという問題である。そして、辿った辺の数をすべての頂点を見つけるまでの計算時間で割ったTEPS(Traversed Edge Per Second)で性能を表す。

九大などの国際研究グループは、京コンピュータを使い、38621.4GTEPSをマークして1位になっている。なお、太湖之光は23755.7GTEPSで2位になっている。

右下の表のように、頂点の数で、問題規模はToyからHugeまであり、それぞれのサイズでの頂点数と、グラフ全体を格納するのに必要なメモリ量が書かれている。表には無いが、京コンピュータのサイズ40の場合は、282TBのメモリが必要になる。

BFSを多数の計算ノードで並列に実行する場合は、頂点リストを分割して、各計算ノードに与える。それぞれの頂点のデータには、親となっている頂点番号と、その頂点がすでに見つかったものであることを示すフラグを設ける。

そして、全部のノードで並列に繋がっている頂点を見つけデータを更新する。これを1レベル終わると、新たに見つかった頂点から繋がっている次のレベルの頂点を見つけるという操作を繰り返す。

このためには、1レベルについて、2回のバリアと、全頂点が見つかったかどうかを調べるAllReduceが必要になる。