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

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

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

分散遺伝的アルゴリズム（ＤＧＡ） 単純ＧＡ（ＳＧＡ） 分散ＧＡ（ＤＧＡ） 移住 母集団を複数のサブ母集団（島）に分割する 移住による個体交換を行う 多様性を維持し，解の探索能力が高い 各島を１つのプロセッサに割り当てる

２個体分散遺伝的アルゴリズム （Ｄｕａｌ ＤＧＡ） ２個体分散ＧＡ （Ｄｕａｌ ＤＧＡ） 分散ＧＡ（ＤＧＡ） 島内のアルゴリズムを単純にする 島数を多くすることで，より多様性を維持する 分散ＧＡより探索性能が良い

Ｄｕａｌ ＤＧＡの並列モデル 島移住 通信量が少なくて済む 粒度の単位を１つの島と，小さくすることができる １ＰＥ 通信量が少なくて済む 粒度の単位を１つの島と，小さくすることができる 計算機の特性に合った（通信／計算）の割合 ロードバランス

Ｄｕａｌ ＤＧＡの性能（１） ＧＡ Ｃｌｕｓｔｅｒ Ｒｉｄｇｅ 関数 （ｎ ＝ 30） 島数： 96 移住トポロジ： リング プロセッサ内移住間隔： 5 プロセッサ間移住間隔： 25 ＧＡ ＰＥ数：16 ＣＰＵ：Ｐｅｎｔｉｕｍ ＩＩ 400ＭＨｚ メモリ：128ＭＢ ネットワーク：ＦａｓｔＥｈｔｅｒｎｅｔ Ｃｌｕｓｔｅｒ Ｒｉｄｇｅ 関数 （ｎ ＝ 30）

Ｄｕａｌ ＤＧＡの性能（２） 解探索の性能 実行性能

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

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

チェックポインティングとキュー キュー Ｄｕａｌ ＤＧＡの計算 Ｄｕａｌ ＤＧＡの計算 最良の個体を収集 個体を分配 キューを用いて 時間 Ｄｕａｌ ＤＧＡの計算 サイト１ 個体を分配 最良の個体を収集 Ｄｕａｌ ＤＧＡの計算 サイト２ キューを用いて サイト間の情報交換 解のバックアップ 探索状態の確認 キュー

キューの仕組み マスターサイト スレーブサイト ① 管理プロセス 探索プロセス ４ＰＥ キュー ② 最良個体を選ぶ スレーブサイト

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

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

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

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

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

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

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

シナリオ１ 問題なく実行できる キューがない場合 検討モデル 目的関数 ｆ 目的関数 ｆ 世代数 世代数 サイト１ サイト２ サイト３ 目的関数 ｆ 目的関数 ｆ サイト１ サイト２ サイト３ サイト４ 世代数 世代数 キューがない場合 検討モデル

シナリオ１ 問題なく実行できる キューがない場合 検討モデル 目的関数 ｆ 目的関数 ｆ 世代数 世代数 サイト１ サイト２ サイト３ 目的関数 ｆ 目的関数 ｆ サイト１ サイト２ サイト３ サイト４ 世代数 世代数 キューがない場合 検討モデル

シナリオ２ チェックポイントが不定期 不定期に行う場合 定期的に行う場合 目的関数 ｆ 目的関数 ｆ 世代数 世代数 サイト１ サイト２ 目的関数 ｆ 目的関数 ｆ サイト１ サイト２ サイト３ サイト４ 世代数 世代数 不定期に行う場合 定期的に行う場合

シナリオ３ サイトが停止する場合 キューがないモデル 検討モデル 目的関数 ｆ 目的関数 ｆ 世代数 世代数 サイト１ サイト２ サイト３ サイト４ 目的関数 ｆ 目的関数 ｆ 世代数 世代数 キューがないモデル 検討モデル

デモ・システム（実装方法） シェルスクリプト ＭＰＩプログラム ＲＰＣ サイト１ × スケジューラ サイト２ サイト３ 世代数 探索点情報 負荷情報

デモ・システム（実験環境） 8 5 : 3 速度比 ＦａｓｔＥｔｈｅｒｎｅｔで接続 サイト１ Ｐ３ 850ＭＨｚ × ４ Ｌｉｎｕｘクラスタ Ｐ３ 850ＭＨｚ × ４ Ｌｉｎｕｘクラスタ サイト２ Ｐ３ 500ＭＨｚ × ４ Ｌｉｎｕｘクラスタ サイト３ Ｐ２ 300ＭＨｚ × １ Ｐ３ 600ＭＨｚ × ３ Ｌｉｎｕｘクラスタ ＦａｓｔＥｔｈｅｒｎｅｔで接続

デモ・システム（実験結果） シナリオ２，３ と同様の結果 実行時間 Ｒｉｄｇｅ 関数の計算負荷を150倍にして測定 Ｄｕａｌ ＤＧＡの実行時間 その他に要した時間

各サイトに性能差がある場合 高速なサイトでは，進化のスピードが速い サイト１ サイト２ サイト３ キューがないモデル 検討モデル

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

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

今後の課題 実際のグローバルコンピューティング環境で動作するシステムを開発する デモ・システムを拡張する スケーラビリティについて検討を行う Ｎｉｎｆ，Ｇｌｏｂｕｓ，ＡｐｐＬｅＳ などを利用する スケーラビリティについて検討を行う 数十サイト以上を利用できるのか？ より実際的な問題を扱う ＧＡ以外のデータの取り扱い

ｰ

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

グローバルコンピューティングの階層化モデル アプリケーション ミドルウェア ツール群 ネットワーク／テストベッド ＧＵＳＴＯ Ｉ－ＷＡＹ ＡＰＡＮ アカウント管理 セキュリティ 資源管理・スケジューリング 通信 情報管理，提供 並列拡張言語 メッセージ通信ライブラリ 遠隔システム向けＲＰＣ 広域分散処理 大規模シミュレータ

従来的な並列ＧＡのモデル 単純ＧＡ 分散ＧＡ セルラＧＡ ・・・ 通信量 多い 解探索 － 通信量 少ない 解探索 良い 通信量 多い ：１つのプロセッサに対応 単純ＧＡ 分散ＧＡ セルラＧＡ ・・・ マスター スレーブ 島 個体 通信量 多い 解探索 － 通信量 少ない 解探索 良い 通信量 多い 解探索 良い ｂｙ 文献，谷村・佐野の実験結果

Ｄｕａｌ ＰＤＧＡの粒度について 低性能 高性能 高性能 低性能 適切な 通信／計算 のバランス

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

ｰ

ｰ