FIT2016 第15回情報科学技術フォーラム 開催日:2016年9月7日(水)~9日(金) 会場:富山大学キャンパス
イベント企画
小直径グラフの追究 ~グラフ理論の未解決問題とインターコネクトの未来~
9月9日(金) 9:30-12:00
第3イベント会場(共通教育棟A棟2階A23)
【セッション概要】 グラフ理論上の未解決問題と言えるorder/degree問題(ODP)への挑戦の軌跡を紹介し、その解に基づく計算機インターコネクト(相互結合網)の新たな設計法を展望する。ODPは、与えられたノード数・次数をもつグラフの中で、直径・平均距離が最小のものを求める問題である。大規模かつ低遅延な相互結合網の設計に役立つが、これまでグラフ理論家の関心を得られず研究が進んでいなかった。本イベントでは、昨年開催されたODPのコンペ「Graph Golf」の受賞者3チームを招待する。小直径グラフ探索/構築に関する知見を参加者と共有し、議論を深める機会としたい。
司会:藤原 一毅(国立情報学研究所 アーキテクチャ科学研究系 特任准教授)
【略歴】 2002年東京工業大学工学部制御システム工学科卒。2004年同大学院理工学研究科機械制御システム専攻修了。同年~2008年まで日立製作所情報制御システム事業部。2012年総合研究大学院大学複合科学研究科情報学専攻博士後期課程修了。博士(情報学)。現在、国立情報学研究所アーキテクチャ科学研究系特任准教授。高性能計算システムの相互結合網に関する研究に従事。2015年情報処理学会山下記念研究賞。
9:30-10:10 講演(1) 既知のグラフを用いた小直径グラフの構成
水野 良祐(京都大学 大学院理学研究科物理学・宇宙物理学専攻物理第二分野天体核研究室 学生)
【概要】 多くのノード同士を互いに接続する場合、その通信の遅延が最小になるようなネットワーク構造を一般的に求める方法は、現在のところ知られていない。一方で、厳密な最小ではないが、比較的遅延が小さくなる密なネットワーク構造を求める方法はいくつも知られており、実際にそれらを用いて準最適なネットワークの設計が試みられている。今回我々は、その中でも特に、グラフ理論の手法を用いることで準最適なネットワークを構成する基本的な方法をいくつか紹介する。その上で、「Graph Golf」において我々が作成したノード数256、次数22のグラフの具体的な構成方法を紹介する。
【略歴】 京都大学大学院理学研究科物理学・宇宙物理学専攻修士課程修了後、同博士課程進学。現在、同博士課程在学中。
10:10-10:50 講演(2) グラフゴルフのはじめ方 - 手書きグラフから経験的手法によるグラフ生成まで
北須賀 輝明(熊本大学 大学院先端科学研究部環境科学部門 准教授)
【概要】 多数の節点と枝で構成されるグラフはグラフ理論の専門家でなくとも理解できる。手に負える数の節点数と枝数であればグラフを手書し、本コンペで競う直径と平均距離(節点対間の最短経路長の平均)の最小化も難しいことではなく、グラフ理論の例題の一つとして楽しめるものである。本講演では、手書きしたグラフを分析する過程や、節点数が256から10000のグラフに対して我々が採用したアプローチを紹介する。我々のアプローチは、目標とする直径に対しては素性がよいが節点数の少ないグラフを選び、そのグラフを多数複製してつなぎ合わせた後、貪欲に枝を追加していくものである。このアプローチが、直径3の一部のグラフではうまくいくことを紹介する。また、グラフの一部を変更しながら平均距離を短縮する局所探索についても我々のアプローチを紹介する。組合せ爆発とデータ構造の良し悪しに関するエピソードなども紹介する。
【略歴】 1993年京大・工・情報工卒。1995年奈良先端大・情報・博士前期課程了。同年シャープ(株)入社。2001年九州大学大学院システム情報科学研究院助手。2007年より熊本大学大学院自然科学研究科情報電気電子工学専攻准教授。2016年同大学大学院先端科学研究部環境科学部門に配置換。博士(工学)。モバイルネットワークとユビキタスコンピューティングの研究等に従事。情報処理学会、電子情報通信学会、IEEE各会員。
10:50-11:30 講演(3) 直径3のグラフにおける平均最短経路長の近似
清水 伸高(東京大学 大学院情報理工学系研究科数理情報学専攻 学生)
【概要】 グラフの直径(最短経路の最大値)と次数の間にはトレードオフがあることがグラフ理論では古くから知られていて、次数が制限されつつも小直径を実現するネットワークトポロジーの設計はVLSIデザイン、HPC、Data center、NoCsといった計算機の相互接続ネットワークを用いるような分野において重要な課題となっている。本講演では直径の代わりに平均最短経路長を最小化するような近傍探索を考える上で計算時間的なボトルネックとなる平均距離の計算について焦点を当て、小直径グラフの平均距離に関する理論的な結果を紹介し、この結果に基づいた手法とその有用性について発表する。
【略歴】 高校生の時より競技プログラミングに興味を持つ。Supercomputing Contest 2010, 2011第三位。パソコン甲子園プログラミング部門2009第二位。2016年東京工業大学理学部情報科学科卒業。同年より東京大学大学院情報理工学系研究科数理情報学専攻修士過程在学中。組合せ最適化理論とランダムグラフ理論に興味を持つ。