MC-MPI (Multi-Cluster MPI) 近山・田浦研究室 力から知へ，知から力へ 力の情報処理： 大量の計算機を連携させて大規模な計算を高速に行う 並列・分散プログラミング環境， 並列・分散処理，メモリ管理，OS， プログラミング言語処理系 計算を支える根幹となる部分 日本中，世界中に広がった多数の計算機を使い超大規模な計算を高速に，かつ簡単に実現することを目標とする 知の情報処理： 計算機に知的・人間的な情報処理をさせる  コンピュータゲームプレイヤ，音楽情報処理，WWWデータの解析，大規模な 自然言語テキストの解析 人間が「うまく説明できないけれど」実現できていること 人間が発見するには困難な知識を，機械学習などの手法で計算機に学習させる 力と技術が知を産み， その知が新たな力となる 潜在する知識の発見 データマイニング 統計的自然言語処理 グラフ構造解析 大規模な実世界データ へのアクセス Web … Web Crawler crawling Collecter Extracter URL Web page Webクローラ 強いゲームプレイヤ (将棋・麻雀…) パワフルな プログラミング環境 ゲームの理解 探索アルゴリズム 並列計算技術 クラスタ管理技術 機械学習 知識獲得 クラスタ計算機 力の情報処理 接続関係を考慮した通信 トポロジ情報を用いた、高速・効率的な通信 - 用いるノードの接続関係を自動で推定 し，遠いノード同士の通信を極力減らす - 帯域幅を最大限使う 　- 無駄な通信を減らす 接続関係の推定 メッセージの往復時間(RTT) の測定だけを用いる 100ノードの推定にかかる時間は20秒程度 動的なプロセスの参加・脱退 プロセスの脱退 プロトコル 適応的な並列計算において， メッセージの喪失やデッド ロックのない、プロセスの 安全な脱退を支援 脱退したい ネットワークトポロジー情報の応用 InTrigger プロジェクト 6拠点514コアが 運用中 - 最終的に20-30拠点1000コア以上 Leaf のノードから 脱退する メッセージが 転送される 残ったノードで 計算続行 深さ優先ブロードキャスト バンド幅を有効に利用するため、互いに干渉しないリンクに沿ってパイプラインを構成してブロードキャストを行う 最適ブロードキャスト 　トポロジーとバンド幅の情報をもとに、スループットを最大にするパイプラインを構築する バンド幅の測定 　推定したトポロジー情報のエッジごとに利用可能な最大バンド幅を推定する D0 D2 D1 6 10 8 5 転送元 転送先 S 2 4 簡単な方法 Stable Broadcast 3 各ノードが受け取る データ量の合計: 19 データ量の合計: 10 脱退の流れ 同時に複数のプロセスが脱退を希望すると，脱退しないプロセスをRootとしたTreeを構築 Leafのノードから順に脱退 MC-MPI (Multi-Cluster MPI) プロファイリング結果を基に環境・アプリに適応する 　ノード間のRTT・ランク間のメッセージ数を数える 局所性を考慮したランク割り当て 低通信オーバヘッドのランク割り当てを行う 二次割り当て問題（QAP）の近似解を求める 局所性を考慮した接続確立 全対全で接続を張らない 近いノード・通信量が多いノードを中心に接続を張る リアルタイムな クラスタ監視・ 可視化システム スケーラブルな管理・監視 利用可能な計算機環境 日本中に分散した多数のクラスタ計算機 1000CPU規模 自動化されたアカウント管理 クラスタ間でアカウント情報を同期 多数の計算機の効率的な利用 多数のノードに対してコマンドを投入 ディスクイメージを用いて，簡単に多数のノードを再インストールリアルタイムに多数のノードの状態を把握 クラスタA クラスタB 8 16 24 1 9 17 25 2 10 18 26 3 11 19 27 32 40 48 56 33 41 49 57 34 42 50 58 35 43 51 59 4 12 20 28 5 13 21 29 6 14 22 30 7 15 23 31 36 44 52 60 37 45 53 61 38 46 54 62 39 47 55 63 8 16 24 1 9 17 25 2 10 18 26 3 11 19 27 32 40 48 56 33 41 49 57 34 42 50 58 35 43 51 59 4 12 20 28 5 13 21 29 6 14 22 30 7 15 23 31 36 44 52 60 37 45 53 61 38 46 54 62 39 47 55 63 8 16 24 1 9 17 25 2 10 18 26 3 11 19 27 32 40 48 56 33 41 49 57 34 42 50 58 35 43 51 59 4 12 20 28 5 13 21 29 6 14 22 30 7 15 23 31 36 44 52 60 37 45 53 61 38 46 54 62 39 47 55 63 クラスタ計算機 左: 本郷キャンパス 191ノード/382 CPU, 右: 柏キャンパス 65ノード/130 CPU) ランダムに 分担すると 性能が悪い きれいに分けたつもりでも 問題によっては 性能が悪化する 通信パターンを実測して その問題に適した分担方法を 自動的に選べるように

