大規模グラフの最大クリーク問題に対するソフトウェア·再構成可能ハードウェア協調解法

摘要

大規模グラフを対象とした最大クリーク問題の解法を提案する．提案解法は，ソフトウェアと再構成可能ハードウェアの協調解法であり，分枝限定法に基づいて，与えられた大規模グラフから部分グラフを複数生成するソフトウェア部と，部分グラフに対し高速に解探索を行うハードウェア部からなる．本稿では，ハードウェア部をFPGA 上に実装した結果を報告する．提案解法は生成した部分グラフに対して分枝限定を行うことで効率良く解探索を行う．ハードウェア部をグラフのインスタンスに非依存な回路とすることで論理合成等の時間を不要とし，大量の部分グラフに対して解探索を行う場合でも高速に解を得ることを可能とした．提案解法により，ソフトウェアやハードウェア単体では解が得られなかった大規模グラフに対して，高速に解が得られることを確認した．