谷村 勇輔 （同志社大学大学院） 廣安 知之 （同志社大学） 三木 光範 （同志社大学） 青井 桂子 （同志社大学大学院）

Presentation on theme: "谷村 勇輔 （同志社大学大学院） 廣安 知之 （同志社大学） 三木 光範 （同志社大学） 青井 桂子 （同志社大学大学院）"— Presentation transcript:

1 谷村 勇輔 （同志社大学大学院） 廣安 知之 （同志社大学） 三木 光範 （同志社大学） 青井 桂子 （同志社大学大学院）
Grid環境における 進化計算手法の検討 Summer United Workshops on Parallel, Distributed and Cooperative Processing , 湯布院ハイツ 谷村 勇輔 （同志社大学大学院） 廣安 知之 （同志社大学） 三木 光範 （同志社大学） 青井 桂子 （同志社大学大学院）

2 研究背景 Grid計算環境 Gridのアプリケーション 仮想的なコミュニティで資源を共有し，大規模計算が可能 従来とは異なる並列計算環境
動的に変化する環境，非均質な環境 セキュリティ，ポータビリティ，etc. 各種ミドルウェアの整備 テストベッドの整備 Gridのアプリケーション 様々なアプリケーションを動かしたい・・ どのような計算？ どのような計算モデル？ プログラミングモデルは？

3 Gridのプログラミングモデル Grid RPCに基づくシステム 上記以外の計算モデル 遠隔サーバに用意されたライブラリを容易に使う仕組み
ex. Ninf / Ninf-G, Netsolve Parameter Sweep, Master Workerモデルを想定 上記以外の計算モデル もともとGridに適したアルゴリズムのアプリケーションがあるのではないか？ タスク並列に適している あらかじめ分割された仕事

4 GOCA Grid Oriented Computing Application 上記を満たすアプリケーションとして・・
仕事は複数に分割できる 分割された仕事 互いに依存関係が少ないか，独立に実行可能である 並列処理可能である 仕事間は頻繁な通信を必要としない ある資源が突然利用できなくなっても，低コストで仕事を継続できる ある資源が突然加わっても，それを有効に利用できる 上記を満たすアプリケーションとして・・

5 進化計算 進化計算手法 (GA, GP, PSA, etc.) 最適化問題 生物の進化にヒントを得た最適化手法
目的関数の値を制約条件内で最小化，もしくは最大化する設計変数を決定する問題 Ex. 構造物の設計，タンパク質の立体構造予測 生物の進化にヒントを得た最適化手法 経験的かつ確率的な探索 ← GOCAを満たす 複雑かつ大規模な問題が解ける可能性 目的関数 設計変数 Opt.

6 EVOLVE/Gシステムの提案 目的 新しい機能として アプリケーションの記述 進化計算の研究者がGridモデルを容易に検討できる
MW以外のGridモデルの構築をサポートする 効率的にGrid環境を利用できる 新しい機能として Gridのノードをクラスタリングできる 階層的なクラスタを構築できる アプリケーションの記述 EVOLVE/Gが提供するAPIを利用する ジョブの実行，情報の取得，通信の枠組みなど

7 EVOLVE/Gシステム Client Agent Worker Agent Worker Worker Worker管理
コアな計算 実行要求，その他命令 情報の取得 実行要求 モニタリング Agentを介した通信 ユーザ拡張 Agent 基本システム Worker ユーザ拡張 Worker 基本システム Grid計算環境

8 Agentの動作 Agent Agentによる定期チェック 取得情報 3 1 情報の利用方法 2 Worker 障害ノードは省く
ネットワーク停止 マシン停止 3 Agentによる定期チェック 障害ノードは省く 取得情報 計算経過・結果 通信データ マシン状況 情報の利用方法 アプリケーション側で記述

9 Gridノードのクラスタリング ユーザが定義するルールに従う 計算性能，ネットワーク性能 所属するサイト，クラスタ型計算機 など
所属するサイト，クラスタ型計算機 など Grid環境

10 階層的なクラスタ計算 Super Agent Super Agent : 最上位のAgent 上位のWorker :
Worker / Agent Worker Super Agent : 最上位のAgent 上位のWorker : 下位のクラスタのAgent 上位の通信モデルと下位の通信モデルが存在する

11 評価実験 EVOLVE/Gを構築し，それを用いてPSA/GAcのGridモデルを実装する 3サイト，25ノードからなるGrid環境で実験
Basicモデル： クラスタリングしない Hybridモデル： クラスタリングする 3サイト，25ノードからなるGrid環境で実験 BasicモデルとHybridモデルの比較 手動でクラスタリングを行い，3つのサイト毎に分類する

