Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Efficient Parallel Knuth-Morris-Pratt Algorithm for Multi-GPUs with CUDA
verfasst von : Kuan-Ju Lin, Yi-Hsuan Huang, Chun-Yuan Lin
Erschienen in: Advances in Intelligent Systems and Applications - Volume 2
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
String matching is an important technique among various applications. The traditional string matching algorithm needs the backtracking procedure and does the comparison repeatedly, thus these factors affect its efficiency. Knuth-Morris-Pratt (KMP) is one of well-known and efficient string matching algorithms. However, the computation time of KMP algorithm still is large for processing thousands of pattern strings. Current high-end graphics processing units (GPUs), contain up to hundreds cores per chip, are very popular in the high performance computing community. In this paper, we proposed an efficient parallel KMP algorithm, called KMP-GPU, for multi-GPUs with CUDA. The experimental results showed that the proposed KMP-GPU algorithm can achieve 97x speedups compared with the CPU-based KMP algorithm.