The Research And Implementation Of String Matching Algorithm On CPU+GPU Platform

String matching is one of the most pervasive and most widely studied technologies in computer science. Nowadays, its related applications can be found everywhere. Especially in the fields of information retrieval and network security, string matching has played a significant role to the developing of society and science. However, with the text size increasing drastically and more sophisticated searching should be implemented, string matching is in urgent need for adopting new technology to design more efficient and high-quality algorithms to meet the needs of large-scale applications.Meanwhile, the CPU+GPU (central processing unit + graphic processing unit) heterogeneous processing platform has become the popular parallel solution in solving high performance computing applications. GPU greatly outpaces CPU in both arithmetic throughput and memory bandwidth side. On the other side, CPU has the huge advantage in instruction executing and scheduling. This paper aims at analysing classic string matching algorithms and designing the high performance parallel string matching algorithm through exploiting the high-parallel capacity of CPU+GPU platform. Furthemore, we implement the algorithm on each application to meet the needs of social development.Firstly, this paper introduced the widely applications and chanllenges of string matching, and the related research of GPU based string matching on world. Then we described the features of GPU's framework, which includes CUDA (the Compute Unified Device Architecture). Furthermore, in order to exploit the advantages of GPU, we studied the skills about how to dispatch the threads and memory by using CUDA.Secondly, through researching on classic multi-string matching algorithm, the AC (Aho-Corasick) algorithm, we proposed GAC (GPU-based Aho-Corasick) algorithm, which is the advanced parallel algorithm of AC. Then base on GAC, the webpage matching system enhances 28 times speedup than the original system.Finally, this paper developed the high performance regular expression matching system, GFlex (GPU-based Flex), on CPU+GPU platform. The system designed some advanced technologies such as extended table, data parallel and pipeline etc, which make the system obtains a high speed even than the parallel system on CPU.