Presentation is loading. Please wait.

Presentation is loading. Please wait.

グローバルコンピューティング環境における遺伝的アルゴリズムの検討

Similar presentations


Presentation on theme: "グローバルコンピューティング環境における遺伝的アルゴリズムの検討"— Presentation transcript:

1 グローバルコンピューティング環境における遺伝的アルゴリズムの検討
- JSPP2001 - グローバルコンピューティング環境における遺伝的アルゴリズムの検討 June 5-8, 2001, Joint Symposium on Parallel Processing, Kyoto Research Park 谷村 勇輔,廣安 知之 三木 光範,佐野 正樹 (同志社大学)

2 本研究の目的 グローバルコンピューティング環境を利用できる最適化システムの構築 最適化ソフトウェアとしてGAに着目し,
構造物の設計,たんぱく質の構造解析 従来の最適化手法では困難 GAなどのヒューリスティックなアルゴリズム 繰り返し計算が多いために膨大な計算が必要 Gridを利用する 最適化ソフトウェアとしてGAに着目し, そのグリッドモデルを検討する

3 遺伝的アルゴリズム(GA) 生物の進化の仕組みを応用 強力な最適化手法の1つ 個体(探索点) 計算負荷が高いという欠点 評価 選択 交叉
突然変異

4 分散遺伝的アルゴリズム(DGA) 単純GA(SGA) 分散GA(DGA) 移住 母集団を複数のサブ母集団(島)に分割する
移住による個体交換を行う 多様性を維持し,解の探索能力が高い 各島を1つのプロセッサに割り当てる

5 2個体分散遺伝的アルゴリズム (Dual DGA)
2個体分散GA (Dual DGA) 分散GA(DGA) 島内のアルゴリズムを単純にする 島数を多くすることで,より多様性を維持する 分散GAより探索性能が良い

6 Dual DGAの並列モデル 島移住 通信量が少なくて済む 粒度の単位を1つの島と,小さくすることができる
1PE 通信量が少なくて済む 粒度の単位を1つの島と,小さくすることができる 計算機の特性に合った(通信/計算)の割合 ロードバランス

7 Dual DGAの性能(1) GA Cluster Ridge 関数 (n = 30) 島数: 96 移住トポロジ: リング
プロセッサ内移住間隔: 5 プロセッサ間移住間隔: 25 GA PE数:16 CPU:Pentium II 400MHz メモリ:128MB ネットワーク:FastEhternet Cluster Ridge 関数 (n = 30)

8 Dual DGAの性能(2) 解探索の性能 実行性能

9 グローバルコンピューティング 環境でのモデル検討
サイト (並列計算機) Dual DGAを用いる理由 性能の良いGAを用いる 並列計算機(クラスタ)に実装しやすい 目的,要件 速く,良い解が得られること スケジューラの利用 サイト間のコミュニケーション 障害対策

10 検討するモデル スケジューラ チェックポインティング グローバルネットワーク スレーブサイト マスターサイト (並列計算機) (端末)
探索プロセス (Dual DGA) (並列計算機) マスターサイト (端末) ジョブの投入 スケジューラ 結果報告 ユーザ 管理プロセス 監視 キュー 経過報告,状態報告 チェックポインティング

11 チェックポインティングとキュー キュー Dual DGAの計算 Dual DGAの計算 最良の個体を収集 個体を分配 キューを用いて
時間 Dual DGAの計算 サイト1 個体を分配 最良の個体を収集 Dual DGAの計算 サイト2 キューを用いて サイト間の情報交換 解のバックアップ 探索状態の確認 キュー

12 キューの仕組み マスターサイト スレーブサイト 管理プロセス 探索プロセス 4PE キュー 最良個体を選ぶ スレーブサイト

13 キューの仕組み マスターサイト スレーブサイト 管理プロセス 探索プロセス キュー 最良個体 スレーブサイト

14 検討モデルが考慮したこと Gridで考慮すべきこと ネットワーク 性能,スループットの変動 通信モデル,トポロジ 障害,予測不能な現象
アプリケーション (検討モデル) ジョブ管理 (スケジューラ) Gridで考慮すべきこと その他 ネットワーク 性能,スループットの変動 通信モデル,トポロジ 障害,予測不能な現象 サイト 性能 スループットの変動 異なるアーキテクチャ

15 シミュレーション環境 任意の現象を何度でも再現できる ある現象を再現するシナリオ 各計算機は均等,スケジューリングアルゴリズムは考慮しない
モデルの検討 チェックポイントとキューの仕組みによる効果 Dual DGA スレーブサイト数: 4 各サイトのPE数: 4 チェックポイント: 100世代 キューサイズ: 32個体

16 想定するシナリオ シナリオ1 最後まで問題なく計算を実行できる シナリオ2 (ネットワークの障害) シナリオ3 (サイトの障害)
ネットワークが利用できない時がある 各サイトが定期的にチェックポイントを受けられない シナリオ3 (サイトの障害) スレーブサイトが停止する時がある 停止したサイトでは,計算を初めからやり直す

17 シナリオ2 チェックポイントが不定期 サイト 0 サイト 1 サイト 2 サイト 3 1 2 3 4 5 6 7 ネットワークが低負荷
サイト 0 サイト 1 サイト 2 サイト 3 ネットワークが低負荷 ネットワークが高負荷

