FPGA上への遺伝的アルゴリズムの柔軟な実装手法の提案

Abstract

遺伝的アルゴリズム（GA）は様々なアプリケーションに用いることができる．GAを用いたアプリケーションは，ハードウェア上に実装することで，安価で資源の少ない情報機器上で利用することができる．本論文では，適用する問題や利用可能な回路規模に従って，実行効率の良いGA回路を合成するためのアーキテクチャを提案し，またこのアーキテクチャに従って実装される回路の規模予測モデルを提案する．本アーキテクチャ及び回路規模予測モデルを用いて，指定するFPGAデバイスに実装が可能なパラメータ値を探索するツールと，そのパラメータ値をもとにVHDLで記述されたRTレベル回路記述を自動で生成するツールを作成した．提案手法の有効性を示すために，ナップサック問題と巡回セールスマン問題を対象とするGA回路を提案アーキテクチャに従ってVHDLで記述し，コンパイルを行いゲートレベルで合成した．合成された回路が優れた解探索性能をもつことをシミュレーションにより確認し，また低消費電力で動作することも確認した．また，回路規模の予測結果が実際に論理合成を行って得たサイズに十分近いことを確認した．