NII、効率的なスパコン設計につながるグラフを16パターン発見

問題と回答例

　大学共同利用機関法人 情報・システム研究機構 国立情報学研究所(NII)は26日、スーパーコンピュータ(スパコン)の効率的なネットワークを発見するコンペティション「グラフ ゴルフ2019」の表彰式を実施した。

　このなかで、優れたグラフを発見した理化学研究所計算科学研究センターの中尾昌広氏、関西大学の酒井真章氏および花田良子氏のチーム、電気通信大学の寺尾創氏を表彰した。

　スパコンでは最大1,000万以上のプロセッサコアを相互接続しているが、この膨大な数のコアをいかに効率的なネットワークトポロジーで相互接続するかが課題となっている。

　グラフ ゴルフ2019では、コアを「頂点」、そのあいだをつなぐ配線を「辺」とみなし、ネットワークトポロジーを達成するグラフを構成。1つの頂点からもっとも離れた頂点までのホップ数(経由する辺の数)を「直径」、各頂点間のホップ数の平均値を「平均パス長」と呼び、指定された条件において、この直径と平均パス長がもっとも小さいグラフを発見することを問題として設定している。

　スパコンに置き換えると、直径の削減は最長通信遅延の削減、平均パス長の削減は平均通信遅延の削減に関係する。スパコンの約8割が採用しているInfiniBandやEthernetでは自由にネットワークを構築できるため、優れたグラフをネットワーク構成として採用すれば処理能力の向上につながる。

　この問題の定義自体は簡単だが、グラフの変化に対する直径の変化は不規則であり、最適なグラフを効率的に求める方法がないため、解くのは困難である。たとえば12個の頂点と36本の辺で構成されるきわめて小さなグラフでも3兆個近いグラフ数があるという。

　NIIがコンペを4月から10月まで実施したところ、国内外から1,382件以上の有効応募があった。その結果、平均パス長の計算が困難な、頂点数100万の巨大グラフを含む一般グラフの出題5問、および格子グラフの全出題11問において、理論上最小の直径を有するグラフ16パターンを発見できた。

　また、中尾氏らのチームは格子グラフの11出題、寺尾氏は一般グラフの5出題において、平均パス長がもっとも小さいグラフを発見した。

　NIIでは今後、問題の条件設計を変えてコンペを継続し、学術界や産業界に貢献していく。