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

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

We have proposed parallel early computation, an asymmetrical speculative multi-threading with auto-memoization technology. However, some programs benefit not so much from parallel early computation bacause of low hit-ratio of input speculation, and other programs such as GA benefit little. Hence, we aim the combination of parallel processing and early computation. This system dynamically changes the ratio between the number of main cores and speculative cores according to the behavior of target programs, and two or more main cores share the memoization information. This paper proposes a speedup technique with the dual-core auto-memoization processor for the fitness calculation of GA programs. Through the result of an evaluation with GENEsYs, a well-known GA software, we show that dualcore auto-memoization processor gains significantly large speedup, up to 14.2-fold and 3.1-fold on average.The method of combining auto-memoization technique with parallel processing is effective in such as genetic algorithm programs.