発表のポイント：

• 高速な幅優先探索（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においてこれまで確認されていません。


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

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

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

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


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

・SCALE 43の結果
これまで「富岳」ではグラフの大きさに対してメモリ容量が足りず、SCALE 43は実行できませんでした。今回始めて、グラフデータの圧縮技術とForest Pruningによるグラフ縮小の効果により、計測が可能になりました。得られた性能は2023年11月のものと比べると約43%高く、SCALE 42の性能向上率よりもさらに大きな値です。しかしSCALE 43では性能計測に要する時間を抑えるためにGraph500が要求するBFS木の検算を省略したことから、記録はランキングに投稿されていません。


5．今後の展開
　共同研究グループでは、SCALE 43での性能測定を検算も含めて実施し、その性能をランキングに投稿すべくプログラムの効率化や実行方法の工夫に取り組んでいます。長期的には、他の研究チームの技術も取り込みながら性能を改善するともに、GPUを搭載したスーパーコンピュータでの効率的なグラフ処理技術の開発を行ってまいります。NTTではこのような取り組みを通じて最新の計算機システムの活用や大規模グラフ処理に関する技術を開発し、データマイニングやAIなど幅広い処理の性能向上により一層貢献していきます。

発表について
　Forest Pruningや「富岳」で計測した性能は、共同研究グループの他の成果と合わせThe International Conference for High Performance Computing, Networking, Storage, and Analysis (SC24)にて以下の論文で発表されます。なお今年の採択率は22.7%でした。
タイトル：Doubling Graph Traversal Efficiency to 198 TeraTEPS on the Supercomputer Fugaku
著者：新井淳也（NTT），中尾昌広（理研），井上雄登（フィックスターズ），寺西寛人（フィックスターズ），上野晃司（フィックスターズ），山村圭一郎（九大），佐藤三久（理研），藤澤克樹（東工大）
SC24 Webサイト：https://sc24.supercomputing.org/

【用語解説】
※1 グラフ：事物のつながりを頂点と枝によって表現したデータ。グラフはその柔軟性と表現力の高さから AI やセキュリティ、インフラ管理など様々な分野で重要な表現形式です。例えば路線図は、駅を頂点に、線路を枝に当てはめることでグラフとみなすことができます。このようなグラフは目的地までの適切な経路を割り出すために役立ちます。また知識を表現したグラフはAIなどで利用されます（図3）。さらに人物の行動や交友関係、通信記録、金融取引などもグラフで表現され（図4）、動画の推薦、サイバー攻撃の検知、マネーロンダリングの発見などに用いられます。 ※2 幅優先探索（breadth-first search, BFS）：グラフの探索方式のひとつ。BFSを用いると、ある頂点（始点）と他の頂点の間にある最も経由頂点数が少ない経路を発見できます。つながりに着目するグラフ分析において短い経路は有用な情報です。例えば鉄道や車での移動では短い経路が好まれます。また図の例で「1985年」と「東京都千代田区」のつながりに関心があるとすれば、「1985年」―「NTT」―「東京都千代田区」という経路が最も直接的な情報を表現しています。BFSは始点と枝で直接接続されている頂点に訪問し、次にそれらに接続されている頂点に訪問するという操作を繰り返すことでグラフ中の全ての到達可能な頂点に訪問します（図1）。BFSの訪問経路はBFS木として表現されます。

※3 Graph500：スーパーコンピュータの性能ランキングのひとつ。グラフ分析の重要性を踏まえ、BFS性能に基づくランキングとして2010年に創設されました。Graph500はBFSを通じたBFS木構築の性能をTEPS※6という指標で表します。なおGraph500には後にベンチマーク問題が追加され，現在はBFS、SSSP（単一始点最短経路）、Green（BFSの電力効率）の3部門でそれぞれランキングが作成されています。
Webサイト：https://graph500.org/

※4 共同研究グループ：理化学研究所、東京工業大学、株式会社フィックスターズ、およびNTTから成ります。NTTは2023年11月に参加を発表しました。

※5 計算ノード：CPUやメモリを備えた、システムを構成する計算機の単位。

※6 TEPS, GTEPS（ギガTEPS）：Traversed edges per second (TEPS)はGraph500で用いられる性能指標。端的にはTEPSはグラフの枝の数を処理時間で割った値です。GTEPSは1,000,000,000 TEPSを表します。