日本電信電話株式会社（以下、NTT）は、頂点と枝により事物の関連性を示したデータである「グラフ」に対して、頂点全体のつながりを始点から近い順に辿る計算BFSを高速に行うためのアルゴリズム「Forest Pruning」を開発した。
同技術は、スーパーコンピュータの性能ランキング「Graph500」のBFS部門で、スーパーコンピュータ「富岳」が保有する首位記録を、さらに約20%向上させることに貢献した。同技術を用いることで、大規模なグラフデータを用いるデータマイニングやAIなど、幅広い処理の性能向上が期待できる。
「Forest Pruning」の特徴は、グラフの中でもともと木構造になっている部分の探索を省略する点にある。
木構造である部分はそのままの形でBFS木の一部を構成するため、事前に木を発見し分離しておくことで、都度それらを探索することなく、短時間でBFS木を構築できる。さらに、木の分離は、グラフの縮小によって消費メモリ量を削減する効果もある。
なお、「Forest Pruning」の処理は、事前計算としてのグラフの分解と、BFS木構築における結果生成の2つに分けられる。
事前計算では、グラフを木の集合と木でない部分の2つに分解し、それぞれ異なるデータ構造で保存する。Graph500の規定上、この処理は性能計測対象に含まれない。
BFS木構築では、与えられた始点に基づき、木でない部分においてのみ従来通りのBFSを実行する。それにより得た部分的なBFS木に、事前計算で分解しておいた木をコピーして接合することで、完全なBFS木を得る。
与えられた始点が木の集合と木でない部分のどちらに含まれるかにより場合分けされ、始点の選び方に関係なく正しいBFS木が構築される。
このように、「Forest Pruning」は事前計算を行うことで、BFS木構築の処理を削減する。同じグラフで始点を変更しながら繰り返しBFSを行う場合、BFS木構築のみが繰り返し実行されるため、同技術によって全体の処理時間を短縮することが可能だ。
また、NTTを含む共同研究グループは「Forest Pruning」に加え、新しく開発したグラフデータの圧縮技術を、「富岳」向けのGraph500 BFSベンチマークプログラムに実装し、Graph500で規定されたSCALE 42および43のグラフで性能を計測した。
その結果、SCALE 42では、前回の性能から約20%の向上が得られ、SCALE 43では約43%の性能向上が確認された。しかしSCALE 43では性能計測に要する時間を抑えるためにGraph500が要求するBFS木の検算を省略したことから、記録はランキングに投稿されていないとのことだ。
共同研究グループでは、今後もプログラムの効率化や実行方法の工夫に取り組み、SCALE 43での性能測定を検算も含めて実施し、その性能をランキングに投稿する予定だ。
また、長期的には、他の研究チームの技術も取り込みながら性能を改善するともに、GPUを搭載したスーパーコンピュータでの効率的なグラフ処理技術の開発も行っていくとしている。
なお、同技術を含む共同研究グループの成果は、2024年11月17日から22日までアメリカ・アトランタで開催される高性能計算分野のカンファレンス「The International Conference for High Performance Computing, Networking, Storage, and Analysis（SC24）」にて発表される予定だ。
無料メルマガ会員に登録しませんか？
IoTNEWSは、毎日10-20本の新着ニュースを公開しております。 また、デジタル社会に必要な視点を養う、DIGITIDEという特集コンテンツも毎日投稿しております。
そこで、週一回配信される、無料のメールマガジン会員になっていただくと、記事一覧やオリジナルコンテンツの情報が取得可能となります。
- DXに関する最新ニュース
- 曜日代わりのデジタル社会の潮流を知る『DIGITIDE』
- 実践を重要視する方に聞く、インタビュー記事
- 業務改革に必要なDX手法などDXノウハウ
など、多岐にわたるテーマが配信されております。
また、無料メルマガ会員になると、会員限定のコンテンツも読むことができます。
無料メールから、気になるテーマの記事だけをピックアップして読んでいただけます。 ぜひ、無料のメールマガジンを購読して、貴社の取り組みに役立ててください。
無料メルマガ会員登録
IoTに関する様々な情報を取材し、皆様にお届けいたします。
