Parallel Rabin-Karp Algorithm Implementation on GPU (preliminary version)

Abstract

The task of finding strings that match to a given pat- tern is of interest in a variety of practical applications, including DNA sequencing and text searching. Owing to its importance, alternatives to accelerate the pattern matching task have been widely investigated in the literature. The main contribution of this work is to present a parallel version of the celebrated Rabin-Karp algorithm. Given a pattern P of size m and a text string T of size n, the Rabin-Karp algorithm finds all occurrences of the pattern P in T with high probability. The proposed scheme can compare k different patterns to the input text concurrently. The proposed, parallelized, version of the Rabin-Karp algorithm has been implemented on the GeForce GTX 960 GPU. The results obtained show that the proposed implementation provides acceleration, compared to a sequential (CPU) implementation, surpassing 140 times for k = m = 1024 and n = 2^22.