世界最速、NTTのアルゴリズムにより「富岳」の大規模グラフ探索性能が約20%向上 ～スパコン性能ランキング「Graph500」における9期連続世界1位に貢献～

[画像1]https://digitalpr.jp/simg/2341/90442/700_220_20240625120328667a3380c1c56.JPG


　Forest Pruningの処理は事前計算としてのグラフの分解とBFS木構築における結果生成の2つに分けられます（図2）。

事前計算：グラフを木の集合とそれ以外の部分2つに分解し、それぞれ異なるデータ構造で保存。Graph500の規定上、この処理は性能計測対象に含まれない。
BFS木構築：与えられた始点に基づき、木でない部分においてのみ従来通りのBFSを実行する。それによる得た部分的なBFS木に、事前計算で分解しておいた木をコピーして接合することで完全なBFS木を得る。与えられた始点が木の集合と木でない部分どちらに含まれるかにより場合分けされ、始点の選び方に関係なく正しいBFS木が構築される。



[画像2]https://digitalpr.jp/simg/2341/90442/600_298_20240625120328667a3380be90e.JPG


　このようにForest Pruningは事前計算を行うことでBFS木構築の処理を削減します。同じグラフで始点を変更しながら繰り返しBFSを行う場合、BFS木構築のみが繰り返し実行されるため、本技術によって全体の処理時間を短縮することができます。

3．実験の概要
　NTTを含む共同研究グループは、Forest Pruningに加え新しく開発したグラフデータの圧縮技術を、「富岳」向けのGraph500 BFSベンチマークプログラムに実装しました。そして「富岳」を構成する計算ノード※5のうち152,064台（全体の約96%）を用いて、Graph500で規定されたSCALE 42および43のグラフで性能を計測しました。表にそれぞれのSCALEで生成されるグラフの規模（頂点と枝の数）および性能計測結果を示します。


[画像3]https://digitalpr.jp/simg/2341/90442/700_178_20240625120328667a3380b4b1e.JPG


・SCALE 42の結果
SCALE 42では2023年11月に発表した前回の性能（138,867 GTEPS※6）から、約20%の向上が得られました。今回実装したそれぞれの機能の性能への貢献を調査した結果、この性能向上はほぼForest Pruningによって得られていることが確認できました。この記録はJune 2024ランキングとしてGraph500のWebサイトに掲載されています。