NTTのアルゴリズムによりスーパーコンピュータ「富岳」の大規模グラフ探索性能が約20%向上　スパコン性能ランキング9期連続世界1位に貢献

2024年6月27日 By ロボスタ編集部

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

本技術はスーパーコンピュータの性能ランキング「Graph500」のBFS部門でスーパーコンピュータ「富岳」が保有する首位記録をさらに約20%向上させることに貢献。本技術を用いることで大規模なグラフデータを用いるデータマイニングやAIなど幅広い処理の性能向上を期待できる。

本技術を含む共同研究グループの成果は、2024年11月17日から22日までアメリカ・アトランタで開催される高性能計算分野のトップカンファレンスThe International Conference for High Performance Computing, Networking, Storage, and Analysis（SC24）にて発表される。

背景

実社会における複雑な情報の多くはグラフとして表現される。

NTTは長年、大規模なグラフをより短時間かつ低消費電力で処理するための研究を行っており、その中で効率的なBFSを可能にするアルゴリズム「Forest Pruning」を考案。2023年11月発表のGraph500 Greenビッグデータ部門ランキングでは、GPU上でForest Pruningを含むNTTのグラフ処理技術を用いることで市販プロセッサとして最高の電力効率を記録した。

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

技術のポイント

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

従来のBFSの流れ　頂点②を始点とする場合を示す。始点から近い順に枝で接続された頂点を訪問し、グラフの全ての頂点を発見する。この訪問経路を表現したBFS木の構築がGraph500における性能計測対象の処理である。

本技術は同じグラフに対して異なる始点で繰り返しBFSを行う場合に効果的である。事前計算を通じて後続の処理を高速化する枠組みは様々な問題に適用されてきが、Forest Pruningのように部分的な解を事前に計算する手法は、BFSにおいてこれまで確認されていない。

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

Forest Pruningを用いたBFS木構築の流れ

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

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

実験の概要

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

SCALE 42の結果

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

SCALE 43の結果

これまで「富岳」ではグラフの大きさに対してメモリ容量が足りず、SCALE 43は実行できなかった。今回初めて、グラフデータの圧縮技術とForest Pruningによるグラフ縮小の効果により、計測が可能となった。

得られた性能は2023年11月のものと比べると約43%高く、SCALE 42の性能向上率よりもさらに大きな値だが、SCALE 43では性能計測に要する時間を抑えるためにGraph500が要求するBFS木の検算を省略したことから、記録はランキングに投稿されていない。

今後の展開

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

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

関連サイト
日本電信電話株式会社