部分グラフ同型判定アルゴリズムのFPGAによる実装と評価 An FPGA - Based Implementation of Subgraph Isomorphism Algorithm

この論文にアクセスする

この論文をさがす

著者

抄録

多くの応用は部分グラフ同型判定問題としてモデル化できるが,部分グラフ同型判定は一般にNP完全で実用時間内に解くことが難しい.この問題を専用回路で高速に解くため,ハードウェア化に適したアルゴリズムを提案し,FPGAに実装して評価した.試作回路はPCIバス経由でホストPCに接続され,ホスト上のソフトウェアから利用される.1チップのLucent ORCA 2C15A FPGA上に2つの同型判定ユニットが実装され,それぞれ16.5MHzで並列に動作する.Pentium-II 400MHzのPC上でソフトウェアを用いて実行した場合と比べ,最大20倍程度の性能を発揮する.より大規模なFPGAを用い,複数のチップやボードを同時利用することで,更なる性能向上も容易である.Many applications can be modeled as subgraph isomorphism problem, which is generally NP-complete and hard to compute practically. To accelerate the solver, an algorithm that is suited for hardware implementation is proposed and evaluated on FPGA. The prototype accelerator operates at 16.5 MHz on Lucent ORCA 2C15A, which outperforms the software implementation of Ullmann's algorithm on 400 MHz Pentium-II by 20 times in the best case. The performance can be boosted easily by using multiple FPGA chips or multiple boards.

Many applications can be modeled as subgraph isomorphism problem, which is generally NP-complete and hard to compute practically. To accelerate the solver, and algorithm that is suited for hardware implementation is proposed and evaluated on FPGA. The prototype accelerator operates at 16.5 MHz on Lucent ORCA 2C15A, which outperforms the software implementation of Ullmann's algorithm on 400 MHz Pentium-II by 20 times in the best case. The performance can be boosted easily by using multiple FPGA chips or multiple boards.

収録刊行物

  • 情報処理学会研究報告計算機アーキテクチャ(ARC)

    情報処理学会研究報告計算機アーキテクチャ(ARC) 2000(23(1999-ARC-137)), 71-76, 2000-03-02

    一般社団法人情報処理学会

参考文献:  7件中 1-7件 を表示

各種コード

  • NII論文ID(NAID)
    110002774830
  • NII書誌ID(NCID)
    AN10096105
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    5340346
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-1121
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