Clgrep: A Parallel String Matching Tool
In this study, we widely investigate the problem of string matching in the context 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 in addition 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.
Advisor: Nowostawski, Mariusz
Degree Name: Master of Science
Degree Discipline: Information Science
Publisher: University of Otago
Keywords: gpgpu; stringmatching
Research Type: Thesis