ニュース / News

ニュースリリース

100万個のCPUを効率的に接続するグラフの発見者求む!
~未来スパコンのネットワーク構成を発見するコンペ 「グラフ ゴルフ2019」を今年も開催~

 大学共同利用機関法人 情報・システム研究機構 国立情報学研究所(NII、所長:喜連川 優、東京都千代田区)は、スーパーコンピューター(スパコン)などで使われている複雑なネットワーク構成を簡単なグラフにおきかえ、CPUチップ内およびCPUチップ間のネットワークの効率的な設計につながるような単純な構成のグラフの発見を競うコンペティション「グラフ ゴルフ(*1)2019」を開催します。

 今年度は100万の頂点数を持つ「巨大グラフ」を新たに出題し、4月29日から10月14日まで専用ウェブサイト(http://research.nii.ac.jp/graphgolf)で応募を受け付けます。優れたグラフの発見者は11月に長崎県長崎市で開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2019」(*2)で表彰します。「グラフ ゴルフ」は2015年度(平成27年度)から毎年開催し、今回が5回目となります。

 最近のコンピューターは大規模で複雑になってきており、スパコンでは数百万のプロセッサーコアが相互に接続されています。膨大な数のコアをいかに効率的に相互接続するかというネットワーク構成(ネットワークトポロジー)の設計は、スパコンの処理能力に大きく影響します。本コンペでは、コアを「頂点」、コアとコアをつなぐ配線を「辺」とみなし、ネットワークトポロジーを表現するグラフを構成します。一つの頂点から最も離れた頂点までのホップ数(経由した辺数)を「直径」、各頂点間のホップ数の平均値を「平均パス長」と呼び、指定された条件で直径と平均パス長が最も小さいグラフを発見することを問題として設定しています(図参照)。

nii_newsrelease_20190426_image1.png

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

 本コンペでは、グラフ生成のサンプルプログラムや過去の表彰者の発表資料を公開しています。そのため、グラフ問題の専門家ではない研究者や大学生でも、それらの資料を参考にしてコンペにチャレンジできるのが特徴です。また、参加者の応募案は7月23日以降毎週公開(*3)され、週ごとにランキングが表示されます。専用サイトでは、応募案の中で最も優れたグラフや自分が応募したグラフの順位も確認でき、ゲーム感覚でコンペを楽しむことができます。

 本コンペでは「一般グラフ部門」と「格子グラフ部門」を設置し、これまでに900件を超える応募(*4)がありました。スパコンは日進月歩であり、スパコンに求められるネットワーク構成も変わってきています。そのため、「グラフ ゴルフ」では次世代のスパコンの技術トレンドを毎年想定してグラフの出題をしています。今年は、将来に登場するであろうエクサスケール級(1秒間に1018回以上の浮動小数点演算が可能) のスパコンの構成(*5)を想定して、100万の頂点数を持つ「巨大グラフ」を新たに出題しました。昨年度よりも高度な問題ですが、巨大グラフのホップ数を高速に計算する並列プログラムが参加者のご厚意により提供されたため、この巨大グラフの問題にも気軽に挑戦できるコンペになっています。

 「グラフ ゴルフ」の成果は、通信遅延を削減することを重視する最近のスパコンや計算機プロセッサーチップのネットワークトポロジー設計への直接的な利用が期待されています。本コンペは今後も継続する予定で、優れたグラフを蓄積していくことで学術界や産業界に貢献していきます。

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

応募受付  2019年4月29日(月)~10月14日(月)

ウェブサイト http://research.nii.ac.jp/graphgolf

表彰式 2019年11月26日(火)~29日(金)に開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2019」(長崎県長崎市)で実施

一般グラフ部門

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

条件設定
頂点数「50」〜「1,000,000」、頂点からの辺の数「4」~「32」の条件を組み合わせた11パターン

格子グラフ部門

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

条件設定
頂点数「25」〜「10,000」、頂点からの辺の数「4」〜「8」、最大辺長「2」〜「4」の条件を組み合わせた11パターン

関連リンク

グラフ ゴルフ2019

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

100万個のCPUを効率的に接続するグラフの発見者求む!
~未来スパコンのネットワーク構成を発見するコンペ 「グラフ ゴルフ2019」を今年も開催~


(*1) グラフ ゴルフ: 専門家以外にもコンペを身近に感じてもらい、より多くの方の参加につなげるため、信号がコアを一つひとつ経由して流れていく様を、ショットを一打ずつ積み重ねて最少打数を競うゴルフになぞらえて命名。
(*2) CANDAR2019: コンピューターシステムとネットワーク技術に関する国際シンポジウム。http://is-candar.org/を参照。
(*3) 7月22日以降は毎週公開: 7月22日までの応募案はすべて7月23日に公開。同じ内容の提案があった場合、順位は公開順とする。
(*4) 900件を超える応募: 2015年=284件、2016年=131件、2017年=269件、2018年=239件
(*5) エクサスケール級のスパコン: 「HPCI 技術ロードマップ白書」におけるエクサスケールシステム構成例に基づいて想定した。http://open-supercomputer.org/wp-content/uploads/2012/03/hpci-roadmap.pdfを参照。
(*6) 最新のスパコン: スパコンの性能ランキング「TOP500」(https://www.top500.org/)の2018年11月時点の上位10台の一部のスパコンの仕様から設定。
3729

注目コンテンツ / SPECIAL