ニュース / News

ニュースリリース

より具体的な条件設定のホスト-スイッチグラフ部門を新設!
未来スパコンのネットワーク構成を発見するコンペ 「グラフ ゴルフ」を復活して開催

 大学共同利用機関法人 情報・システム研究機構 国立情報学研究所(NIIエヌアイアイ、所長:喜連川 優、東京都千代田区)は、スーパーコンピューター(スパコン)などで使われている複雑なネットワーク構成を簡単なグラフにおきかえ、CPUチップ内およびCPUチップ間のネットワークの効率的な設計につながる構成のグラフの発見を競うコンペティション「グラフ ゴルフ2021」(*1)を開催します。今年度は、より具体的な条件設定のホスト-スイッチグラフ部門を新設し、4月27日から10月11日まで専用ウェブサイト(http://research.nii.ac.jp/graphgolf)で応募を受け付けます。優れたグラフの発見者は11月に島根県松江市で開催予定のコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2021」(*2)で表彰します。「グラフ ゴルフ」は2015年度(平成27年度)から2020年を除く各年にて開催し、今回が6回目となります。

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

nii_newsrelease_20210427_image1.png

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

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

 本コンペではこれまでに2,300件を超える応募(*4)がありました。スパコンは日進月歩であり、スパコンに求められるネットワーク構成も変わってきています。そのため、「グラフ ゴルフ」では次世代のスパコンの技術トレンドを毎年想定してグラフの出題をしています。最近のスパコンではネットワークスイッチ(*5)を用いてCPU間を間接的に接続することが多くなっています。その構成を表現するため、グラフの頂点をホスト(CPU)頂点とスイッチ頂点に区別するホスト-スイッチグラフ部門を新設し、従来の一般グラフ部門と併せて2部門で出題します。このホスト-スイッチグラフ部門は、一般グラフ部門と比べて高度な技術が必要です。そこでその対応として、ホスト-スイッチグラフを生成できるサンプルプログラムと、任意のホスト-スイッチグラフのホップ数を計算するサンプルプログラムを主催者側から提供し、従来どおり気軽に挑戦できるコンペとなるようにしました。

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

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

応募受付 2021年4月27日(火)~10月11日(月)
ウェブサイト http://research.nii.ac.jp/graphgolf
表彰式 2021年11月23日(火)~26日(金)に開催されるコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR2021」(島根県松江市予定)で実施

開催部門

条件設定

一般グラフ部門

現在、あるいは将来のスパコンに対して、ホップ数の観点からどれ位効率的なネットワークが構成できるかという挑戦といえます。

頂点数「40」〜「100,000」、頂点からの辺の数「5」~「128」の条件を組み合わせた8パターン

ホスト-スイッチグラフ部門

ホスト頂点間のホップ数を小さくすることを競います。使用するスイッチ頂点数に制限がないことから工夫する余地がより大きいといえます。

ホスト頂点数「32」〜「65,536」、スイッチ頂点からの辺の数「4」〜「100」の条件を組み合わせた13パターン

関連リンク

グラフ ゴルフ2021

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

より具体的な条件設定のホスト-スイッチグラフ部門を新設!
未来スパコンのネットワーク構成を発見するコンペ 「グラフ ゴルフ」を復活して開催


(*1) グラフ ゴルフ: 専門家以外にもコンペを身近に感じてもらい、より多くの方の参加につなげるため、信号がコアを一つひとつ経由して流れていく様を、ショットを一打ずつ積み重ねて最少打数を競うゴルフになぞらえて命名。
(*2) CANDAR2021: コンピューターシステムとネットワーク技術に関する国際シンポジウム。http://is-candar.org/を参照。
(*3) 7月26日以降は毎週公開: 7月26日までの応募案はすべて7月27日に公開。同じ内容の提案があった場合、順位は公開順とする。
(*4) 2,300件を超える応募: 2015年=284件、2016年=131件、2017年=269件、2018年=239件、2019年=1,382件
(*5) ネットワークスイッチ: 機器間でやりとりするデータの中継および転送を行う集線装置。
4891

注目コンテンツ / SPECIAL