大規模グラフの最大クリーク問題に対するソフトウェア・再構成可能ハードウェア協調解法(FPGA高位合成,FPGA応用及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
大規模グラフを対象とした最大クリーク問題の解法を提案する.提案解法は,ソフトウェアと再構成可能ハードウェアの協調解法であり,分枝限定法に基づいて,与えられた大規模グラフから部分グラフを複数生成するソフトウェア部と,部分グラフに対し高速に解探索を行うハードウェア部からなる.本稿では,ハードウェア部をFPGA上に実装した結果を報告する.提案解法は生成した部分グラフに対して分枝限定を行うことで効率良く解探索を行う.ハードウェア部をグラフのインスタンスに非依存な回路とすることで論理合成等の時間を不要とし,大量の部分グラフに対して解探索を行う場合でも高速に解を得ることを可能とした.提案解法により,ソフトウェアやハードウェア単体では解が得られなかった大規模グラフに対して,高速に解が得られることを確認した.
- 一般社団法人電子情報通信学会の論文
- 2014-01-21
著者
関連論文
- 大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-)
- 大規模グラフの最大クリーク問題に対するソフトウェア・再構成可能ハードウェア協調解法(FPGA高位合成,FPGA応用及び一般)