ニュース / News

2017/11/22

優れたグラフを発見した応募者を表彰／効率的なスパコン設計につながるグラフ発見を競うコンペ「グラフ ゴルフ」

大学共同利用機関法人 情報・システム研究機構 国立情報学研究所（NII、所長：喜連川 優、東京都千代田区）は、スーパーコンピューター（スパコン）などで使われる複雑なネットワーク構成をグラフに置き換えてより単純な構成のグラフの発見を競うコンペティション「グラフ ゴルフ」で優れたグラフを発見した松崎 貴之・飯田 全広（ともに熊本大学）・北須賀 輝明（広島大学）のチームと、川又 生吹（東北大学）、森 立平（東京工業大学）の2名を、本日11月22日、青森市で開催されていたコンピューターシステムとネットワーク技術に関する国際シンポジウム「CANDAR 2017」で表彰しました。（文中敬称略）

最近のコンピューターは大規模で複雑になってきており、スパコンでは数百万のプロセッサーコアが相互に接続されています。膨大な数のコアを相互接続するネットワーク構成（ネットワークトポロジー）の設計は、スパコンの処理能力に大きく影響します。「グラフ ゴルフ」（*1）は、このネットワークトポロジーのコアを「頂点」、コアとコアをつなぐ配線を「辺」とみなしたグラフとしてモデル化し、指定された頂点数と「次数」（一つの頂点から出る辺の数）で構成されるグラフの中で、一つの頂点から最も離れた頂点までの「ホップ数」（経路上の辺の数）、および、各頂点間のホップ数の平均値が最も小さいグラフの発見を競います。

第3回となる今年度のコンペは、平面上の辺長に制約のある格子グラフ部門を新設し、現在のスパコンにおいてホップ数の観点からどれ位効率的なネットワークが構成できるかを競う一般グラフ部門と計2部門で競いました。コンペは3月～9月に実施し、国内外より269件の有効応募がありました。その結果、以下のような実用上重要なグラフの発見がありました。

1. スーパーコンピューターの性能ランキング「TOP500」の2016年11月版で世界5位だった米クレイ社「Cori」のネットワークトポロジーに応用した場合、それ以上ホップ数を削減することができない理論限界（*2）を満たすホップ数「2」のネットワークを構成できるグラフ
2. 本コンペでは2016年11月版の「TOP500」のトップテン中6台のスパコンのネットワーク構成をグラフとしてモデル化して出題しており、その6台のいずれにおいてもホップ数「2」〜「7」と極めて効率的なネットワークを構成できるグラフ（上述の①を含む）

「グラフ ゴルフ」のサイトでは、過去3回の表彰者の方々のご協力を得て本コンペに関連した国内外のイベントでの発表資料を公開し、さまざまな優れたグラフの構成方法を分かりやすく解説しています。

NIIでは来年度以降も問題の条件設定を変えて本コンペを継続し、グラフ（ネットワークトポロジー）のカタログを更新して情報発信していくことで、学術界や産業界に貢献していきます。

ニュースリリース

---

（*1）「グラフ ゴルフ」：　専門家以外にもコンペを身近に感じてもらい、より多くの方の参加につなげるため、信号がコアを一つひとつ経由して流れていく様を、一打ずつショットを積み重ねて最少打数を競うゴルフになぞらえて命名。昨年度の結果
（*2）「理論限界」：　ある頂点からnホップで到達可能な頂点の数は次数のn乗に比例する。この事実から求めた最大ホップ数の下限値を理論限界（Moore Bound）と呼ぶ。Moore Boundを満たす理想的なグラフはほとんど発見されていない。