Investigation of GPU-based Pattern Matching
Department of Electronic & Electrical Engineering, University of Strathclyde, Glasgow, G1 1XW, UK
14th Annual Post Graduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting (PG Net 2013), 2013
@article{bellekens2013investigation,
title={Investigation of GPU-based Pattern Matching},
author={Bellekens, X and Andonovic, I and Atkinson, RC and Renfrew, C and Kirkham, T},
year={2013}
}
Graphics Processing Units (GPUs) have become the focus of much interest with the scientific community lately due to their highly parallel computing capabilities, and cost effectiveness. They have evolved from simple graphic rendering devices to extremely complex parallel processors, used in a plethora of scientific areas. This paper outlines experimental results of a comparison between GPUs and general purpose CPUs for exact pattern matching. Specifically, a comparison is conducted for the Knuth-Morris-Pratt algorithm using different string sizes, alphabet sizes and introduces different techniques such as loop unrolling, and shared memory using the Compute Unified Device Architecture framework. Empirical results demonstrate nearly a 30 fold increase in processing speed where GPUs are used instead of CPUs.
June 17, 2013 by hgpu
