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

Search this Article

Author(s)

Abstract

多くの応用は部分グラフ同型判定問題としてモデル化できるが、部分グラフ同型判定は一般に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.

Journal

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

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

    Information Processing Society of Japan (IPSJ)

References:  23

Keywords

Codes

  • NII Article ID (NAID)
    110002725569
  • NII NACSIS-CAT ID (NCID)
    AA11560614
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    03875806
  • NDL Article ID
    5731881
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  NDL  NII-ELS 
Page Top