部分一致を含む文字列に対する探索のAVXによる高スループット化

• Item type: SIG Technical Reports(1)
• 公開日: 2014-02-24
• タイトル: 部分一致を含む文字列に対する探索のAVXによる高スループット化
• タイトル / 言語: en
• タイトル: A High-Throughput String Search Using AVX for Partially Matching Data
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アプリケーション
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者名: 楠堂, 航; 伊野, 文彦; 萩原, 兼一
• 著者名(英): Ko, Kusudo; Fumihiko, Ino; Kenichi, Hagihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，多数の部分一致を含む文字列に対する高速な探索の実現を目的として，ベクトル命令 AVX （Advanced Vector Extensions） によるビット並列アルゴリズムの高スループット化手法を提案する．ビット並列アルゴリズムの特長は，部分一致する箇所の数や長さに実行時間が依存しないことである．提案手法は，探索の高スループット化を図るために，長さの異なる複数のパターンを同時に探索できるよう，ビット並列アルゴリズムを拡張する．具体的には，AVX 命令により CPU コアあたりの探索スループットを高め，OpenMP 指示文によるデータ並列処理を実現する．また，データ構造を工夫することにより，長さの異なる複数のパターンを効率よく同時に処理する．実験の結果，データ構造の工夫により探索スループットをおよそ 2 倍に向上できた．また，ゲノムデータのように多数の部分一致を含み，大きなテキストに対して提案手法が有用であることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we present an AVX (Advanced Vector Extensions) based high-throughput method for a bit-parallel algorithm, aiming at realizing fast string search for partially matching data. An advantage of the bit-parallel algorithm is that, its execution time does not depend on the number and length of partially matching strings. Our method realizes high-throughput string search by extending the bit-parallel algorithm so that it can simultaneously search multiple patterns of different lengths. We use AVX instructions to increase the search throughput per CPU core and employ OpenMP directives to realize data-parallel processing of string search. Furthermore, we improve the data structure so that multiple patterns of different lengths can be efficiently processed at the same time. As a result, we find that our data structure doubles the search throughput. We also find that our method is useful for partially matching large texts such as genomic data.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2014-HPC-143, 号 14, p. 1-7, 発行日 2014-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会