| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-03-07 13:45 近似正規表現マッチングアルゴリズムのGPGPU実装およびFPGA実装と比較 ○宇丹裕一朗・稲木雅人・永山 忍・若林真一（広島市大）  VLD2011-139 |
|
| 抄録 | （和） | バイオインフォマティクスやデータベース検索で使用されている近似文字列マッチングにおいて，より高度なマッチングを行うため， 正規表現を扱うシストリックアルゴリズムとそのFPGA実装法が提案されている． しかし，このFPGA実装では，DNAの配列検索などに必要な長いパターンを扱うことができない． そこで本研究では，スケーラブルな処理が可能なGPU上での近似正規表現マッチングの高速解法を提案する． また，FPGA実装と比較することで近似正規表現マッチングをGPU上で実装することの有用性を検証する． 実験の結果，CPUと比較してFPGA実装が8.3倍，GPU実装が2.9倍高速に実行できることが分かった． 特に，パターン長が3200以上の場合，CPUと比較してGPU実装では18倍以上の高速化ができた． また，FPGA実装ではパターンの文字数がFPGAの規模に制限されるのに対し，GPU実装ではFPGA実装よりも長いパターンを容易に扱えることを確認した． |
| （英） | Recently, to conduct more advanced approximate string matching, a systolic hardware algorithm for approximate string matching with some regular expression operators and its FPGA implementation have been proposed. In DNA sequence search, a long pattern and a long text are used. However, the FPGA implementation cannot handle a long pattern. This paper proposes a fast matching method for a long pattern on a GPU, which scalably proccesses data. Also, we evaluate the effectiveness of the GPU implementation comparing with the FPGA implementation. The experimental results showed that the FPGA and GPU implementations are 8.3 and 2.9 times as fast as a CPU implementation, respectively. Especially, the GPU implementation is more than 18 times as fast as the CPU implementation when the pattern length is greater than 3200. Futhermore, the FPGA implementation cannot handle long patterns, because its acceptable pattern length is limited by the size of an FPGA. Thus, the GPU implementation is effective to deal with a long pattern, such as DNA sequence. |
|
| キーワード | （和） | GPGPU / CUDA / FPGA / ストリングマッチング / / / / |
| （英） | GPGPU / CUDA / FPGA / String matching / / / / | |
| 文献情報 | 信学技報, vol. 111, no. 450, VLD2011-139, pp. 115-120, 2012年3月. | |
| 資料番号 | VLD2011-139 | |
| 発行日 | 2012-02-28 (VLD) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2011-139 |
|
| 研究会情報 | |
| 研究会 | VLD |
| 開催期間 | 2012-03-06 - 2012-03-07 |
| 開催地（和） | ビーコンプラザ |
| 開催地（英） | B-con Plaza |
| テーマ（和） | システムオンシリコンを支える設計技術 |
| テーマ（英） | Design Methodologies for System-on-a-chip |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2012-03-VLD |
| 本文の言語 | 日本語 |
| タイトル（和） | 近似正規表現マッチングアルゴリズムのGPGPU実装およびFPGA実装と比較 |
| サブタイトル（和） | |
| タイトル（英） | A GPGPU Implementation of Approximate Regular Expression Matching Algorithm and Comparison with an FPGA Implementation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | GPGPU / GPGPU |
| キーワード(2)（和/英） | CUDA / CUDA |
| キーワード(3)（和/英） | FPGA / FPGA |
| キーワード(4)（和/英） | ストリングマッチング / String matching |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 宇丹 裕一朗 / Yuichiro Utan / ウタン ユウイチロウ |
| 第1著者 所属（和/英） | 広島市立大学 (略称： 広島市大) Hiroshima City University (略称： Hiroshima City Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 稲木 雅人 / Masato Inagi / イナギ マサト |
| 第2著者 所属（和/英） | 広島市立大学 (略称： 広島市大) Hiroshima City University (略称： Hiroshima City Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 永山 忍 / Shinobu Nagayama / ナガヤマ シノブ |
| 第3著者 所属（和/英） | 広島市立大学 (略称： 広島市大) Hiroshima City University (略称： Hiroshima City Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 若林 真一 / Shin'ichi Wakabayashi / ワカバヤシ シンイチ |
| 第4著者 所属（和/英） | 広島市立大学 (略称： 広島市大) Hiroshima City University (略称： Hiroshima City Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-03-07 13:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2011-139 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.450 |
| ページ範囲 | pp.115-120 |
| ページ数 | 6 |
| 発行日 | 2012-02-28 (VLD) |
[研究会発表申込システムのトップページに戻る]