木構造の事前分離によりBFS木構築を高速化、富岳で約20%の性能向上

NTTがグラフ探索の高速化アルゴリズム開発 スパコン富岳のBFS世界1位に貢献

　NTTは、2024年6月25日、グラフ探索を高速化するアルゴリズムを開発したことを発表した。

　多くの情報は事物のネットワーク構造として解釈可能であり、そのつながりを「頂点」と「辺」で表現するグラフは、都市インフラやAI、セキュリティ、創薬などの分野で重要視されている。

　このグラフデータの活用に向け、同社ではグラフ処理における基礎的な要素技術であるBFS（幅優先探索）の研究を続けてきた。BFSは、グラフ全体の頂点を近い順に辿る計算方法となる。

木構造の事前分離により BFS木構築を高速化

　今回NTTが確立したのは、「Forest Pruning」という、始点から近い順に頂点を辿るための「BFS木」の構築を高速化するアルゴリズムだ。

　まず、事前計算でグラフの一部（木構造部分）を分離。始点が与えられた際に、残ったグラフで頂点を辿って部分的なBFS木を構築する。そこに分離しておいた木構造部分を接合して、完全なBFS木を構築する。

処理の流れ：グラフの一部（木構造の部分）を事前に発見して分離、BFS木構築時に接続する

　このアルゴリズムによって、繰り返されるBFSの時間を短縮して、高速化および省電力化を実現する。通常のBFSと同一のBDS木構築が担保され、木構造部分の分離でグラフが縮小されることで、消費メモリ量も削減される。

　同技術は、同じグラフに対して、異なる始点でBFSを繰り返す用途に効果的だという。

「富岳」の大規模グラフ探索性能が約20%向上

　NTTを含むスーパーコンピュータ「富岳」の共同研究グループでは、Forest Pruningと新たなグラフデータの圧縮技術を富岳向けに実装。スーパーコンピュータの性能ランキング「Graph500」のBFS部門で、富岳が保有する最高記録を約20%向上させ、同ランキングの9期連続世界1位に貢献したという。

　富岳を構成する計算ノードのうち15万2064台（全体の約96%）を用いて、Graph500で規定されたSCALE42および43のグラフで性能を計測。SCALE42では約20%の性能向上を、SCALE43では約43%の性能向上を実現した。なお、SCALE43は、実験時間短縮のためにGraph500で要求されている検算処理を省略したことから、ランキングには投稿していない。

富岳の性能向上の結果

■関連サイト

• ニュースリリース