最小p-準クリーク被覆問題に対するハードウェアアルゴリズム(システム設計・開発,デザインガイア2006-VLSI設計の新しい大地を考える研究会)  [in Japanese] A Hardware Algorithm for the Minimum p-quasi Clique Cover Problem  [in Japanese]

本論文では最小p-準クリーク被覆問題に対するハードウェアアルゴリズムを提案し,それをFPGA上へ実装する.本問題はNP完全として知られ,応用分野の一つに遺伝子発現プロファイル解析がある.本問題の計算時間の削減は遺伝子解析の高速化にとって重要である.本アルゴリズムは計算時間の削減のためニューラルネットワークを採用する.リングネットワークを用いた本アーキテクチャは全てのモジュールが互いに独立して並列動作が可能であるので,本アルゴリズムを高速に実行できる.本手法は既存手法より解の探索能力が高く,計算時間が小さいことを示す.

This paper proposes a hardware algorithm for the minimum p-quasi clique cover problem, and it is implemented on FPGA. This problem is known as NP-complete and appears in the gene expression profile analysis. The reduction of the calculation time for this problem is important to accelerate the gene analysis. Our algorithm adopts a neural network for the reduction of the calculation time. Our architecture using a ring network can accelerate the execution of our algorithm because all modules can execute in parallel independently. We show our method is better than the existing methods in the searching ability of a solution and the calculation time.