Ho ThienLuan, Oh Seung-Rohk, Kim HyunJin
School of Electronics and Electrical Engineering, Dankook University, Yongin-si, Republic of Korea.
PLoS One. 2017 Oct 10;12(10):e0186251. doi: 10.1371/journal.pone.0186251. eCollection 2017.
Approximate string matching with k-differences has a number of practical applications, ranging from pattern recognition to computational biology. This paper proposes an efficient memory-access algorithm for parallel approximate string matching with k-differences on Graphics Processing Units (GPUs). In the proposed algorithm, all threads in the same GPUs warp share data using warp-shuffle operation instead of accessing the shared memory. Moreover, we implement the proposed algorithm by exploiting the memory structure of GPUs to optimize its performance. Experiment results for real DNA packages revealed that the performance of the proposed algorithm and its implementation archived up to 122.64 and 1.53 times compared to that of sequential algorithm on CPU and previous parallel approximate string matching algorithm on GPUs, respectively.
具有k差异的近似字符串匹配有许多实际应用，从模式识别到计算生物学。本文提出了一种高效的内存访问算法，用于在图形处理单元（GPU）上进行具有k差异的并行近似字符串匹配。在所提出的算法中，同一GPU warp中的所有线程使用warp-shuffle操作共享数据，而不是访问共享内存。此外，我们通过利用GPU的内存结构来实现所提出的算法，以优化其性能。对真实DNA包的实验结果表明，所提出的算法及其实现的性能分别比CPU上的顺序算法和GPU上以前的并行近似字符串匹配算法提高了122.64倍和1.53倍。
