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

発表のポイント：

高速な幅優先探索（BFS）アルゴリズムを開発しました。
「富岳」において頂点数約4.4兆、枝数70.4兆のグラフに対するBFSを平均0.42秒まで高速化しました。
大規模グラフを用いるデータマイニングやAIなど幅広い処理の性能向上を期待できます。

　日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田　明、以下「NTT」）は、グラフ※1（頂点と枝により事物の関連性を示したデータ）に対して、頂点全体のつながりを始点から近い順に辿る計算（BFS※2）を高速に行うためのアルゴリズム「Forest Pruning」を開発しました。本技術はスーパーコンピュータの性能ランキング「Graph500※3」のBFS部門でスーパーコンピュータ「富岳」が保有する首位記録をさらに約20%向上させることに貢献しました。本技術を用いることで大規模なグラフデータを用いるデータマイニングやAIなど幅広い処理の性能向上を期待できます。
　本技術を含む共同研究グループの成果は、2024年11月17日から22日までアメリカ・アトランタで開催される高性能計算分野のトップカンファレンスThe International Conference for High Performance Computing, Networking, Storage, and Analysis (SC24)にて発表されます。

1．背景
　実社会における複雑な情報の多くはグラフとして表現されます。NTTは長年、大規模なグラフをより短時間かつ低消費電力で処理するための研究を行っており、その中で効率的なBFSを可能にするアルゴリズム「Forest Pruning」を考案しました。2023年11月発表のGraph500 Greenビッグデータ部門ランキングでは、GPU上でForest Pruningを含むNTTのグラフ処理技術を用いることで市販プロセッサとして最高の電力効率を記録しました。今回、スーパーコンピュータ「富岳」でGraph500に取り組む共同研究グループ※4へ参加し、Forest Pruningを「富岳」向けに実装したことで本発表の成果が得られました。

2．技術のポイント
　Forest Pruningはグラフの中でもともと木構造になっている部分の探索を省略します。木構造である部分はそのままの形でBFS木の一部を構成するため（図1）、事前に木を発見し分離しておくことで、都度それらを探索することなく短時間でBFS木を構築できます。さらに木の分離はグラフの縮小によって消費メモリ量を削減する効果もあります。本技術は同じグラフに対して異なる始点で繰り返しBFSを行う場合に効果的です。事前計算を通じて後続の処理を高速化する枠組みは様々な問題に適用されてきましたが、Forest Pruningのように部分的な解を事前に計算する手法は、BFSにおいてこれまで確認されていません。