部分グラフ同型判定アルゴリズムの 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 problems, which is generally NP-complete and difficult 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.5MHz on Lucent ORCA 2C15A, which outperforms the software implementation of Ullmann's algorithm on a 400MHz Pentium-II by 20 times in the best case. The performance can be boosted easily by using multiple FPGA chips or multiple boards.

収録刊行物

  • 情報処理学会論文誌. ハイパフォーマンスコンピューティングシステム

    情報処理学会論文誌. ハイパフォーマンスコンピューティングシステム 41(1), 39-49, 2000-08-15

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

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

キーワード

各種コード

  • NII論文ID(NAID)
    110002725569
  • NII書誌ID(NCID)
    AA11560614
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    03875806
  • NDL 記事登録ID
    5731881
  • NDL 請求記号
    Z74-C192
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