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

これに対して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教授は、分析の発表を締めくくった。