ニュース / News

ニュースリリース

効率的なネットワーク構成を示すグラフ発見を競うコンペを今年も開催/スパコン内のCPU、あなたならどう接続しますか?

効率的なネットワーク構成を示すグラフ発見を競うコンペを今年も開催
スパコン内のCPU、あなたならどう接続しますか?
~新たに40万頂点数の巨大グラフを出題~

大学共同利用機関法人 情報・システム研究機構 国立情報学研究所(NII、所長:喜連川 優、東京都千代田区)は、スーパーコンピューター(スパコン)などで使われている複雑なネットワーク構成を簡単なグラフ(*1) におきかえ、CPUチップ内およびCPUチップ間のネットワークの効率的な設計につながるような単純な構成のグラフの発見を競うコンペティション「グラフ ゴルフ」(*2) を開催します。応募は、10月14日まで専用ウェブサイトで受け付けます。優れたグラフの発見者は11月に岐阜県高山市で開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2018」(*3) で表彰します。「グラフ ゴルフ」は2015年度(平成27年度)から毎年開催し、今回が4回目となります。

最近のコンピューターは大規模で複雑になってきており、スパコンでは数百万のプロセッサーコアが相互に接続されています。膨大な数のコアをいかに効率的に相互接続するかというネットワーク構成(ネットワークトポロジー)の設計は、スパコンの処理能力に大きく影響します。

本コンペでは、コアを「頂点」、コアとコアをつなぐ配線を「辺」とみなしたグラフとして、ネットワークトポロジーをモデル化しました。一つの頂点から最も離れた頂点までのホップ数(経由した頂点+終点の頂点の合計数)を「直径」、各頂点間のホップ数の平均値を「平均パス長」と呼び、指定された条件で直径と平均パス長が最も小さいグラフを発見することが問題です(図参照)。

img_graphgolf_2018_800.png

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

本コンペは、グラフ生成のサンプルプログラムや過去の表彰者の発表資料が公開されているため気軽に参加できます。参加者の応募案は7月23日以降毎週公開(*4) され、週ごとにランキングが表示されます。専用サイトでは、応募案の中で最も優れたグラフや自分が応募したグラフの順位も確認でき、ゲーム感覚でコンペを楽しむことができます。

本コンペでは「一般グラフ部門」と「格子グラフ部門」を設置し、これまでに600件を超える応募(*5) がありました。最近の高性能プロセッサーチップは正方形ではなく長方形のため、そのチップ内ネットワークも長方形内に配線されます。

そこで、今年の「格子グラフ部門」では出題を長方形に変更し、より現実的な内容としました。また、40万の頂点数を持つ「巨大グラフ」も新たに出題しています。

「グラフ ゴルフ」の成果は、通信遅延を削減することを重視する最近のスパコンや計算機プロセッサーチップのネットワークトポロジー設計への直接的な利用が期待されています。

本コンペは今後も継続する予定で、グラフ(ネットワークトポロジー)のカタログを「Graph Bank」(*6) に蓄積していくことで学術界や産業界に貢献していきます。

「グラフ ゴルフ」開催概要

応募受付: 5月16日(水)~10月14日(日)
ウェブサイト: http://research.nii.ac.jp/graphgolf
表彰式: 11月27日(火)~30日(金)に開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2018」(岐阜県高山市)にて表彰式とワークショップを行う。

一般グラフ部門

最新のスパコン(*7) のネットワーク構成のグラフ。現在のスパコンに対して、ホップ数の観点からどれ位効率的なネットワークが構成できるかという挑戦といえます。

条件設定
頂点数「72」〜「400,000」と頂点からの辺の数「4」~「64」の条件を組み合わせた14パターン

格子グラフ部門

2次元平面上に頂点と辺があるグリッドグラフ。頂点が格子状に並んでおり、かつ、平面上の辺長に制約があります。マシンルーム内のケーブル長に実装上の制約がある場合のコンピューターシステムを模しています。

条件設定
頂点数「64」〜「1,024」、頂点からの辺の数「4」、最大辺長「3」〜「24」の条件を組み合わせた10パターン

ニュースリリース(PDF版)

効率的なネットワーク構成を示すグラフ発見を競うコンペを今年も開催/スパコン内のCPU、あなたならどう接続しますか? ~新たに40万頂点数の巨大グラフを出題~


  • (*1)グラフ:「頂点」と頂点間の連結関係を表す「辺」の集合で構成される型のこと。
  • (*2)「グラフ ゴルフ」:専門家以外にもコンペを身近に感じてもらい、より多くの方の参加につなげるため、信号がコアを一つひとつ経由して流れていく様を、ショットを一打ずつ積み重ねて最少打数を競うゴルフになぞらえて命名。
  • (*3)「CANDAR2018」:コンピューターシステムとネットワーク技術に関する国際シンポジウム。
  • (*4)「7月23日以降は毎週公開」:7月22日までの応募案はすべて7月23日に公開。同じ内容の提案があった場合、順位は公開順とする。
  • (*5)「600件を超える応募」:2015年=284件、2016年=131件、2017年=269件
  • (*6)「Graph Bank」:様々なグラフの構成情報や、直径、平均パス長などの特徴を蓄積したデータベース。
  • (*7)「最新のスパコン」:スパコンの性能ランキング「TOP500」の2017年11月時点の上位10台の一部、および今後上位ランク入りが予想されるスパコンの仕様から設定。
3370

注目コンテンツ / SPECIAL