2019-11-26 国立情報学研究所
効率的なスパコン設計につながるグラフ発見を競うコンペ「グラフ ゴルフ」で理論上最小の直径を持つグラフを16パターンで発見
次世代スパコンの計算時間の最小化などの応用に期待
大学共同利用機関法人 情報・システム研究機構 国立情報学研究所（NII、所長：喜連川 優、東京都千代田区）は、未来のスーパーコンピュータ(スパコン)のネットワーク構成を発見するコンペティション「グラフ ゴルフ2019」（*1）の表彰式を、長崎県長崎市で開催された国際シンポジウム「CANDAR2019」（*2）で本日11月26日に行いました。「グラフ ゴルフ2019」は、スパコンなどで使われている複雑なネットワーク構成をスイッチ間の接続関係を表す簡単なグラフにおきかえ、CPUチップ内およびCPUチップ間のネットワークの効率的な設計につながる構成のグラフの発見を競うコンペです。今回は、優れたグラフを発見した中尾 昌広（理化学研究所計算科学研究センター）、酒井 真章(関西大学)、花田 良子（関西大学）のチーム、寺尾 創(電気通信大学)の個人1名を表彰しました。これらのグラフは、次世代のスパコンの超並列計算の通信時間の最小化など、実用への応用が期待されます。
最近のコンピューターは大規模で複雑になってきており、スパコンでは最大で1千万以上のプロセッサーコアが相互に接続されています。膨大な数のコアをいかに効率的に相互接続するかというネットワーク構成（ネットワークトポロジー）の設計は、スパコンの処理能力に大きく影響します。本コンペでは、コアを「頂点」、コアとコアをつなぐ配線を「辺」とみなし、ネットワークトポロジーを達成するグラフを構成しました。一つの頂点から最も離れた頂点までのホップ数（経由した辺数）を「直径」、各頂点間のホップ数の平均値を「平均パス長」と呼び、指定された条件で直径と平均パス長が最も小さいグラフを発見することを問題として設定しました(図参照)。
〈図〉頂点数が「16」、各頂点からの辺の数が「4」で構成されたグラフの例。直径、平均パス長ともに最も小さい左端のグラフが最も優れていることになる。
この問題の定義は簡単ですが、解くのは困難です。グラフの変化に対する直径の変化は不規則であり、膨大な数のグラフから最適なグラフを効率的に求める方法は知られていません。例えば、12個の頂点と36本の辺で構成される極めて小さいグラフですら、3兆個近いグラフ数があるため、その中から単純な探索によって最適なグラフを発見することは絶望的です。
そこで、過去4回のコンペの各表彰者の方々の全面的なご協力により、グラフゴルフに関連した国際会議等のイベントでの発表資料をホームページ(http://research.nii.ac.jp/graphgolf/2019/candar19/) 上にて公開することで、様々な優れたグラフの構成方法を分かりやすく解説しています。また、グラフゴルフに関連する学術論文や技術報告計22本のリストを同ホームページ上に掲載し、今後のグラフ発見の参考となるようにしました。
第5回となる本コンペは4月～10月に実施し（*3）、国内外から1,382件(前回比5倍以上)と多数の有効応募がありました。その結果、平均パス長の計算が困難である頂点数100万の巨大グラフを含む一般グラフの出題5問および、格子グラフの全出題11問において、理論上最小の直径を有するグラフを発見する成果が得られました。また、表彰者の中尾らのチームは格子グラフの11出題、寺尾は一般グラフの5出題において、各々平均パス長が最も小さいグラフを発見しました。実用上、グラフの直径の削減はスパコンの最長通信遅延の削減、グラフの平均パス長の削減はスパコンの平均通信遅延の削減に直結します。
スパコンは日進月歩であり、スパコンに求められるネットワーク構成も変わっていきます。実際に、上位500台のスパコン（*4）のうち、約8割のスパコンでは任意のネットワーク構成を実装することができるInfiniBandやイーサネットを採用しており、優れたグラフをネットワーク構成として採用することが技術的に可能です。本コンペは問題の条件設定を変えて今後も継続することで学術界や産業界に貢献していきます。（文中敬称略）
（*1）「グラフ ゴルフ」：専門家以外にもコンペを身近に感じてもらい、より多くの方の参加につなげるため、信号がコアを一つひとつ経由して流れていく様を、ショットを一打ずつ積み重ねて最少打数を競うゴルフになぞらえて命名。コンペの結果はhttp://research.nii.ac.jp/graphgolf/ranking.html。
（*2）「CANDAR2019」：コンピューターシステムとネットワーク技術に関する国際シンポジウム（http://is-candar.org/）。
（*3）2019年4月26日付ニュースリリース「100万個のCPUを効率的に接続するグラフの発見者求む！～未来スパコンのネットワーク構成を発見するコンペ 「グラフ ゴルフ2019」を今年も開催～」（https://www.nii.ac.jp/news/release/2019/0426.html）参照。
（*4）「TOP500」: スーパーコンピュータのランキングに関するプロジェクト (https://www.top500.org/)。 2019年6月時点のランキングによる。
