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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

実験環境 同志社大学 大阪産業大学 合計 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 合計 1 + 24 ノード 同志社大 Galley 100Mbps LAN Gregor Internet 大産大 Moon 1KB メッセージ送信時のスループット Galley – Gregor 10.95 MB/sec Galley – Moon 107.7 KB/sec

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

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

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

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

モデル比較：ステップ数

モデル比較：経過時間

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

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

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

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へ送る情報の書き出し

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