Efficient Parallel Knuth-Morris-Pratt Algorithm for Multi-GPUs with CUDA

String matching is an important technique among various applications. The traditional string matching algorithm needs the backtracking procedure and does the comparison repeatedly, thus these factors affect its efficiency. Knuth-Morris-Pratt (KMP) is one of well-known and efficient string matching algorithms. However, the computation time of KMP algorithm still is large for processing thousands of pattern strings. Current high-end graphics processing units (GPUs), contain up to hundreds cores per chip, are very popular in the high performance computing community. In this paper, we proposed an efficient parallel KMP algorithm, called KMP-GPU, for multi-GPUs with CUDA. The experimental results showed that the proposed KMP-GPU algorithm can achieve 97x speedups compared with the CPU-based KMP algorithm.