The search functionality is under construction.

The search functionality is under construction.

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*=2^{27}. 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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.12 pp.2412-2420

- Publication Date
- 2020/12/01

- Publicized
- 2020/09/24

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2020PAP0002

- Type of Manuscript
- Special Section PAPER (Special Section on Parallel, Distributed, and Reconfigurable Computing, and Networking)

- Category
- Fundamentals of Information Systems

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.

Copy

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*=2^{27}. 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

Copy

@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*=2^{27}. 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},}

Copy

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*=2^{27}. 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 -