Accelerating rabin karp on a multi-core graphics processing unit using CUDA

Abstract

String matching algorithms are used to find the occurrences of a pattern in a given text or a large pool of strings. They are widely used in text editors in computing machines, database queries, bio-informatics, chern-informatics, search engines and many more applications. String matching can be of two ways as single pattern matching and multiple - pattern matching algorithms. Rabin Karp algorithm can act in both ways. Main usage of Rabin Karp is in plagiarism detecting applications and network intrusion detection systems. Since these algorithms are working on large pool of data, achieving higher efficiency on the implementation of these algorithms has been a major concern. Such implementations would enhance the efficiency of their applications. Parallel implementation of such algorithms can achieve such efficiency. Parallelism could have been achieved on such algorithms easily with the rapid development of GPU, (Graphical Processing Unit) which used to render graphics in computers in early days. But now they have evolved to cater for complex computations. The objective of this research is to achieve high efficiency of Rabin Karp algorithm . In this research the implementations have done in Rabin Karp algorithm using CUDA C, which is a language used for parallel programming on GPUs. We have compared CUDA implementation of this algorithm with its serial CPU implementation and parallel Pthread implementation on multi-core CPUs, to check whether the objective of- this research has accomplished. Eventually, based on comparison of average execution time for varying lengths of patterns for serial, CUDA C and Pthread implementations, conclusion was that CUDA implementation of Rabin Karp on the GPU can achieve high efficiency for large pool of data in string matching.