CUSMART: effective parallelization of string matching algorithms using GPGPU accelerators

Abstract

This study presents a parallel version of the string matching algorithms research tool (SMART) library, implemented on NVIDIA's compute unified device architecture (CUDA) platform, and uses general-purpose computing on graphics processing unit (GPGPU) programming concepts to enhance performance and gain insight into the parallel versions of these algorithms. We have developed the CUDA-enhanced SMART (CUSMART) library, which incorporates parallelized iterations of 64 string matching algorithms, leveraging the CUDA application programming interface. The performance of these algorithms has been assessed across various scenarios to ensure a comprehensive and impartial comparison, allowing for the identification of their strengths and weaknesses in specific application contexts. We have explored and established optimization techniques to gauge their influence on the performance of these algorithms. The results of this study highlight the potential of GPGPU computing in string matching applications through the scalability of algorithms, suggesting significant performance improvements. Furthermore, we have identified the best and worst performing algorithms in various scenarios.

Keywords

String matching / Parallel programming / Graphics processing unit (GPU) programming / General-purpose computing on GPU (GPGPU) / NVIDIA / Compute unified device architecture (CUDA) / String matching algorithms research tool (SMART)

RIGHTS & PERMISSIONS

The Author(s)