 |
Parallel Rabin-Karp Algorithm for String Matching using GPU |
 |
|
|
|
Parallel Rabin-Karp Algorithm for String Matching using GPU
Masoumeh Moeini
School of Electrical Engineering
Iran University of Science and Technology
Tehran, Iran |
Hadi Shahriar Shahhoseini
School of Electrical Engineering
Iran University of Science and Technology
Tehran, Iran |
PDF │ Abstract │ Keywords │ References │ Cite This
Abstract:
String matching algorithms play an important role in many aspects. In this paper, a new method is proposed for parallel execution of Rabin-Karp string matching algorithm. In the proposed method, all patterns are divided into different groups. This categorization has been used to prevent redundant comparisons and accelerate the matching process. This procedure takes two advantages: a reduction in the number of comparisons of hash values and a decline in the number of pattern reading from global memory. It is recommended to implement the algorithm in various cases on NVIDIA GPUs using CUDA Platform to demonstrate the efficiency of the proposed algorithm. Experimental results depict that the execution time of the algorithm has decreased significantly. In the best case, the proposed method is approximately 27 times faster than the series mode.
Keywords: String Matching Algorithm; Rabin-Karp Algorithm; GPU; Categorization
References:
[1] P. Rastogi and R. Guddeti, "GPU accelerated inexact matching for multiple patterns in DNA sequences," International Conference Advances in Computing on Communications and Informatics (ICACCI), pp. 163-167, 2014. doi: 10.1109/ICACCI.2014.6968404. Google Scholar
[2] D.R.V.L.B. Thambawita, R.G. Ragel and D. Elkaduwe, "An optimized Parallel Failure-less Aho-Corasick algorithm for DNA sequence matching," 2016 IEEE International Conference on Information and Automation for Sustainability (ICIAfS), Galle, 2016, pp. 1-6, doi: 10.1109/ICIAFS.2016.7946533. Google Scholar
[3] H. Naderi, H. S. Shahhoseini, A. H. Jafari, "Evaluation MCDM multi disjoint paths selection algorithms using fuzzy-copeland ranking method," International Journal of Communication Networks and Information Security, Vol. 5, No. 1, pp. 59-67, 2013. Google Scholar
[4] M.M. Bassiri, H.S. Shahhoseini, "Configuration reusing in on-line task scheduling for reconfigurable computing systems," Journal of Computer Science and Technology Vol. 26, No. 3, pp. 463-473, 2011. https://doi.org/10.1007/s11390-011-1147-2 Google Scholar
[5] M.M. Bassiri and H.S. Shahhoseini, "A New approach in on-line task scheduling for reconfigurable computing systems," ASAP 2010 - 21st IEEE International Conference on Application-specific Systems, Architectures and Processors, Rennes, 2010, pp. 321-324, doi: 10.1109/ASAP.2010.5540975. Google Scholar
[6] A. Tabatabaei, M.R. Mosavi, A. Khavari, H.S. Shahhoseini, "Reliable urban Canyon navigation solution in GPS and GLONASS integrated receiver using improved Fuzzy weighted Least-Square method," Wireless Personal Communications Vol. 94, No. 4, pp. 3181-3196, 2017.https://doi.org/10.1007/s11277-016-3771-1. Google Scholar
[7] H. Jamali Rad, M. Azarafrooz, H.S. Shahhoseini and B. Abolhassani, "A new adaptive power optimization scheme for target tracking Wireless Sensor Networks," 2009 IEEE Symposium on Industrial Electronics & Applications, Kuala Lumpur, 2009, pp. 307-312, doi: 10.1109/ISIEA.2009.5356452. Google Scholar
[8] B.M. Bidgoli, M. Analoui, M.H. Rezvani, H.S. Shahhoseini, "Performance evaluation of decision tree for intrusion detection using reduced feature spaces," Trends in Intelligent Systems and Computer Engineering, 2008 Lecture Notes in Electrical Engineering, Vol. 6, pp. 273-284 Springer, 2008. https://doi.org/10.1007/978-0-387-74935-8_20 Google Scholar
[9] M. Saeed and H.S. Shahhoseini, "APPMA - an Anti-phishing protocol with mutual Authentication," The IEEE symposium on Computers and Communications, Riccione, 2010, pp. 308-313, doi: 10.1109/ISCC.2010.5546794. Google Scholar
[10] T. AbuHmed, A. Mohaisen, and D. Nyang, "Deep packet inspection for intrusion detection systems: A survey," Magazine of Korea Telecommunication Society, Vol. 24, pp. 25-36, 2007. Google Scholar
[11] H.S. Shahhoseini, M. Naderi and R. Buyya, "Shared memory multistage clustering structure, an efficient structure for massively parallel processing systems," Proceedings Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, Beijing, China, 2000, pp. 22-27 vol.1, doi: 10.1109/HPC.2000.846510. Google Scholar
[12] C.S. Kouzinopoulos and K.G. Margaritis, "String Matching on a Multicore GPU Using CUDA," 2009 13th Panhellenic Conference on Informatics, Corfu, 2009, pp. 14-18, doi: 10.1109/PCI.2009.47. Google Scholar
[13] RR.M. Karp and M.O. Rabin, "Efficient randomized pattern-matching algorithms," in IBM Journal of Research and Development, vol. 31, no. 2, pp. 249-260, March 1987, doi: 10.1147/rd.312.0249. Google Scholar
[14] A.V. Aho and M.J. Corasick, "Efficient string matching: An aid to bibliographic search," Commun. ACM, Vol. 18, No. 6, pp. 333–340, Jun. 1975. Google Scholar
[15] R. S. Boyer and J. S. Moore, "A fast string searching algorithm," Commun. ACM, Vol. 20, No. 10, pp. 762–772, 1977. https://doi.org/10.1145/360825.360855 Google Scholar
[16] D.E. Knuth, J.H. Morris, and V.R. Pratt, "Fast pattern matching in strings," SIAM J. Comput., Vol. 6, No. 2, pp. 323–350, Jun. 1977. https://doi.org/10.1137/0206024 Google Scholar
[17] A. Tumeo, O. Villa, and D. Sciuto, "Efficient pattern matching on GPUs for intrusion detection systems," Proc. Seventh ACM Int’l Conf. Computing Frontiers, 2010. https://doi.org/10.1145/1787275.1787296 Google Scholar
[18] P.R. Jelenkovic, X. Kang and A. Radovanovic, "Near optimality of the discrete persistent access caching algorithm," DMTCS proc. AD, pp. 201–222, 2005. Google Scholar
[19] C. Lin, C. Liu, L. Chien and S. Chang, "Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs," in IEEE Transactions on Computers, vol. 62, no. 10, pp. 1906-1916, Oct. 2013, doi: 10.1109/TC.2012.254. Google Scholar
[20] C. Lin, S. Tsai, C. Liu, S. Chang and J. Shyu, "Accelerating String Matching Using Multi-Threaded Algorithm on GPU," 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, Miami, FL, 2010, pp. 1-5, doi: 10.1109/GLOCOM.2010.5683320. Google Scholar
[21] A. Rasool and N. Khare, "Parallelization of KMP string matching algorithm on different SIMD architectures: multi-core and GPGPU’s," Int. J. Comput. Appl., Vol. 49, No. 11, pp. 26–28, 2012. Google Scholar
[22] X. Zha and S. Sahni, "GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU," in IEEE Transactions on Computers, vol. 62, no. 6, pp. 1156-1169, June 2013, doi: 10.1109/TC.2012.61. Google Scholar
[23] N. Dayarathne and R. Ragel, "Accelerating Rabin Karp on a Graphics Processing Unit (GPU) using Compute Unified Device Architecture (CUDA)," 7th International Conference on Information and Automation for Sustainability, Colombo, 2014, pp. 1-6, doi: 10.1109/ICIAFS.2014.7069589. Google Scholar
[24] J. Sharma and M. Singh, "CUDA based Rabin-Karp pattern matching for deep packet inspection on a multicore GPU," International Journal Computer Network and Information Security, Vol. 10, pp. 70-77, 2015. Google Scholar
[25] Y. Tan and K. Ding, "A Survey on GPU-Based Implementation of Swarm Intelligence Algorithms," in IEEE Transactions on Cybernetics, vol. 46, no. 9, pp. 2028-2041, Sept. 2016, doi: 10.1109/TCYB.2015.2460261. Google Scholar
[26] NVIDIA Corporation, "NVIDIA CUDA C programming guide," Sep. 2015, pG-02829-001_v7.5. Google Scholar
[27] CUDA NVIDIA, "NVIDIA CUDA programming guide," (version 1.0), NVIDIA: Santa Clara, CA (2007). Google Scholar
Cite this paper as:
M. Moeini and H.S. Shahhoseini, "Parallel Rabin-Karp Algorithm for String Matching using GPU," 10th International Conference on Information and Knowledge Technology (IKT 2019), Tehran, Iran, 2019.
|
|
|
|
