並列化および再利用によるGAの高速化(ARC-5 : マルチプロセッサ応用,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))

概要

論文の詳細を見る
我々は,再利用および並列事前実行を用いた高速化手法を提案している.しかし,並列事前実行では投機に多数のコアを割り当てても更なる高速化は見込めず,逆に速度の低下を招くこともある.また,GAのように並列事前実行の効果が得られないプログラムも存在することから,全てのコアを投機に割り当てる方法は有効とは言えない.この様な場合に,従来投機に割り当てていたコアをメインコアとしても用いることで並列処理を行い,この投機コアとメインコアの数を動的に変えて実行を行う手法が考えられる.本稿ではこの効果を検証するため,2つのメインコアが再利用表を共有する機構を実装し,GAにおいて評価,検討を行った.汎用GAソフトウェアGENEsYsの,24種の適合度関数に対しコア数2つで再利用を行った場合,コア数1つで再利用を行わない場合に比べ最大14.2倍,平均3.1倍の高速化を実現した.このようにGAのような並列化が容易なプログラムについては,再利用と並列処理を組み合わせることで更なる効果を得られることが分かった.
2007-08-01