A parallel approximate string matching under Levenshtein distance on graphics processing units using warp-shuffle operations.
作者： ThienLuan Ho , Seung-Rohk Oh , HyunJin Kim
DOI: 10.1371/JOURNAL.PONE.0186251
关键词:
摘要: 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 on Graphics Processing Units (GPUs). In the proposed algorithm, all threads in same GPUs warp share data using warp-shuffle operation instead accessing shared memory. Moreover, we implement by exploiting memory structure optimize its performance. Experiment results real DNA packages revealed that performance and implementation archived up 122.64 1.53 times compared sequential CPU previous GPUs, respectively.
harvard.edu
paperity.org参考文章(27)
M.C. Herbordt, T. Van Court, Families of FPGA-based algorithms for approximate string matching application-specific systems, architectures, and processors. pp. 354- 364 ,(2004) , 10.1109/ASAP.2004.25
V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals Soviet physics. Doklady. ,vol. 10, pp. 707- 710 ,(1966)
Marc-André Schulz, Barbara Schmalbach, Peter Brugger, Karsten Witt, Analysing Humanly Generated Random Number Sequences: A Pattern-Based Approach PLoS ONE. ,vol. 7, pp. e41531- ,(2012) , 10.1371/JOURNAL.PONE.0041531
Duhu Man, Koji Nakano, Yasuaki Ito, The Approximate String Matching on the Hierarchical Memory Machine, with Performance Evaluation 2013 IEEE 7th International Symposium on Embedded Multicore Socs. pp. 79- 84 ,(2013) , 10.1109/MCSOC.2013.22
Kimmo Fredriksson, Szymon Grabowski, Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching The Journal of Combinatorics. ,vol. 34, pp. 38- 51 ,(2013) , 10.1016/J.EJC.2012.07.013
Gonzalo Navarro, A guided tour to approximate string matching ACM Computing Surveys. ,vol. 33, pp. 31- 88 ,(2001) , 10.1145/375360.375365
Longjiang Guo, Shufang Du, Meirui Ren, Yu Liu, Jinbao Li, Jing He, Ning Tian, Keqin Li, Parallel Algorithm for Approximate String Matching with K Differences 2013 IEEE Eighth International Conference on Networking, Architecture and Storage. pp. 257- 261 ,(2013) , 10.1109/NAS.2013.40
Yu Liu, Longjiang Guo, Jinbao Li, Meirui Ren, Keqin Li, Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA international parallel and distributed processing symposium. pp. 2414- 2422 ,(2012) , 10.1109/IPDPSW.2012.298
Kentaro Inoue, Shinichi Shimozono, Hideaki Yoshida, Hiroyuki Kurata, Application of Approximate Pattern Matching in Two Dimensional Spaces to Grid Layout for Biochemical Network Maps PLoS ONE. ,vol. 7, pp. e37739- ,(2012) , 10.1371/JOURNAL.PONE.0037739
Cheng-Hung Lin, Chen-Hsiung Liu, Lung-Sheng Chien, Shih-Chieh Chang, Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs IEEE Transactions on Computers. ,vol. 62, pp. 1906- 1916 ,(2013) , 10.1109/TC.2012.254