近似正規表現マッチングアルゴリズムのGPGPU実装およびFPGA実装と比較(再構成回路,システムオンシリコンを支える設計技術)

スポンサーリンク

概要

論文の詳細を見る
バイオインフォマティクスやデータベース検索で使用されている近似文字列マッチングにおいて,より高度なマッチングを行うため,正規表現を扱うシストリックアルゴリズムとそのFPGA実装法が提案されている.しかし,このFPGA実装では,DNAの配列検索などに必要な長いパターンを扱うことができない.そこで本研究では,スケーラブルな処理が可能なGPU上での近似正規表現マッチングの高速解法を提案する.また,FPGA実装と比較することで近似正規表現マッチングをGPU上で実装することの有用性を検証する.実験の結果,CPUと比較してFPGA実装が8.3倍,GPU実装が2.9倍高速に実行できることが分かった.特に,パターン長が3200以上の場合,CPUと比較してGPU実装では18倍以上の高速化ができた.また,FPGA実装ではパターンの文字数がFPGAの規模に制限されるのに対し,GPU実装ではFPGA実装よりも長いパターンを容易に扱えることを確認した.
2012-02-28

著者

関連論文

もっと見る

スポンサーリンク