R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)

概要

論文の詳細を見る
本稿では,進化型計算の隔世代交替モデルをGrid Computingに実装することを試みる.隔世代交替モデルでは,世代交替の際に各計算機の同期を世代ごとに行う必要がある.しかし,Gridは動的かつヘテロな計算機環境であるため,低速計算機がボトルネックとなり,同期処理が効率良く行えない.さらに,分散可能なタスクが中粒度タスクゆえに,ネットワーク環境における通信遅延が問題となり,分散計算の効果が低下してしまう.本稿では,これらの問題に対し,Gridスケジューリングの立場から対処する.まず,同期処理に対し,タスクスケジューリングアルゴリズムRR(list scheduling with Round-robin order Replication)を適用する.さらに,通信遅延に対し,RRにおける強制終了の効率を考慮したスケジューリング手法RWQ(Remote Work Queue)を提案し,RRとRWQを併用するR3Qを提案する.いくつかの手法を比較した計算機実験の結果より,R3Qにより通信遅延時間に左右されず高い並列化効率が得られることを確認した.これより,R3QによりECの隔世代交替モデルにおいても,進化ダイナミクスを変えることなく,効率良くGridに実装できることを示した.
社団法人情報処理学会の論文
2006-09-15