スパコンのCPUネットワーク単純化を試みる“グラフ ゴルフ”コンペが開催

頂点数が「16」、各頂点からの辺の数が「4」で構成されたグラフの例。直径、平均パス長ともにもっとも小さい左端のグラフがもっとも優れていることになる

　大学共同利用機関法人 情報・システム研究機構 国立情報学研究所(NII)は5月16日、効率的な構成のグラフ発見を競うコンペティション「グラフ ゴルフ」を開催した。特設サイトにて募集しており、応募期間は10月14日まで。

　グラフ ゴルフは、2015年より毎年開催され、今年(2018年)で4回目となる。スーパーコンピュータなどで使われている複雑なネットワーク構成を簡単に置き換えるというもので、CPUチップ内およびCPUチップ間ネットワークの効率的な設計につながるような単純なグラフを見つけるのが目的。

　コアを「頂点」、コアとコアをつなぐ配線を「辺」とみなしたグラフとして、ネットワークトポロジーをモデル化。1つの頂点からもっとも離れた頂点までのホップ数(経由した頂点＋終点の頂点の合計数)を「直径」、各頂点間のホップ数の平均値を「平均パス長」とし、指定された条件で直径と平均パス長がもっとも小さいグラフを発見しなければならない。

　コンペでは「一般グラフ部門」と「格子グラフ部門」を設置。なお、最近の高性能プロセッサは正方形ではなく長方形となっているため、今年から格子グラフ部門の出題が長方形に変更された。

　それぞれの条件は以下のようになっている。

• 一般グラフ部門
  最新のスパコンのネットワーク構成のグラフ。頂点数「72」〜「400,000」と頂点からの辺の数「4」～「64」の条件を組み合わせた14パターン
  
• 格子グラフ部門
  2次元平面上に頂点と辺があるグリッドグラフ。頂点数「64」〜「1,024」、頂点からの辺の数「4」、最大辺長「3」〜「24」の条件を組み合わせた10パターン

　優勝者は11月に岐阜県高山市で開催される国際シンポジウム「CANDAR2018」にて表彰される。