Acceleration Of Pattern Matching Algorithms On Many-Core Hardware

In recent years, with the development of the network, the explosive increase trend has been seen in the data of all walks of life. The global amount of digital information was predicted by IDC to reach to an astonishing35ZB by2020, which will consequently lead to that the regulation of the information content will be confronted with enormous challenges. Pattern matching algorithm is a fundamental and important algorithm in text processing field, which is generally applied in various of fields such as network intrusion detection, bioinformatics, image processing, etc.Large amounts of CPU resources and storage resources need to be consumed in the pattern matching algorithm based on software so that the actual performance of the system is low. Therefore, it is imperative to adopt the hardware with high performance to handle huge amounts of data. GPU has been used to accelerate pattern matching algorithm performance which is a kind of many-core programmable hardware with super power to do parallel computing. The purpose of this paper is to design and implement the pattern matching algorithm with high-efficiency through making full use of respective hardware features of GPU and CPU, combining the applicability of the pattern matching algorithm.The main achievements and contributions of this article are as follows:(1)Studied the pattern matching technologies. The exact pattern matching and the regular expression matching technologies were introduced in detail and the advantages and disadvantages of related algorithms were analyzed in this paper. (2)Proposed SPAC, which is a STT-Partition-based parallel algorithm for large scale precise pattern matching, implemented on GPU and CPU. The problem that the corresponding STT, which is generated by the pattern set, occupies too much memory of the GPU was solved in this algorithm. Experiments show that about50%of the GPU footprint of the STT is reduced by using the SPAC algorithm, whose effect is particularly obvious when dealing with large-scale precise pattern matching.(3)Proposed MDFA, which is a high-speed regular expression matching algorithm, implemented on GPU and CPU. The algorithm was implemented by this way that many sub-blocks of text were parallelly processed on GPU so that the borders of sub-blocks of text were further processed on CPU, thus, it is solved by this algorithm that there is "boundary issues" between the blocks during the text processing when the regular expression matching is implemented on GPU. It is showed by experiments that MDFA algorithm can efficiently reduce the comparison of redundant string between the adjacent work-group on GPU when the corresponding maximum matching string of regular expression set is longer or the maching length is limited to longer.