Effective and Efficient Parallelization of String Matching Algorithms Using GPGPU Accelerators

Abstract

String matching is one of the oldest and actively studied problems in computer science. It has applications in computer security, bio-informatics, social media processing, data mining, data compression, coding theory, and many other areas. Since the '70s, there have been dozens of proposed algorithms to this problem with different approaches and performance characteristics. While the sheer amount of proposed algorithms makes it hard to put together a comprehensive performance comparison study, there are a few projects like the String Matching Algorithms Research Tool (SMART) library from Thierry Lecroq and Simone Faro achieving this goal. Their library holds the code implementations for the majority of string matching algorithms in the literature. It is an invaluable tool for studying different string matching algorithms, but it lacks practicality because of its serial implementation in the age of parallel computation. Our aim is to present a parallel version of the library realized on the CUDA platform by Nvidia, employing GPGPU programming concepts for improved performance and gain insight on the parallel versions of these algorithms. We have developed CUSMART library, which contains parallelized versions of around 85 string matching algorithms using CUDA API. The performances of these algorithms are tested with different scenarios to get a fair comparison and determine their strong/weak application scenarios. Also, we have investigated some well-known optimization practices to observe how they impact the performance of these algorithms. Our results show an average of 40x speedup compared to the serial CPU version of algorithms indicating the potential of GPGPU computing on string matching applications.