A Prefix-Sum-Based Rabin-Karp Implementation for Multiple Pattern Matching on GPGPU

In recent years, Graphics Processing Unit (GPU) has been increasingly used for general-purpose processing, referred as General Purpose GPU (GPGPU). They have been used by the scientific community in several areas, including cryptography, ordering, graphs and sequence alignment. The main contribution of this work is to propose a parallel Rabin-Karp implementation for handing multiple pattern matching. Given a text of length n and p patterns of length m, the proposed prefix-sum based Rabin-Karp algorithm finds all occurrences of p in n in O(m+q+ n/τ + nm/q) time, where q is a sufficiently large prime number and τ is the available number of threads. The proposed GPGPU implementation uses the prefix-sums algorithm as the basis to maximize parallelization of the algorithm along with a hash table to speedup matching verification. The proposed solution allows the comparison of multiple patterns at once without a significant difference in running time. For n=2
²⁷
and m ranging from 10 to 30, experimental results show that the proposed implementation provides speedup surpassing 2 times for a single pattern and speedup surpassing 10 times for p=256 patterns as compared to an OpenMP implementation on a multicore CPU.