Grid計算環境における遺伝的アルゴリズムのモデルの検討

Grid計算環境における遺伝的
アルゴリズムのモデルの検討
日本機械学会
第11回設計工学・システム部門講演会
(Design & Systems)
2001.11.5-7，香川県ヴィラ塩江
谷村勇輔 (同志社大院)
廣安知之 (同志社大工)
三木光範 (同志社大工)
グローバルコンピューティング
広域に配置された複数の計算資源を結びつけて
分散 / 並列計算を行うための環境
• Grid
– GUSTO, EU Grid, ApGrid
– 次世代の大規模計算（科学技術計算など）や大規模ストレージ
などの社会的 / 産業的基盤を構築する
• Internet Computing / Volunteer Computing
– SETI@home, RC5 Cracking Contest
– 一般ユーザのPC性能を結集して計算を行う
• P2P
– Napster, Gnutella, ICQ
– 各個人，各PC同士の結びつきから，何らかのコラボレーションを
行いながら計算 / 検索 / データおよび情報の共有を行う
Grid計算環境
• 各地に散らばる計算資源を
統合し，大規模計算のため
のポータルを作る (telnet
で接続し，実行するのとは
大きく異なる)
• どこからでも，今まで以上
に大規模な計算を行える
• 数多くの既存の技術を共有
できる
• ネットワーク性能は計算性
能以上に向上している
• 地球規模にネットワークが
普及しつつある
Grid計算環境の特徴
計算資源 (CPU，メモリ，ストレージ)
• 計算には非常に多くの資源が関与
• 各組織から提供される資源量は様々
• 資源の構成，利用できる資源量は動的に変化
ネットワーク資源
• 計算は複数の資源にわたって行われるため，常に
ネットワークを利用
• 各資源を結びつけるネットワークの処理量は様々，
かつ動的に変化
研究目的
• Grid計算環境を利用した最適化システムの構築
• 進化的手法は比較的，Grid環境に向いたアルゴリズム?
– 高い並列性を有している
– 多点探索で比較的独立性の高い探索を行う
– 環境に合わせてモデルを変更できる (動的にも)?
– 計算量を増やすことで，最適解を発見する確率を上げ
ることができる?
– 障害対策ができる?
Grid環境を利用した進化的手法を行うシステムを構築し，
シミュレーション実験を通じて基本的なモデルの検討を行う
Grid環境の階層構造
アプリケーション
AppLes
Nimrod-G
Netsolve
Condor-G
Globus Toolkit
コンピュータ資源
ネットワーク資源
分散メモリ型，共有メモリ型
スカラ型，ベクトル型
Ninf-G
Globus Toolkit
•
•
•
•
http://www.globus.org
Gridの構築に必要とされる基本的なサービスの集まり
これをベースにミドルウェアを開発する
主に以下のサービスがある
– GRAM : 資源管理 (リソースの割り当て)
– GASS : 遠隔データアクセス
– Nexus / Globus IO : 通信
– MDS : システムの構造・状態に関する情報アクセス
– GSI : セキュリティ
– HBM : 状態管理
Evolve システム
アプリケーション
Nimrod-G
GA, GP, SA など
Netsolve
Condor-G
Evolve システム
進化的手法をGridで
実現するためのシステム
Globus Toolkit
コンピュータ資源
ネットワーク資源
分散メモリ型，共有メモリ型
スカラ型，ベクトル型
システムの概要 (Master-Worker型)
Worker
Worker
Worker
システムの概要 (Master-Worker型)
PGA計算
PGA計算
PGA計算
システムの概要 (Master-Worker型)
システムの概要 (Master-Worker型)
チェックポインティング
チェックポインティング
• 定期的だが，Managerの要請によって行われる
• Managerによって管理された情報管理 / 移住モデル
Globus Toolkitを用いた実装
• Workerで実行する並列プログラムはMPIを用いる
(プロセスの起動)
(Master-Workerの通信)
数値実験 (対象問題)
• 構築したシステムと同等の
モデルをシミュレーションと
して用意し，GAの性能に
ついて検討を行う
• シミュレーションを用いるこ
とで，任意の現象を何度で
も再現可能である
Ridge関数
(n=30)
数値実験 (擬似Grid環境)
Grid環境 : 1 Master + 4 Workers
 各Workerサイトは4
ノードのPCクラスタ
 各Workerサイトのス
ペックは同じとする
 各Workerサイトまで
のネットワーク性能は
同じとする
数値実験 (各サイトのパラメータ)
島数
192
プロセッサ数
4
コーディング法
10bit グレイコード
交叉法
1点交叉
突然変異率
1 / 遺伝子長
移住トポロジ
リング
移住間隔
Inter:25, Intra:5
移住島の割合
0.1 (最低1島)
数値実験 (シナリオ)
• シナリオ1
問題なく計算が行える
• シナリオ2
途中でサイトが停止してしま
い，計算をリスタートさせる
必要がある
数値実験 (シナリオ1の結果)
f(x
)100000
f(x)
100000
10000
10000
1000
1000
100
100
10
10
1
1
0
1000
Generation
ばらばらに探索した時
2000
Site
Site
Site
Site
0
1000
Generation
検討モデル
1
2
3
4
2000
数値実験 (シナリオ2の結果)
f(x
)
100000
100000
10000
10000
1000
1000
100
100
10
10
1
1
Site
Site
Site
Site
f(x)
0
1000
Generation
ばらばらに探索した時
2000
0
1000
Generation
検討モデル
1
2
3
4
2000
まとめ
• Gridを利用して，Master-Worker型の進化的手法 (GA)
を実行するシステムを構築した．
• GAのモデルについて，シミュレーション実験を通じて検討を
行った．
– 複数の計算資源を利用して，より早く探索が行える
– 障害に対してロバストなモデルである
• 今後の課題
– 実際的な環境における実験
– 各資源の動的変化に対応したモデルの検討
– 対象問題を実問題とする
Gridを考慮したGAのモデル
• Gridを利用できる既存のアプリケーションモデル
(既存のミドルウェアを用いて，今すぐ実現可能)
– Parameter Sweepingを行う場合
– ホットスポットが粗粒度の反復アルゴリズムである場合
– タスクレベルの分散計算が行える場合
• Gridを考慮したアプリケーションモデルを作ると・・
– 並列コンピュータを複数束ねて，階層的に並列計算を行う
– 使用できる資源量を考慮して，モデルを変更する
興味深いが，これを実現するミドルウェアがない
Spare
Spare

Download Report