2024-03-28T22:05:08Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000270002023-04-27T10:00:04Z01164:02036:02049:02050
最小p-準クリーク被覆問題に対するハードウェアアルゴリズムA Hardware Algorithm for the Minimum p-quasi Clique Cover Problemjpnhttp://id.nii.ac.jp/1001/00027000/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=27000&item_no=1&attribute_id=1&file_no=1Copyright (c) 2006 by the Information Processing Society of Japan会津大学大学院コンピュータ理工学研究科 会津大学大学院コンピュータ理工学研究科 会津大学大学院コンピュータ理工学研究科 会津大学大学院コンピュータ理工学研究科渡辺, 秀一北道, 淳司奥山, 祐市黒田, 研一論文では最小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 ac celerate 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.AA11451459情報処理学会研究報告システムLSI設計技術(SLDM)2006126(2006-SLDM-127)2052102006-11-302009-06-30