A Fast Approximate String Matching Algorithm on GPU

The approximate string matching (ASM) problem asks to find a substring of string Y of length n that is most similar to string X of length m. The ASM can be solved by dynamic programming technique, which computes a table of size m × n. The main contribution of this work is to present a memory-access-efficient implementation for computing the ASM on a GPU. The key idea of our implementation relies on warp shuffle for communication between threads without resorting to shared memory access. Surprisingly, our implementation performs only O(mn/w) memory access operations, where w is the warp size, although O(mn) memory access operations are necessary to access all elements in the table of size n × m. Experimental results, carried out on a GeForce GTX 980 GPU, shows that the proposed implementation called w-SCAN provides a speed-up factor over 200 as compared to a single CPU implementation. Also, w-SCAN computes the ASM in less than 40% of the time required by another prominent alternative.