Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CANDAR.2015.29 | CANDAR |
Keywords | Field | DocType |
approximate string matching, edit distance, GPU, CUDA, memory machine models | Edit distance,Substring,Uniform memory access,Commentz-Walter algorithm,Shared memory,Computer science,CUDA,Parallel computing,Algorithm,Approximate string matching,CUDA Pinned memory | Conference |
ISSN | Citations | PageRank |
2379-1888 | 2 | 0.40 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucas Saad N. Nunes | 1 | 4 | 1.81 |
| Jacir Luiz Bordim | 2 | 57 | 18.86 |
| Koji Nakano | 3 | 1165 | 118.13 |
| Yasuaki Ito | 4 | 511 | 60.47 |