Parallelizing Exact and Approximate String Matching via Inclusive Scan on a GPU
Parallelizing Exact and Approximate String Matching via Inclusive Scan on a GPU
复制标题
通过 GPU 上的包含扫描并行化精确和近似字符串匹配
DOI：
10.1109/tpds.2016.2645222
复制
发表时间：
2017
影响因子：
5.3
通讯作者：
and Kenichi Hagihara.
中科院分区：
文献类型：
--
作者：
Yasuaki Mitani;Fumihiko Ino;and Kenichi Hagihara.
在本研究中，为了大幅提高精确和近似字符串匹配算法的运行时间，我们提出了一种位并行算法（如Shift-Or和Wu-Manber算法）的混合并行方法。我们的基本想法是将位并行算法解释为包含扫描操作，这允许这些位并行算法在图形处理单元（GPU）上有效运行；我们在这里实现了这种加速，因为包含扫描操作不仅消除了线程之间的重复搜索，而且实现了gpu友好的内存访问模式，最大限度地提高了内存读/写吞吐量。为了实现我们的想法，我们首先定义了两个二进制操作符，然后给出了关于这些操作符的结合性的证明，这对于包含扫描操作的并行化是必要的。最后，我们将包含扫描方案集成到先前基于分段的方案中，以最大化搜索吞吐量，确定同步成本和重复工作之间的最佳折衷点。通过实验，我们将所提出的方法与先前的基于片段的方法和基于索引的序列比对器进行了比较。对于在线字符串匹配，我们提出的方法比以前的方法快6.7-16.7倍，在GeForce GTX TITAN X GPU上实现了高达1.88太比特每秒（Tbps）的搜索吞吐量。因此，我们得出结论，我们提出的方法对于减少短模式的在线字符串匹配的运行时间是非常有效的。
In this study, to substantially improve the runtimes of exact and approximate string matching algorithms, we propose a tribrid parallel method for bit-parallel algorithms such as the Shift-Or and Wu-Manber algorithms. Our underlying idea is to interpret bit-parallel algorithms as inclusive-scan operations, which allow these bit-parallel algorithms to run efficiently on a graphics processing unit (GPU); we achieve this speed-up here because inclusive-scan operations not only eliminate duplicate searches between threads but also realize a GPU-friendly memory access pattern that maximizes memory read/write throughput. To realize our ideas, we first define two binary operators and then present a proof regarding the associativity of these operators, which is necessary for the parallelization of the inclusive-scan operations. Finally, we integrate the inclusive-scan scheme into a previous segmentation-based scheme to maximize search throughput, identifying the best tradeoff point between synchronization cost and duplicate work. Through our experiments, we compared our proposed method with previous segmentation-based methods and indexing-based sequence aligners. For online string matching, our proposed method performed 6.7-16.7 times faster than previous methods, achieving a search throughput of up to 1.88 terabits per second (Tbps) on a GeForce GTX TITAN X GPU. We therefore conclude that our proposed method is quite effective for decreasing the runtimes of online string matching of short patterns.
登录
查看更多内容
使用 GPGPU 并行化 Myers 快速位向量算法
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
L. Langner
通讯作者：
L. Langner
影响因子：
48
作者：
Langmead, Ben;Salzberg, Steven L.
通讯作者：
Salzberg, Steven L.
高效的文本搜索
DOI：
--
发表时间：
1989
期刊：
影响因子：
--
作者：
R. Baeza
通讯作者：
R. Baeza
Xeon Phi 协处理器上的位并行近似模式匹配
DOI：
10.1109/sbac-pad.2014.37
发表时间：
2014
期刊：
2014 IEEE 26th International Symposium on Computer Architecture and High Performance Computing
影响因子：
--
作者：
T. T. Tran;Simon Schindel;Yongchao Liu;B. Schmidt
通讯作者：
B. Schmidt
一种位并行近似字符串匹配算法的实现（Algorithm(AL) Vol.2009-AL-124）
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
O. Mikael;Watanabe Osamu
通讯作者：
Watanabe Osamu