Lei Li
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
Yuwan Gu
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
Yanyan Guo
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
Kemeng He
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
Yan Chen
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
Yuqiang Sun
ChangZhou University International Institute of Ubiquitous Computing, Jiangsu, 213164, Changzhou, China
ABSTRACT
Research a master-slave duplex layer structure exact string matching parallel algorithm on the homogeneous PC cluster platform. Making use of the KMP main string mismatching irrelevant feature to construct secondary KR substring and then calculate the value of next function quickly. Using PC Cluster Message Passing Interface (MPI) parallel platforms and for the balanced load of each node processes which involved in computing, an anti-missing methods was proposed to do overlapped block with the target dictionary. The paralleled implementation process of hierarchical nested exact string matching algorithm was discussed in detail. The experiment demonstration is conducted on the homogeneous PC cluster platform, analyzing the parallel processing efficiency of data traffic on different levels under the condition of the intervention of multi nodes. Experimental results show that the algorithm has a high parallel efficiency and linear acceleration was obtained and has good scalability.
PDF References
How to cite this article
Lei Li, Yuwan Gu, Yanyan Guo, Kemeng He, Yan Chen and Yuqiang Sun, 2013. Research on Homogeneous Cluster-based Hierarchical Nested String Matching Parallel Algorithm. Information Technology Journal, 12: 2857-2862.
DOI: 10.3923/itj.2013.2857.2862
URL: https://scialert.net/abstract/?doi=itj.2013.2857.2862
DOI: 10.3923/itj.2013.2857.2862
URL: https://scialert.net/abstract/?doi=itj.2013.2857.2862
REFERENCES
- Du, X.L., C.J. Jiang, G.R. Xu and Z.J. Ding, 2006. A grid DAG scheduling algorithm based on fuzzy clustering. J. Software, 17: 2277-2288.
Direct Link - Li, X., Z.P. Zhi, L. Ju, Y.H. Zhao and Z.L. Zong, 2012. Energy efficient scheduling and optimization for parallel tasks on homogeneous clusters. Chin. J. Comput., 35: 591-602.
Direct Link - Rantonen, M., T. Frantti and K. Leiviska, 2010. Fuzzy expert system for load balancing in symmetric multiprocessor systems. Expert Syst. Applic., 37: 8711-8720.
CrossRef - Bille, P., I.L. Gortz, H.W. Vildhoj and D.K. Wind, 2012. String matching with variable length gaps. Theor. Comput. Sci., 443: 25-34.
CrossRef - Tu, B.B., M. Zou, J.F. Zhan, X.F. Zhao and J.P. Fan, 2008. Research on parallel computation model with memory hierarchy on multi-core clusters. J. Software, 31: 1948-1955.
Direct Link - Zong, Z.L., A. Manzanares, X.J. Ruan and X. Qin, 2011. EAD and PEBD: Two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters. IEEE Trans. Comput., 60: 360-374.
CrossRef