形式文法の推定を用いた複数タスクに対する強化学習 コンピュータ将棋プレイヤ「激指(げきさし)」 Webグラフ構造に着目したコミュニティ抽出 知の情報処理 (近山・田浦研究室) Webを対象にした多言語テキスト処理 形式文法の推定を用いた複数タスクに対する強化学習 大量に集めたWeb文書の中から，言語の垣根を越えた情報抽出を行う 翻訳関係にあるテキストペアを自動で判定・抽出 辞書情報を必要としない多言語ニュース記事の関連付け G S 1 2 3 4 5 6 7 8 試行錯誤で迷路を探索 履歴からのルールの推定 推定結果の文法を元に 強化学習し，最適ルートを獲得 複雑な特徴の自動抽出 ゲームの記録を用いた打ち手の学習 … 単純な特徴を組み合わせてふるい分け， 実際に役に立つ複雑な特徴を自動的に見つけ出す 単純な特徴 組み合わせて 複雑な特徴に 勝ち負けに 大きく影響する パターン これだけでは勝ち負けが判断できない コンピュータゲームプレイヤに，上級者の打つ手の好みを学習させる 上級者の打った手は打たなかった手より良いはず． 上級者の打った手を好んで打つようになれば強くなる． 前アマ竜王と対局中 コンピュータ将棋プレイヤ「激指(げきさし)」 Webグラフ構造に着目したコミュニティ抽出 関連するサイト間のリンクには特徴がある 特徴的な部分グラフ（二部グラフ）を見つければ，トピックを共有するページが含まれている可能性が高い 部分グラフ構造を利用してウェブコミュニティを見つけ出し，ウェブページ全体の内容理解の手助けとしたい ページの内容による分類，トピック間の相関の発見，など… ライフログデータを用いた物品検索 Web Graph Web page Link Web Community 日常生活を観察したデータ(＝ライフログ)から、身の回りの物品が 「いつ」「どこで」見えていたかを検索し、物品の管理に役立てる 大量のセンサデータに対し処理を行うことが必要 　分散したデータに対する大規模な計算を簡単に実現できるような環境を作り、その上で便利なアプリケーションを構築する 非専門家にも大規模並列計算 大規模計算を行いたいユーザー、計算機が置かれている環境共に多様化しており、これらを支援するソフトウェアが大切 スクリプト言語のPythonのライブラリとして提供 Remote Method Invocation (RMI)で遠隔のピアの計算を「遠隔オブジェクトへのメソッド呼び出し」に見せる 複雑なネットワーク環境への対応 NAT/firewall環境の計算資源も合わせた並列計算 スケーラブルなソリューション 900台でも安定して高速に動作する並列分散計算を目指したい グリッド用分散オブジェクトライブラリ leave join Fire Wall SSH Tunneling NAT obj.doJob(args) Transparent communication over the overlay 「電球どこ？」 「 2日前に机の上で見ました」 卒業論文のテーマは，本人の興味ある分野に関連したものを，相談しながら決めていきます． 「ネットワークトポロジを考慮したバンド幅推定の高速化手法」 卒論生からの一言: InTrigger と呼ばれる全国規模の分散環境を使った実験、また運用や管理などにも触れることができます。 「画像群中の物品発見における計算量削減手法の提案」 卒論生からの一言: 研究室内では他の人と少し毛色が違う内容で画像処理っぽいことやってます。 「自動取得したネットワーク構成情報に基づくMPI集合通信アルゴリズムの改良」 卒論生からの一言: 自分の好きなことを，好きなようにできる研究室です．すぐに相談に乗ってくれる先輩ばかりなので，楽しくやりがいがあると思います． 「Webフォーラムの構文情報を用いたトラブルシュート文書抽出」 卒論生からの一言: 並列分散処理から機械学習まで幅広い選択肢があり、様々な興味に応えてくれる研究室です。 「強化学習と進化的アルゴリズムによるゲームの局面評価関数の調整」 卒論生からの一言: 囲碁や将棋に限らず、どんなゲームでも研究対象になりえます。興味のある人はぜひ。 「並列分散環境での異常原因特定のためのログ解析法」 卒論生からの一言: 大規模な計算機環境で動いているプロセスの裏側を知ることができたりしてかなり興味深い内容です。 本年度の卒業論文テーマ例 その他：既存のトピックにとらわれず，自分の研究テーマ，新しい研究テーマを開拓する意欲のある学生諸君の参加を期待します．ソフトウェアを正しく動かすための数学的素養を身につけたい人，ソフトウェアを作って動かすことに喜びを感じられる人は極力支援します．