18 想定するシナリオ シナリオ1 最後まで問題なく計算を実行できる シナリオ2 (ネットワークの障害) シナリオ3 (サイトの障害)
ネットワークが利用できない時がある 各サイトが定期的にチェックポイントを受けられない シナリオ3 (サイトの障害) スレーブサイトが停止する時がある 停止したサイトでは,計算を初めからやり直す

19 シナリオ3 サイトが途中で停止 サイト 0 サイト 1 サイト 2 サイト 3 1 2 3 4 5 6 7 走行 停止 初期化 アイドル
チェックポイント サイト 0 サイト 1 サイト 2 サイト 3 走行 停止 初期化 アイドル

20 シナリオ1 問題なく実行できる キューがない場合 検討モデル 目的関数 f 目的関数 f 世代数 世代数 サイト1 サイト2 サイト3
目的関数 f 目的関数 f サイト1 サイト2 サイト3 サイト4 世代数 世代数 キューがない場合 検討モデル

21 シナリオ1 問題なく実行できる キューがない場合 検討モデル 目的関数 f 目的関数 f 世代数 世代数 サイト1 サイト2 サイト3
目的関数 f 目的関数 f サイト1 サイト2 サイト3 サイト4 世代数 世代数 キューがない場合 検討モデル

22 シナリオ2 チェックポイントが不定期 不定期に行う場合 定期的に行う場合 目的関数 f 目的関数 f 世代数 世代数 サイト1 サイト2
目的関数 f 目的関数 f サイト1 サイト2 サイト3 サイト4 世代数 世代数 不定期に行う場合 定期的に行う場合

23 シナリオ3 サイトが停止する場合 キューがないモデル 検討モデル 目的関数 f 目的関数 f 世代数 世代数 サイト1 サイト2 サイト3
サイト4 目的関数 f 目的関数 f 世代数 世代数 キューがないモデル 検討モデル

24 デモ・システム(実装方法) シェルスクリプト MPIプログラム RPC サイト1 × スケジューラ サイト2 サイト3 世代数 探索点情報
負荷情報

25 デモ・システム(実験環境) 8 5 : 3 速度比 FastEthernetで接続 サイト1 P3 850MHz × 4 Linuxクラスタ
P3 850MHz × 4 Linuxクラスタ サイト2 P3 500MHz × 4 Linuxクラスタ サイト3 P2 300MHz × 1 P3 600MHz × 3 Linuxクラスタ FastEthernetで接続

26 デモ・システム(実験結果) シナリオ2,3 と同様の結果 実行時間 Ridge 関数の計算負荷を150倍にして測定
Dual DGAの実行時間 その他に要した時間

27 各サイトに性能差がある場合 高速なサイトでは,進化のスピードが速い サイト1 サイト2 サイト3 キューがないモデル 検討モデル

28 最良解の履歴を比較 エリートを交換するモデルの問題 初期収束を引き起こす ある程度孤立させる 部分解を分配する その他 工夫が必要

29 まとめ グローバルコンピューティング環境におけるGAのモデルを検討した 数値シミュレーション,およびデモシステム
GAのモデルとしてDual DGAを用いる マスタースレーブ型のモデル キューの仕組みをもったチェックポイント機能 数値シミュレーション,およびデモシステム 複数の計算資源を利用して,より高速に探索を行うことができる スケジューラが予測できないような障害に対してロバストなモデルである

30 今後の課題 実際のグローバルコンピューティング環境で動作するシステムを開発する デモ・システムを拡張する スケーラビリティについて検討を行う
Ninf,Globus,AppLeS などを利用する スケーラビリティについて検討を行う 数十サイト以上を利用できるのか? より実際的な問題を扱う GA以外のデータの取り扱い

31

32 グローバルコンピューティング環境でGAを行う利点
高い並列性を有する ⇒ 様々なモデルを作ることができる可能性 個体数で計算量が調整でき,計算量を増やすことで良い解が求まる可能性が高くなる ⇒ 無限のリソースを有効利用できる可能性 多点探索で比較的独立性が高い探索を行うため,計算途中に探索点情報が多少失われても,大勢に影響はない ⇒ 障害対策ができる可能性

33 グローバルコンピューティングの階層化モデル
アプリケーション ミドルウェア ツール群 ネットワーク/テストベッド GUSTO I-WAY APAN アカウント管理 セキュリティ 資源管理・スケジューリング 通信 情報管理,提供 並列拡張言語 メッセージ通信ライブラリ 遠隔システム向けRPC 広域分散処理 大規模シミュレータ

34 従来的な並列GAのモデル 単純GA 分散GA セルラGA ・・・ 通信量 多い 解探索 - 通信量 少ない 解探索 良い 通信量 多い
:1つのプロセッサに対応 単純GA 分散GA セルラGA ・・・ マスター スレーブ 個体 通信量 多い 解探索 - 通信量 少ない 解探索 良い 通信量 多い 解探索 良い by 文献,谷村・佐野の実験結果

35 Dual PDGAの粒度について 低性能 高性能 高性能 低性能 適切な 通信/計算 のバランス

36 補足資料 正常に動作するシナリオ キューなし キューあり 世代数 消費リソース

37

38


Download ppt "グローバルコンピューティング環境における遺伝的アルゴリズムの検討"

Similar presentations


Ads by Google