高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装

摘要

組み合わせ最適化問題と呼ばれる問題は世の中に広く存在している．組み合わせ最適化問題はNP困難な問題であるため，一般的にはgreedy法のような近似解法を用いて解かれている．しかし，近似解法では，問題によっては局所解に陥り，最適解との差が大きくなってしまう場合や，解を算出できない場合がある．一方，ハードウェアの性能向上などの要因により，組み合わせを総当たりで調べる列挙法を用いた場合でも，最適解を現実的な時間で得ることができる可能性が出てきている·列挙法の高速化のためには，組み合わせを高速に生成する必要がある．そこで，本稿では列挙法の高速化を目的とし，既存の組み合わせ生成アルゴリズムの性能評価を行い，高速化のための課題を明らかにする．さらに，従来よりも高速に組み合わせの生成を行うことが可能なアルゴリズムを提案する．FPGAを対象デバイスとして提案アルゴリズムをハードウェア化し，性能評価を行った結果，既存の組み合わせ生成アルゴリズムを汎用CPUを用いて実行した場合に比べて500倍以上，専用ハードウェアで生成した場合に比べて10倍以上の速度で組み合わせを生成可能であることが示された．