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

【用語解説】
※1 グラフ：事物のつながりを頂点と枝によって表現したデータ。グラフはその柔軟性と表現力の高さから AI やセキュリティ、インフラ管理など様々な分野で重要な表現形式です。例えば路線図は、駅を頂点に、線路を枝に当てはめることでグラフとみなすことができます。このようなグラフは目的地までの適切な経路を割り出すために役立ちます。また知識を表現したグラフはAIなどで利用されます（図3）。さらに人物の行動や交友関係、通信記録、金融取引などもグラフで表現され（図4）、動画の推薦、サイバー攻撃の検知、マネーロンダリングの発見などに用いられます。

[画像5]https://digitalpr.jp/simg/2341/90442/700_152_20240625120327667a337f56bff.JPG





[画像6]https://digitalpr.jp/simg/2341/90442/700_274_20240625120328667a33801aa21.JPG


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

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

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

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

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