Name
Abstract | ||
|---|---|---|
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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">27</sup>
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/CANDAR.2018.00026 | 2018 Sixth International Symposium on Computing and Networking (CANDAR) |
Keywords | Field | DocType |
Pattern matching, Rabin-Karp algorithm, Prefix-sums, GPGPU, CUDA | Computer science,Prefix sum,Parallel computing,Thread (computing),Rabin–Karp algorithm,General-purpose computing on graphics processing units,Graphics processing unit,Pattern matching,Hash table,Speedup | Conference |
ISSN | ISBN | Citations |
2379-1888 | 978-1-5386-9183-0 | 1 |
PageRank | References | Authors |
0.36 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucas Saad N. Nunes | 1 | 4 | 1.81 |
| Jacir Luiz Bordim | 2 | 57 | 18.86 |
| Yasuaki Ito | 3 | 511 | 60.47 |
| K. Nakano | 4 | 31 | 18.27 |