Abstract

Graphics Processing Units (GPUs) were developed for graphics processing and it was not highly-parallel. But to overcome this problem developed General Purpose Computing on GPU, this is known as GPGPU.Boyer-Moore exact string matching algorithm are heavily used in the application of antivirus engines, DNA sequencing, text editors, intrusion detection etc. In this environment, the GPU was highly-parallel, multithreaded. In this Paper extend the GPU application into other area such as string matching problem. This paper shows the results on adapting the enhanced Boyer-Moore (EBM) string matching algorithm to run on GPU paradigm and comparison with serial version and multithreaded version on CPU.The experimental results demonstrate that GPU version of enhanced Boyer-Moore (EBM) string matching algorithm 10 times faster than CPU version and 9 times faster than the multithreaded version. It can be also see there that multithreaded version of EBM algorithm about 12% to 13% peak performance than serial version of EBM.Speedup of EBM algorithm is grow and 12x to 13x than serial one.

References

• Cheng-Hung Lin, Sheng-Yu Tsai, Chen-Hsiung Liu, Shih Chieh Chang, Jyuo-Min Shyu," Accelerating string matching using multi-threaded algorithm on GPU", IEEE Globecom 2010.
• Kenneth Ryan VeriSign Labs, "An Evaluation of GPUs for Accelerating a Selected String Searching Algorithm",21345 ridge top circle,Dulles,VA 20152.
• Charalampos S. Kouzinopoulos and Konstantinos G. Margaritis," String Matching on a multicore GPU using CUDA", 2009 13th Pan-Hellenic Conference on Informatics.
• Jiangfeng Peng,Hu Chen,"CUgrep:A GPU-based high Performance Multi-String Matching System"2010 IEEE:V1-77 to V1-81
• Lingling yuan,"An improved algorithm for Boyer-Moore string Matching Chinese Information Processing" , IEEE. pp. 182-184,2011.
• Zhengda Xiong,"A composite Boyer-Moore Algorithm for the string Matching Problem" IEEE. pp. 492-496,2010.
• Xingxing Wang," A BM algorithm oriented on Network Security Audit System" IEEE. 978-1-4244-5895, 2010.
• Yang Tong, Qiao Xiang-dong, "Analyze and Improvement of BM Algorithm" IEEE: 978-1-4244-3693, 2009.
• Prasad JC, Dr. K. S. M. Panicker,"Single Pattern Search Implementations in a Cluster Computing Environment" , IEEE. pp391-396,2010.
• Knuth,D. E,Morries,Jr. ,J. H. ,and pratt,V. B. " fast pattern matching in string SIAM J. comptng. 6,2(1977),pp323-350.
• Yuting Han, Guoai Xu "Improved algorithm of pattern matching based on BMHS", IEEE. pp238-241,2010.
• Zhu Yong giang,"Two enhanced BM algorithm in pattern matching", IEEE. pp341-346,2011.
• Yihui SHAN, Yuming JIANG, Shiyuan TIAN, "Improved Pattern Matching Algorithm of BMHS for Intrusion Detection". Computer Engineering, vol. 35, 2009, pp. 170-173
• Zhanjun REN, Quanzhu YAO, Xiaofeng WANG, Youjiao ZOU,"Application of Pattern Matching Algorithm in Intrusion Detection Technique". Modern electronic technology, vol. 2, 2009, pp. 63-67
• Baishuhong. Eason, An Improvement on BM Algorithm for Chinese, fujiandiannao, pp. 90–91, October. 2009.