写真提供:マイナビニュース

写真拡大

●13回目を迎えた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が必要になる。

●BFSの性能の分析手法
これに対してScott Beamerなどは、未到達の頂点からスタートして、1つの辺ですでに到達している頂点に繋がっている頂点を、次の到達頂点リストに加えるという逆方向のサーチを考えた。未到達の頂点が少なくなった状況では、この逆方向のサーチの方が効率が良いので、未到達の頂点数が少なくなると、順方向から逆方向サーチに切り替える。

このBeamerのアルゴリズムを使うと、処理する辺の数を最大1/10に減らすことができる。しかし、TEPS性能の計算は実際に処理した辺の数ではなく、頂点数の16倍という全ての辺の数を使って計算されるので、TEPS性能を上げることができる。

また、通信量を減らすため、通信を宛先ノードごとに送るデータまとめておき、一括して送るとか、他ノードの頂点のラベルを圧縮して通信データ量を減らすなどの最適化が行われる。

並列BFSは、次の図のように、グラフデータを各ノードに与えるサブグラフに分割し、それを各ノードで並列に処理して、到達頂点を見つけ、元のグラフデータを更新するというループになる。

ただし、グラフのデータは多数のノードに分散して格納されているので、Batch Analysisで見つけた新しい到達ノードの更新は、あちこちのノードに対して行われることになり、インタコネクトや、メモリアクセスの性能がネックになる。

BFSの性能の分析に当たって、システムのアーキテクチャをインタコネクトとコアのアーキテクチャの組み合わせの2次元の分析を行っている。インタコネクトはEthernetなどのコモディティのネットワーク(L)、カスタムなどの高性能ネットワーク(T)、シェアードメモリ(S)、分散型シェアードメモリ(D)の4分類。コアアーキテクチャはH、L、B、X、V、O、G、Mの8つに分類している。そして、散布図では点の色を変えているのであるが、残念ながらWeb記事では判別が難しい。

次の図はGraph500のデータを時系列で表わしたもので、トップのTEPS性能は2012年末までは順調に伸びているが、それ以降の伸びは比較的少ない状態である。

次の図は、システムの総コア数を横軸にとったグラフで、1000コア以下と1万コア以上の領域の性能カーブは連続していない。1000コア以下のシステムは1本のラックに収まるのに対して、1万コア以上のシステムは複数のラックが必要となり、ノード間の通信がネックになることから、このような傾向になると考えられる。

そして、共通メモリの空間(ドメイン)の数を横軸にとり、縦軸をドメインあたりの性能にすると、1ドメインのシステムが圧倒的に効率が良く、複数ドメインになると2桁近く性能が下がる。これはCPUチップが1個の場合は通信オーバヘッドが小さいのに対して、複数ドメイン間の通信オーバヘッドが大きいことが効いている。また、500ドメインあたりにも不連続があるように見えるが、これはマルチラックの切れ目かと思われる。

次のグラフは、頂点数を横軸にとったグラフである。頂点数が増加するにつれて、106頂点までは性能が減少し、それ以上の頂点数では性能が増加しているが1億〜10億頂点で不連続なへこみも見られる。

結論であるが、BFSの性能には、1ドメイン、1ラック、複数ラックの3つの性能領域がある。1ドメインはコアあたりの性能は圧倒的に高い。それが複数ドメインになると大幅に性能が低下する。しかし、1ラックの領域ではコア数に比例して問題サイズを増やすウイークスケールはうまくいく。

マルチラックになるところで、また、性能低下が起こる。しかし、100万コアまで性能はスケールする。

TEPS性能はメモリバンド幅と高い相関を持っている。しかし、分散メモリよりもシェアードメモリの方がメモリバンド幅を有効に使えている。

低並列の場合、どのようになるかは興味深いところで、このような報告が出てきて欲しいと述べてKogge教授は、分析の発表を締めくくった。

(Hisa Ando)