12 PSA/GAc 並列SAとGAの遺伝的交叉を組み合わせたハイブリッドな最適化手法 SAの特徴 GAの特徴 両者の利点を生かすアルゴリズム
Start 並列SAとGAの遺伝的交叉を組み合わせたハイブリッドな最適化手法 SAの特徴 焼きなまし（アニーリング）を模倣 現在の状態しか保存しない 近傍に重点をおいた解探索 GAの特徴 生物の進化の仕組みを模倣 複数の個体を解候補としてもつ 大域的な探索 両者の利点を生かすアルゴリズム 主にタンパク質の立体構造予測に適用 生成処理 受理判定 推移 徐冷判定 徐冷処理 終了判定 End

13 PSA/GAc (contd.) 2個体のペアを作り，設計変数間で１点交叉を行う d d SA d:Crossover interval
End d Crossover Temperature High Low

14 Basicモデル Worker上でSAを実行し，Agent上で遺伝的交叉を行う
Agentのチェック時に，交叉周期まで計算を終了し，かつ連絡のとれるWorker同士でペアを作る 遅いWorkerは次のチェックポイントまで待機する (Agent) SA/Worker 計算 待機 遺伝的交叉

15 Hybridモデル 2階層のモデル 下位のクラスタでは基本的なPSA/GAcを行う 上位のクラスタでは，各PSA/GAcの最良解を交換する
最良解の交換

16 Hybridモデル (contd.) 最良解の交換 基本的なPSA/GAc Super Agent Worker / Agent

17 実験環境 同志社大学 大阪産業大学 合計 1 + 24 ノード Galley Cluster Gregor Cluster
PentiumIII 1.1GHz x 1 PentiumIII 850MHz x 8 Gregor Cluster PentiumIII 1GHz x 12 大阪産業大学 Moon Cluster Pentium4 1.7GHz x 4 合計 ノード 同志社大 Galley 100Mbps LAN Gregor Internet 大産大 Moon 1KB メッセージ送信時のスループット Galley – Gregor MB/sec Galley – Moon KB/sec

18 対象問題 タンパク質の立体構造予測 岡崎国立共同研究機構分子科学研究所 岡本らのエネルギー関数 Met-Enkephalin （5残基）
最小エネルギー構造は E < -11 kcal/mol である 19個の二面角を設計変数とする Main chain Side

19 パラメータと予備実験 各ノードで実行するSA数 16 初期温度 2.0 最終温度 0.10 交叉周期 192 ステップ
初期温度 2.0 最終温度 交叉周期 ステップ 近傍幅 180°→ （180×0.3）° エネルギー計算に要する時間 [sec] Cluster ステップ 192ステップ Galley Gregor Moon

20 最良解とステップ数の推移 (Basicモデルの場合)

21 Basicモデルの問題 計算の早いWorkerグループと遅いWorkerグループに分かれている 考察
チェックポイントでの最良解が振動している 同じ計算スピード同士で，情報交換を行っている 考察 最初からグループ分けしたモデル？ Hybridモデルが良いのではないか

22 モデル比較：ステップ数

23 モデル比較：経過時間

24 考察 (Hybridモデルの利点) パラメトリック探索（各実行が並列） 階層的な通信モデル
進化計算の並列アルゴリズムは，並列度を上げることにより，解探索能力にも影響があり，並列度を上げることが良い？ 大規模並列より，中規模の並列を複数試す方が良い？ 個々が完全に独立したパラメトリックサーチより，それぞれの情報を交換し合いながら，お互いに適切なパラメータを見つける 階層的な通信モデル 通信モデルを階層化し，上位のクラスタでは疎な通信，下位のクラスタでは密な通信を行う パフォーマンスのスケーラビリティを確保できる ネットワーク的に近いノードをクラスタリングする

25 まとめ 進化計算開発者のためのGridミドルウェア「EVOLVE/G」を提案 PSA/GAcのGridモデルの実装と評価実験
進化計算の論理モデルを自由に構築可能 Grid環境をクラスタリングし，階層的トポロジを形成可能 PSA/GAcのGridモデルの実装と評価実験 クラスタリングを行った階層モデルの有効性が示された 進化計算のようなアプリケーションのGridモデルを検討する際に，EVOLVE/Gが有効なシステムであることを確認した

26 EVOLVE/G Agent API eg_agent_worker_setting() eg_agent_check_worker()
eg_agent_read_data() Workerから取得した情報の読み込み タグを付けて読み込む eg_agent_write_data() Workerに送る情報の書き出し タグを付けて書き出す

27 EVOLVE/G Worker API eg_worker_read_param() eg_worker_check_readable()
Agentから送られる入力ファイルの読み込み eg_worker_check_readable() Agentからの要求が来ているかの確認 eg_worker_read_data() Agentからの受け取った情報の読み込み eg_worker_write_data() Agentへ送る情報の書き出し

28 遅いWorkerグループ 遅いWorkerは局所探索が間に合わない 遅いWorkerが生きる場合 機能分化 保険
傾斜法などで局所探索のみさせる パラメータを変えて，違うものを探す 保険 早いWorkerのノードに障害が発生する (アプリケーションより下位層の問題) 早いWorkerの探索が初期収束する (アプリケーションの問題)