NTTは2024年6月25日、BFS（Breadth-First Search、幅優先探索）を高速に実行するためのアルゴリズム「Forest Pruning」を開発したと発表した。同アルゴリズムは、富士通と理化学研究所が共同開発したスーパーコンピューター「富岳」向けに実装済みで、富岳が2024年5月に発表されたスパコンの性能ランキング「Graph500」のBFS部門で9期連続の1位を獲得したことに貢献したという。
5月のGraph500では、Forest Pruningとグラフ構造データの圧縮技術をプログラムに実装した。15万2064ノードを用いて約4兆4000億個の頂点と約70兆4000億個の枝で構成する超大規模グラフ構造の「幅優先探索問題」を解いた結果、16万6029GTEPS（ギガテップス）のスコアを達成した。TEPS（Traversed Edges Per Second）は、1秒間に処理した枝の数を指す。2023年11月に発表された前回のスコア13万8867GTEPSから約20%向上した。
Forest Pruningの処理は事前計算とBFS木の構築の2段階で構成。事前処理では、グラフ構造を木構造の集合と木構造ではない部分の2つに分解する。Graph500の規定上、事前処理は性能計測の対象には含まれないという。2段階目のBFS木構築では、まず与えられた始点に基づいて木構造ではない部分にBFSを実行し、それにより得られた部分的なBFS木を、事前計算で分解した木構造と接合する。こうして全体のBFS木を構築する。
Forest Pruningを用いたBFS木構築の流れ
（出所：NTT）
[画像タップで拡大表示]
BFSはグラフ構造処理の基礎となっているため、脳機能の分析や創薬などに対して役立つという。
0 コメント:
コメントを投稿