通信遅延の⼤幅な低下などの実⽤に期待
〜効率的なスパコン設計につながるグラフ発⾒を競うコンペ「グラフ ゴルフ」で〜

　国⽴情報学研究所（NII）は11⽉27⽇、複雑なネットワーク構成をスイッチ間の接続関係を表す簡単なグラフに抽象化し、より単純な構成のグラフの発⾒を競うコンペティション「グラフゴルフ」で優れたグラフを発⾒した３名の個⼈と１チームを、岐⾩県⾼⼭市で開催された国際シンポジウム 「CANDAR2018」で表彰した。

　これらのグラフは、効率的なプロセッサーコア間の通信や、スーパーコンピューター（スパコン）の超並列計算の最⻑通信時間の最⼩化、次世代のスパコン設計の通信遅延の低下など、性能向上への応⽤が期待される。また今回、表彰者の⼀⼈である北須賀 輝明が発⾒した4つのグラフが、グラフ理論分野において著名な問題とされてきた次数直径問題の最⼤グラフの記録更新になるという新たな展開が⽣まれ、グラフに関する理論分野にも貢献している。

　最近のコンピュータは⼤規模で複雑になってきており、特にスパコンでは1千万以上のプロセッサ ーコア（以降、コアと表記）が接続されるものも登場している。しかし、⼀つのコアに直接接続できるコアには制限があることから、コア間のネットワーク構成を⼯夫して膨⼤な数のコアを効率的に相互接続することが、スパコンの処理能⼒に⼤きく影響する。同コンペでは、スパコンの専⾨家でなくても参加ができるように、実際のスパコンのネットワークを抽象化した数学的なグラフに置き換えて、効率的なネットワーク構成の発⾒を競った。
　具体的にはコアに直結しているスイッチを「頂点」、コアとコアをつなぐ配線を「辺」とみなしたグラフとして、ネットワーク構成をモデル化した。実際のスパコンのネットワーク設計では、スイッチあたりの接続コア数、ルーティング、スイッチング⽅式をはじめとする多くの検討項⽬があり、同モデルから対象ネットワーク構成の最短経路利⽤時のすべてのスイッチ間の通信遅延を⾒積ることができる。そして、問題設定で指定された頂点数と「次数」（⼀つの頂点から出る辺の数）で構成されるグラフの中で、⼀つの頂点から最も離れた頂点までの「ホップ数」（経路上の辺の数）および各頂点間のホップ数の平均値が最も⼩さいグラフの発⾒を競った。このようなグラフをコンピュータで発⾒する単純な⽅法は、計算ツールを⽤いてすべてを列挙することだが、例えば、頂点数12、次数4のグラフは4,800億個もあり、現在の計算機の性能ではこれ以上⼤きな頂点数を扱うことは困難だ。
　第4回となる同コンペは5⽉〜10⽉に実施し、国内外から239件の有効応募があった。その結果、優れたグラフを発⾒した中尾 昌広氏（理化学研究所計算科学研究センター）、⼩泉 透氏（東京⼤学）、EvbCFfp1XB氏（ユーザ名）の個⼈3名と、北須賀 輝明氏（広島⼤学）と飯⽥ 全広氏（熊本⼤学）との連合チームを表彰した。（1）頂点数72、次数4の理想のグラフ、（2）最も離れた頂点までのホップ数を最⼩にした頂点数3,019、次数30のグラフ、（3）平均ホップ数が理論限界に迫る頂点数40万の巨⼤グラフなど、実⽤上重要な発⾒が得られた。
　それぞれの特徴は以下の通り。

• 実際のプロセッサーチップ（それぞれが72コア搭載）の内部ネットワークを模したグラフ構成を出題し、各コアを頂点（72頂点）として、直径4、平均ホップ数3未満で効率的に接続できることが分かった(図)。同グラフはチップ上にレイアウトした時に⼀部の配線が⻑くなる場合があるが、先⾏研究成果から性能劣化なしでネットワークを動作させる技術があるため、効率的なプロセッサーコア間の接続が実装可能であるといえる。
• 実際のスパコンのネットワークを模した問題を出題し、最⻑ホップ数を最⼩にするネットワーク設計が可能であることが分かった。スパコンの超並列計算のボトルネックとなることが多い最⻑通信時間を最⼩化できる可能性がある。
• 次世代のスパコン設計は10万ノード以上（1ノードあたり100 プロセッサコア以上）が想定されるため、同コンペでは初めて40万ノードのネットワーク構成を出題した。今回の成果は、通信遅延を⼤幅に低下させることが期待できる巨⼤ネットワーク構成の解の⼀つを⽰した点で有益といえる。

　これらのグラフは、効率的なプロセッサーコア間の通信や、スパコンの超並列計算の最⻑通信時間の最⼩化、スパコン設計の通信遅延の低下など、実⽤への応⽤が期待される。また今回、表彰者の北須賀 輝明氏が発⾒した4つのグラフが、グラフ理論分野の著名な問題である次数直径問題の最⼤グラフの記録更新になるという新たな展開が⽣まれ、理論分野の活性化にも貢献していく。
　同研究所は「過去3回のコンペの各表彰者の⽅々の全⾯的なご協⼒により、グラフゴルフに関連した国内外のイベントでの発表資料をホームページ上にて公開することで、様々な優れたグラフの構成⽅法を分かりやすく解説している」としており、「“グラフ ゴルフ”の成果は、通信遅延を削減することを重視する最近のスパコンや計算機プロセッサチップのネットワーク構成の設計への直接的な利⽤が期待されている。本コンペは問題の条件設定を変えて今後も継続する予定で、グラフ（ネットワーク構成）のカタログを“Graph Bank”に蓄積していくことで学術界や産業界に貢献していく」とコメントを出している。