Clgrep: A Parallel String Matching Tool

gpgpu;stringmatching

Peng, Wu ; Nowostawski, Mariusz

University of Otago

关键词: gpgpu;    stringmatching;   

Others  :  https://ourarchive.otago.ac.nz/bitstream/10523/4001/5/PengWu2013MSc.pdf

美国|英语

来源: Otago University Research Archive

【 摘 要 】

In this study, we widely investigate the problem of string matching in thecontext of Heterogeneous Parallel Computing. A overview of string match- ing is made, in which the different forms of string matching problem are distinguished, and the classifications of string matching algorithm are discussed.As an alternative to grep for computational intensive string matching and inaddition to support the research of the study, a parallel exact string matching utility;;Clgrep’ is developed.By experimental studies, we investigate the use of heuristics-based algo- rithms, specifically QS and Horspool algorithms, in the context of Het- erogeneous Parallel Computing. The results suggest that the performance of Heterogeneous Parallel Computing matching, either on multi-core CPU or GPU, is highly related to the computational intensity of certain cases. When computational power is intensively required, the SIMD Parallel Com- puting model of Clgrep can be several times more efficient than correspond- ing sequential matching program.