●科学技術ニュース●NTT、世界最速アルゴリズムにより「富岳」の大規模グラフ探索性能が約20%向上し「Graph500」9期連続世界1位に貢献

　NTTは、グラフ（頂点と枝により事物の関連性を示したデータ）に対して、頂点全体のつながりを始点から近い順に辿る計算（BFS）を高速に行うためのアルゴリズム「Forest Pruning」を開発した。

　同技術はスーパーコンピュータの性能ランキング「Graph500」のBFS部門でスーパーコンピュータ「富岳」が保有する首位記録をさらに約20%向上させることに貢献した。

　同技術を用いることで大規模なグラフデータを用いるデータマイニングやAIなど幅広い処理の性能向上を期待できる。
　
　実社会における複雑な情報の多くはグラフとして表現されている。

　NTTは長年、大規模なグラフをより短時間かつ低消費電力で処理するための研究を行っており、その中で効率的なBFSを可能にするアルゴリズム「Forest Pruning」を考案した。

　2023年11月発表のGraph500 Greenビッグデータ部門ランキングでは、GPU上でForest Pruningを含むNTTのグラフ処理技術を用いることで市販プロセッサとして最高の電力効率を記録した。

　今回、スーパーコンピュータ「富岳」でGraph500に取り組む共同研究グループへ参加し、Forest Pruningを「富岳」向けに実装したことで成果が得られた。

　Forest Pruningはグラフの中でもともと木構造になっている部分の探索を省略。木構造である部分はそのままの形でBFS木の一部を構成するため、事前に木を発見し分離しておくことで、都度それらを探索することなく短時間でBFS木を構築できる。

　さらに木の分離はグラフの縮小によって消費メモリ量を削減する効果もある。

　同技術は、同じグラフに対して異なる始点で繰り返しBFSを行う場合に効果的。

　事前計算を通じて後続の処理を高速化する枠組みは様々な問題に適用されてきたが、Forest Pruningのように部分的な解を事前に計算する手法は、BFSにおいてこれまで確認されていない。

　同共同研究グループでは、SCALE 43での性能測定を検算も含めて実施し、その性能をランキングに投稿すべくプログラムの効率化や実行方法の工夫に取り組んでいる。

　長期的には、他の研究チームの技術も取り込みながら性能を改善するともに、GPUを搭載したスーパーコンピュータでの効率的なグラフ処理技術の開発を行う。NTTではこのような取り組みを通じて最新の計算機システムの活用や大規模グラフ処理に関する技術を開発し、データマイニングやAIなど幅広い処理の性能向上により一層貢献していく。＜NTT＞