ニュース / News

2021/11/24

効率的なスパコン設計につながるグラフ発見を競うコンペ「グラフ ゴルフ」で理論上最小の直径を持つ間接網を発見
～ネットワークスイッチを用いてCPUを間接接続する構成にも有効～

　大学共同利用機関法人 情報・システム研究機構 国立情報学研究所（NIIエヌアイアイ、所長：喜連川 優、東京都千代田区）は、未来のスーパーコンピュータ(スパコン)のネットワーク構成を発見するコンペティション「グラフ ゴルフ2021」^（*1）の表彰式を、オンラインで開催された国際シンポジウム「CANDAR2021」^（*2）で本日11月24日に行いました。「グラフ ゴルフ2021」は、スパコンなどで使われているネットワーク構成をCPU間の接続関係を表すグラフにおきかえ、CPU間のネットワークの効率的な設計につながる構成のグラフの発見を競うコンペです。今回は、2部門において優れたグラフを発見した中尾 昌広（理化学研究所計算科学研究センター）、塚本 雅生(関西大学)、花田 良子（関西大学）のチーム他を表彰しました。これらのグラフは、次世代のスパコンの超並列計算の通信時間の最小化など、実用への応用が期待されます。

　最近のコンピューターは大規模で複雑になってきており、スパコンでは最大で1千万以上のプロセッサーコアが相互に接続されています。膨大な数のコアをいかに効率的に相互接続するかというネットワーク構成（ネットワークトポロジー）の設計は、スパコンの処理能力に大きく影響します。本コンペでは、CPUを「頂点」、CPUとCPUをつなぐ配線を「辺」とみなし、ネットワークトポロジーを達成するグラフを構成しました。一つの頂点から最も離れた頂点までのホップ数（経由した辺数）を「直径」、各頂点間のホップ数の平均値を「平均パス長」と呼び、指定された条件で直径と平均パス長が最も小さいグラフを発見することを問題として設定しました。

　第6回となる本コンペは、ホスト(CPU)頂点とネットワークスイッチ頂点に区別するホスト-スイッチグラフ部門を新設しました。ホスト-スイッチグラフは、InfiniBandなどのネットワークスイッチを用いてCPU間を間接的に接続するスパコンのネットワーク構成を表しています。4月～10月に実施し^（*3）、国内外から91件（全6回にて延べ2,396件^（*4））の有効応募がありました。その結果、一般グラフの出題8問中4問および、ホスト-スイッチグラフの出題13問中6問において、理論上最小の直径を有するグラフを発見する成果が得られました。ホスト-スイッチグラフ部門では、スイッチ頂点に接続するホスト頂点数を不均一にする工夫が重要となる場合を中尾らのチーム他が発見しました (図1)。この結果は、間接網^（*5）の特徴が顕著に現れる展開といえます。

図1: 表彰となった中尾らのチームが発見したホスト-スイッチグラフ。ホスト頂点とそのリンクが赤色、スイッチ頂点とスイッチ頂点間のリンクが青色で示されている。

　グラフゴルフのホームページ(http://research.nii.ac.jp/graphgolf/2021/candar21/)では、過去5回のコンペの各表彰者の方々の全面的なご協力により、グラフゴルフに関連した国際会議等のイベントでの発表資料を公開することで、様々な優れたグラフの構成方法を分かりやすく解説しています。また、グラフゴルフに関連する学術論文や技術報告計26本のリストを同ホームページ上に掲載し、今後のグラフ発見の参考となるようにしています。

　実用上、グラフの直径の削減はスパコンの最長通信遅延の削減、グラフの平均パス長の削減はスパコンの平均通信遅延の削減に直結します。スパコンは日進月歩であり、スパコンに求められるネットワーク構成も変わっていきます。上位500台のスパコン^（*6）のうち、約8割のスパコンでは任意のネットワーク構成を実装することができるInfiniBandやイーサネットを採用しており、優れたグラフをネットワーク構成として採用することが技術的に可能です。本コンペは投稿されたグラフを公開することで、学術界や産業界に貢献していきます。

関連リンク

• グラフ ゴルフ
• グラフ ゴルフ2021

ニュースリリース（PDF版）

効率的なスパコン設計につながるグラフ発見を競うコンペ「グラフ ゴルフ」で理論上最小の直径を持つ間接網を発見
～ネットワークスイッチを用いてCPUを間接接続する構成にも有効～