| Title |
High Throughput Parallel KMP Algorithm Considering CPU-GPU Memory Hierarchy |
| Authors |
박소은(Soeun Park) ; 김대희(Daehee Kim) ; 이명호(Myungho Lee) ; 박능수(Neungsoo Park) |
| DOI |
http://doi.org/10.5370/KIEE.2018.67.5.656 |
| Keywords |
KMP algorithm ; GPGPU ; OpenCL |
| Abstract |
Pattern matching algorithm is widely used in many application fields such as bio-informatics, intrusion detection, etc. Among many string matching algorithms, KMP (Knuth-Morris-Pratt) algorithm is commonly used because of its fast execution time when using large texts. However, the processing speed of KMP algorithm is also limited when the text size increases significantly. In this paper, we propose a high throughput parallel KMP algorithm considering CPU-GPU memory hierarchy based on OpenCL in GPGPU (General Purpose computing on Graphic Processing Unit). We focus on the optimization for the allocation of work-times and work-groups, the local memory copy of the pattern data and the failure table, and the overlapping of the data transfer with the string matching operations. The experimental results show that the execution time of the optimized parallel KMP algorithm is about 3.6 times faster than that of the non-optimized parallel KMP algorithm. |