Parallel Approximate String Matching Algorithm Based On Gpu

GPU has high parallel processing capability and low cost of computing.Accelerating string operations on GPU has been a research focus on parallel computingarea. Approximate string matching technique has been widely applied to many fieldssuch as virus detection, text mining and computational biology. The traditionalsequential algorithms are slow, and the parallel algorithms are all based on multipleprocessors, which have high costs of computing. Therefore, the effective parallelalgorithm for approximate string matching has significant practical significance. Themain researchs and contributions of this thesis are as follows.Firstly, this paper summarizes the programming environment for GPGPU, andstudies the working principle, programming model, storage model and programmingenvironment configuration method of CUDA in detail.Secondly, for the problem of k-mismatch approximate sting matching. Based onCUDA, this paper presents three parallel algorithms, namely, the thread parallelalgorithm, the block-thread parallel algorithm, and the OPT-block-thread parallelalgorithm. The OPT-block-thread parallel algorithm can take full advantage of thepowerful parallel capability of GPU. Furthermore, it balances the load among thethreads and optimizes the execution time with the memory model of GPU. This paperuses actual DNA sequences as experimental data, and the experimental results show thatcompared with the traditional sequential algorithm on CPU, the OPT-block-threadparallel algorithm on GPU in this paper achieves speedup of40–80, and the speedup isconsistent with theoretical analysis. Futhermore, the other algorithms achieve thespeedups of10.In the end, for the problem of k-difference approximate sting matching. Based ondynamic programming method, this paper presents a parallel algorithm which can calculate the elements in the same row of the Edit Distance Matrix in parallel byeliminating data dependency. The algorithm has a few synchronization times with highparallelism. This paper also implements the algorithm on GPU and multiple-core CPUs,and analyses the speedups of the algorithm under two envirements. The experimentalresults show that compared with the traditional sequential algorithm on CPU, theparallel algorithm proposed in this paper achieves speedup of7–12on GPU,1.3ondual-core CPU, and8–13on CPU with twenty-four cores. Futhermore, the speedups areconsistent with theoretical analysis in this paper.