「夏の電脳甲子園」SupercomputingContest2016の本選結果について
第22回スーパーコンピューティングコンテストを8月22日から26日の5日間、大阪会場と東京会場に分かれて開催しました。予選参加校27校35チームの上位20チームが熱き知的な戦いを繰り広げました。
今年は、東京工業大学のスーパーコンピュータTSUBAME2.5を使用しました。本選課題「でっかい小さなグラフ設計問題」では与えられた「グラフ条件」を満たすグラフの中で総最短経路長ASPLの小さなグラフの設計をいかに高速に実行するかを競いました。
【本選課題】
問題の背景:グラフの最短経路長は、非常に多くの分野で使われているが、この課題では、総最短経路長(すべての頂点間の最短経路の総和)が最小となるグラフを設計する問題を考える。与えられた頂点数n次数d対し、その頂点数と次数を持つ正則グラフのうちで総最短経路長が最小となるグラフを求めよ、というのが今回の課題である。
この課題自身もいろいろな応用が考えられるが、とくにスーパーコンピュータ(スパコン)のネットワーク配線でも重要な意味を持つ問題である。現代のスパコンの多くは、非常に多数の演算装置(計算ノードという)が並列に動くことで高速化を達成している。こうした計算ノード群は高速なデータ交換をしなければならない。そのため、計算ノードは高速ネットワークでつながれている。けれども、各計算ノードから出すことのできる線(つまり次数)の数は限られている。すべての計算ノードは、他の計算ノードを中継して、目的の計算ノードにデータを送ることができるが、そうした転送距離が短い方が望ましい。その設計に、小さいグラフ(つまり、総最短経路長が小さいグラフ)が必要になってくるのである。
小さなグラフ構成問題：入力として与えられる以下のグラフの条件パラメータに対し、最短経路長(ASPL)が最小となる単純正則無向グラフを求めよ。
・グラフ条件
頂点数： n 次数：d 色数： C
各色で塗られる頂点数： n0; . . . ; nC－1
色間の距離：(wi, j) (ただし、＜i、＜C－1)
注意：同じASPLを持つグラフは複数存在するが、そのうちの1つを答えればよい。
【本選結果】
8月26日に表彰式を行い、上位3チームに表彰状とメダルが授与されました。
優勝
GhostDiv 久留米工業高等専門学校
準優勝
KISS 慶應義塾高等学校
３位
kingyo 奈良工業高等専門学校
下條センター長 開会式での挨拶
森原副センター長 表彰式での挨拶
優勝チーム（GhostDiv）
大阪会場（豊中教育研究棟）
東京会場（東京工業大学 蔵前会館）
公開日：2016年09月06日
カテゴリー：一般の方
