La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

A Rabin-Karp Implementation for Handling Multiple Pattern-Matching on the GPU Une implémentation Rabin-Karp pour gérer plusieurs correspondances de modèles sur le GPU

Lucas Saad Nogueira NUNES, Jacir Luiz BORDIM, Yasuaki ITO, Koji NAKANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.12 pp.2412-2420
Date de publication
2020/12/01
Publicisé
2020/09/24
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2020PAP0002
Type de manuscrit
Special Section PAPER (Special Section on Parallel, Distributed, and Reconfigurable Computing, and Networking)
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Lucas Saad Nogueira NUNES
  University of Brasilia
Jacir Luiz BORDIM
  University of Brasilia
Yasuaki ITO
  Hiroshima University
Koji NAKANO
  Hiroshima University

Mots-clés

Table des matières