多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例）コンピュータ将棋における次手の計算 6八金 2六歩 3六香 ゲーム木探索 例）コンピュータ将棋における次手の計算 非常に多くの計算リソースを消費する ⇒遊休PCを利用して高速化 低コストで高性能 3六香 6八金
将棋ソフト激指（開発：近山研有志）を改造 実装 特徴 動的にPCが増減する中でも動作可能 中央集権的な管理を行わない システムの構成 コンピュータ将棋 将棋ソフト激指（開発：近山研有志）を改造 将棋の思考ルーチンなど 岸本らの手法 [ICCP’02]に基づく 同じ盤面を探索するPCは常に同じ 同じ盤面の2回目以降の探索を省略 分散ゲーム木探索 タスクの生成 実行結果の取得 タスク管理機構 盤面のハッシュ値に基づいて探索を各PCにばらまく タスク投入先PCとの通信 通信機構 Phoenixを利用 物理PCに依存しない名前空間を提供 盤面のハッシュ値とPCとを対応付け 並列計算ライブラリ 実行の様子 以前に現れた盤面なので探索を省略 6 17 20 13 名前空間の割り当ては動的に変更可能 ⇒PCの追加・削除にあわせて調節 3 34 62 42 53 23 １ 60 6 名前空間 16 32 48 64
多数の遊休PC上での 分散ゲーム木探索 性能評価 実験環境 実験内容 東芝TECRA x 720台 各PCは100Base-Tで結合 金田憲二 東京大学 / PRESTO, JST 性能評価 実験環境 東芝TECRA x 720台 CPU: PentiumM 1.3GHz Memory: 512MB 各PCは100Base-Tで結合 実験内容 将棋の中盤の盤面からの探索時間 探索の深さは12と14
実験結果 考察：性能低下の原因 1台時と比較して7~8倍の性能向上 元の激指と比較すると4~15倍遅い 分散化によるオーバヘッド 探索盤面数の増加 深さ12で約2倍，深さ14で約7倍 小さい並列度 同時に探索可能な盤面数が， 深さ10の探索では，最大で162 深さ12における探索時間 深さ14における探索時間 2分木の探索木 将棋の探索木 参考文献 Kenjiro Taura, Kenji Kaneda, and Toshio Endo “Phoenix: a Parallel Programming Model for Accommodating Dynamically Joining/Leaving Resources” (PPoPP’03) Kenji Kaneda, Kenjiro Taura, and Akinori Yonezawa “Routing and Resource Discovery in Phoenix Grid-Enabled Message Passing Library” (CCGrid’04)
27 侵入検知システムのデータベース 22 侵入検知システムのデータベース 24 侵入検知システムのデータベース 12 侵入検知システムのデータベース 14 侵入検知システムのデータベース 16 侵入検知システムのデータベース 18 侵入検知システムのデータベース 20 侵入検知システムのデータベース 22 侵入検知システムのデータベース 24 侵入検知システムのデータベース 27 侵入検知システムのデータベース
36 侵入検知 侵入検知 44 侵入検知 48 侵入検知 56 侵入検知 80 侵入検知システムのデータベース