スパコン内CPUコアの効率的な接続へ、より単純なネットワークトポロジー図を競うコンペ「グラフゴルフ」、NIIが開催

　大学共同利用機関法人情報システム研究機構国立情報学研究所（NII）は、スーパーコンピューター内のプロセッサコアの効率的な相互接続に置き換え可能な、より単純な構成のグラフの発見を競うコンペティション「グラフゴルフ」への応募受付を開始した。期間は9月24日まで。

　数百万のプロセッサコアが相互に接続されるスパコンでは、膨大な数のコアを効率的に相互接続するネットワークトポロジーの設計が、処理能力に大きく影響する。

　グラフゴルフでは、コアを「頂点」、コア間の配線を「辺」とみなし、ネットワークトポロジーをモデル化したグラフを募集する。1つの頂点から最も離れた頂点までに経由した頂点と終点の合計数である「ホップ数」を「直径（Diameter）」、各頂点間のホップ数の平均値を「平均パス長（ASPL：Average Shortest Path Length）」と呼び、指定された条件で直径と平均パス長が最も小さいグラフを発見することが問われる。

　第3回となる今回の開催部門は、頂点数が32～100000、辺の数が10～64の条件を組み合わせた10パターンを募集する「一般グラフ部門」と、頂点数が16～10000、辺の数が3～28、最大辺長が2～33の条件を組み合わせた19パターンを募集する「格子グラフ部門」。後者は今回新設された。

頂点数16、辺の数が4で構成されたグラフの例。直径と平均パス長がより小さい左のグラフが優れたものとなる

　成果は、通信遅延削減を重視するスパコンなどのチップにおけるネットワークトポロジー設計への直接的な利用が期待されている。応募案は6月26日以降に毎週公開されるため、応募したグラフの順位を確認できる。また、コンペは今後も継続予定で、グラフのカタログを「Graph Bank」のデータベースに蓄積していくという。優れたグラフの発見者は、11月に青森市で開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2017」で表彰される。

　なお、グラフゴルフの名称は、信号がコア1つ1つを経由して流れていく様子を、ショットを1打ずつ積み重ねて最小打数を競うゴルフになぞらえて命名したという。