The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le volume d’informations numériques augmente à un rythme extrêmement rapide, ce qui, à son tour, exacerbe le besoin de mécanismes efficaces pour détecter la présence d’un modèle dans un texte saisi ou un ensemble de chaînes saisies. Combiner la puissance de traitement de l'unité de traitement graphique (GPU) avec des algorithmes de correspondance semble une alternative naturelle pour accélérer le processus de correspondance de chaînes. Ce travail propose une implémentation parallèle de Rabin-Karp (PRK) qui englobe un algorithme de sommes de préfixes parallèles rapides pour maximiser la parallélisation et accélérer la vérification de la correspondance. Étant donné un texte d'entrée T de longueur n et p modèles de longueur m, l'implémentation proposée trouve toutes les occurrences de p in T in O(m+q+n/τ+nm/q) heure, où q est un nombre premier suffisamment grand et τ est le nombre de threads disponibles. Des versions séquentielles et parallèles du PRK ont été implémentées. Des expériences ont été réalisées sur p≥1 modèles de longueur m comprenant m=10, 20, 30 caractères comparés à une chaîne de texte de longueur n=227. Les résultats montrent que l'implémentation parallèle de l'algorithme PRK sur le GPU NVIDIA V100 offre une accélération supérieure à 372 fois par rapport à l'implémentation séquentielle et une accélération de 12.59 fois par rapport à une implémentation OpenMP exécutée sur un serveur multicœur avec 128 threads. Par rapport à une autre implémentation GPU importante, l’implémentation PRK a atteint une vitesse supérieure à 37 fois.
Lucas Saad Nogueira NUNES
University of Brasilia
Jacir Luiz BORDIM
University of Brasilia
Yasuaki ITO
Hiroshima University
Koji NAKANO
Hiroshima University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Lucas Saad Nogueira NUNES, Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, "A Rabin-Karp Implementation for Handling Multiple Pattern-Matching on the GPU" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 12, pp. 2412-2420, December 2020, doi: 10.1587/transinf.2020PAP0002.
Abstract: The volume of digital information is growing at an extremely fast pace which, in turn, exacerbates the need of efficient mechanisms to find the presence of a pattern in an input text or a set of input strings. Combining the processing power of Graphics Processing Unit (GPU) with matching algorithms seems a natural alternative to speedup the string-matching process. This work proposes a Parallel Rabin-Karp implementation (PRK) that encompasses a fast-parallel prefix-sums algorithm to maximize parallelization and accelerate the matching verification. Given an input text T of length n and p patterns of length m, the proposed implementation finds all occurrences of p in T in O(m+q+n/τ+nm/q) time, where q is a sufficiently large prime number and τ is the available number of threads. Sequential and parallel versions of the PRK have been implemented. Experiments have been executed on p≥1 patterns of length m comprising of m=10, 20, 30 characters which are compared against a text string of length n=227. The results show that the parallel implementation of the PRK algorithm on NVIDIA V100 GPU provides speedup surpassing 372 times when compared to the sequential implementation and speedup of 12.59 times against an OpenMP implementation running on a multi-core server with 128 threads. Compared to another prominent GPU implementation, the PRK implementation attained speedup surpassing 37 times.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020PAP0002/_p
Copier
@ARTICLE{e103-d_12_2412,
author={Lucas Saad Nogueira NUNES, Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={A Rabin-Karp Implementation for Handling Multiple Pattern-Matching on the GPU},
year={2020},
volume={E103-D},
number={12},
pages={2412-2420},
abstract={The volume of digital information is growing at an extremely fast pace which, in turn, exacerbates the need of efficient mechanisms to find the presence of a pattern in an input text or a set of input strings. Combining the processing power of Graphics Processing Unit (GPU) with matching algorithms seems a natural alternative to speedup the string-matching process. This work proposes a Parallel Rabin-Karp implementation (PRK) that encompasses a fast-parallel prefix-sums algorithm to maximize parallelization and accelerate the matching verification. Given an input text T of length n and p patterns of length m, the proposed implementation finds all occurrences of p in T in O(m+q+n/τ+nm/q) time, where q is a sufficiently large prime number and τ is the available number of threads. Sequential and parallel versions of the PRK have been implemented. Experiments have been executed on p≥1 patterns of length m comprising of m=10, 20, 30 characters which are compared against a text string of length n=227. The results show that the parallel implementation of the PRK algorithm on NVIDIA V100 GPU provides speedup surpassing 372 times when compared to the sequential implementation and speedup of 12.59 times against an OpenMP implementation running on a multi-core server with 128 threads. Compared to another prominent GPU implementation, the PRK implementation attained speedup surpassing 37 times.},
keywords={},
doi={10.1587/transinf.2020PAP0002},
ISSN={1745-1361},
month={December},}
Copier
TY - JOUR
TI - A Rabin-Karp Implementation for Handling Multiple Pattern-Matching on the GPU
T2 - IEICE TRANSACTIONS on Information
SP - 2412
EP - 2420
AU - Lucas Saad Nogueira NUNES
AU - Jacir Luiz BORDIM
AU - Yasuaki ITO
AU - Koji NAKANO
PY - 2020
DO - 10.1587/transinf.2020PAP0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2020
AB - The volume of digital information is growing at an extremely fast pace which, in turn, exacerbates the need of efficient mechanisms to find the presence of a pattern in an input text or a set of input strings. Combining the processing power of Graphics Processing Unit (GPU) with matching algorithms seems a natural alternative to speedup the string-matching process. This work proposes a Parallel Rabin-Karp implementation (PRK) that encompasses a fast-parallel prefix-sums algorithm to maximize parallelization and accelerate the matching verification. Given an input text T of length n and p patterns of length m, the proposed implementation finds all occurrences of p in T in O(m+q+n/τ+nm/q) time, where q is a sufficiently large prime number and τ is the available number of threads. Sequential and parallel versions of the PRK have been implemented. Experiments have been executed on p≥1 patterns of length m comprising of m=10, 20, 30 characters which are compared against a text string of length n=227. The results show that the parallel implementation of the PRK algorithm on NVIDIA V100 GPU provides speedup surpassing 372 times when compared to the sequential implementation and speedup of 12.59 times against an OpenMP implementation running on a multi-core server with 128 threads. Compared to another prominent GPU implementation, the PRK implementation attained speedup surpassing 37 times.
ER -