NTT開発のアルゴリズム、スパコン「富岳」の大規模グラフ探索性能を約20％向上

「BFS木の構築を高速化することを目的とした実装であり、グラフの一部がそのままBFS木に現れることに着目。同じ形で現われる部分を事前に発見することで、BFS木を構築する処理を削減した」という。

事前計算では、入力されるグラフを受け取り、グラフを木の部分と、それ以外の部分に分離。この処理はGraph500の性能計算範囲には含まれない。実際の処理においては、木ではない部分だけを対象にBFSを実行して、BFS木を構築。事前計算で構築した木の部分については、そのままコピーして、接ぎ木のようにして利用する。「従来は3ステップでBFSの処理を行っていたが、1ステップで終了できる。また、木を除いた小さいグラフのなかで処理できるようになるという特徴もある。繰り返し行われるBFSの時間を短縮し、高速化とともに、省電力化を実現できるほか、通常と同じBFS木をコピーするため、近似値などとは異なり、正確に構築できること、木の分離によりグラフを縮小できるため、省メモリで処理ができ、同じシステムでより大規模なグラフを処理できるメリットもある」と説明した。

測定においては、頂点数が約4兆4000億のSCALE42では、約20％の性能向上となり、約8兆8000億のSCALE43では19万8321GTEPSの性能を実現できたという。SCALE43では、グラフの規模が大きいため、富岳ではメモリ量が不足しており計算ができなかったが、Forest Pruningのグラフ縮小の効果と、新たなグラフデータ圧縮技術により、初めて実行に成功したという。

SCALE43の成果については、世界最大級のHPC会議であるSC24において論文として測定結果を投稿し、採択されたという。次回のGraph500からは、SCALE43の結果も投稿する予定だ。

今後は、富岳の共同研究グループにおいて、GPU搭載スパコン向けのプログラム開発を進めるという。また、Forest Pruningのソースコードを公開することになる。

NTTの新井主任研究員は、Forest Pruningの実装について、「木の分離を行う部分がポイントであり、ここでピーク時に消費メモリ量を増やさないことに気をつけた。富岳のような大規模なスパコンでは、特定のノードに通信が集中するとメモリがあふれるため、データを各ノードに分散して配置することにこだわった」という。

また、「2023年の計測では、アップルのM1 Maxでは10％の性能向上を実現し、NVIDIAのRTX A6000では約30％の性能向上の実績があったが、富岳での20％の性能向上は想定していなかった。富岳では頂点が減ったことで、ノード間の通信量が減り、それが性能に影響し、想定を上回る性能向上になった」とした。