@techreport{oai:ipsj.ixsq.nii.ac.jp:00098700,
 author = {楠堂, 航 and 伊野, 文彦 and 萩原, 兼一 and Ko, Kusudo and Fumihiko, Ino and Kenichi, Hagihara},
 issue = {14},
 month = {Feb},
 note = {本論文では，多数の部分一致を含む文字列に対する高速な探索の実現を目的として，ベクトル命令 AVX （Advanced Vector Extensions） によるビット並列アルゴリズムの高スループット化手法を提案する．ビット並列アルゴリズムの特長は，部分一致する箇所の数や長さに実行時間が依存しないことである．提案手法は，探索の高スループット化を図るために，長さの異なる複数のパターンを同時に探索できるよう，ビット並列アルゴリズムを拡張する．具体的には，AVX 命令により CPU コアあたりの探索スループットを高め，OpenMP 指示文によるデータ並列処理を実現する．また，データ構造を工夫することにより，長さの異なる複数のパターンを効率よく同時に処理する．実験の結果，データ構造の工夫により探索スループットをおよそ 2 倍に向上できた．また，ゲノムデータのように多数の部分一致を含み，大きなテキストに対して提案手法が有用であることが分かった．, 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.},
 title = {部分一致を含む文字列に対する探索のAVXによる高スループット化},
 year = {2014}
}