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

発表のポイント：

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においてこれまで確認されていません。

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

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

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

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

3. 実験の概要

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

・SCALE 42の結果

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

・SCALE 43の結果

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

4. 今後の展開

共同研究グループでは、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）、動画の推薦、サイバー攻撃の検知、マネーロンダリングの発見などに用いられます。

図3：知識グラフの例
「1985年」と「東京都千代田区」は一見すると関係を見出しにくいが、「NTT」がそれらの間にあることなどを読み取ることが可能

図4：複雑な情報を統合したグラフの例
人物の行動や交友関係、コンピュータ間の通信、口座間の金融取引など、グラフは様々な情報を表現できる

^※2幅優先探索（breadth-first search, BFS）：グラフの探索方式のひとつ。BFSを用いると、ある頂点（始点）と他の頂点の間にある最も経由頂点数が少ない経路を発見できます。つながりに着目するグラフ分析において短い経路は有用な情報です。例えば鉄道や車での移動では短い経路が好まれます。また図3の例で「1985年」と「東京都千代田区」のつながりに関心があるとすれば、「1985年」―「NTT」―「東京都千代田区」という経路が最も直接的な情報を表現しています。BFSは始点と枝で直接接続されている頂点に訪問し、次にそれらに接続されている頂点に訪問するという操作を繰り返すことでグラフ中の全ての到達可能な頂点に訪問します（図1）。BFSの訪問経路はBFS木として表現されます。

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

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

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

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