Implementation Of String Matching Algorithm Based On GPU

With the achievement of IC(Integrated Circuit) technology, GPU(Graphics ProcessingUnit) is becoming very powerful. Recently, a typical shading program running on the GPU canreach the peak performance of 20GFLOPS and the memory bandwidth of 25.3GB/sec, whichis much better than that of the CPU. For sake of such huge potential computing capability,more and more applications are trying to port their computing tasks to the GPU. Utilizing theGPU as a SIMD stream processor for general purpose computations, it has become a topic ofconsiderable interest nowadays. The GPU could become an efficient co-processor of the CPU,gaining the high performance price ratio.The string matching algorithm is a basic algorithm in the bioinformatics and informationsearching fields. With the bombing growing of the gene data and web data, the need for highperformance string matching algorithms is growing. But the string matching algorithms havethe data dependency problems, which badly restrict the efficiency in CPU.This thesis is concentrated on the system architecture of the GPU, studying the efficientlyprogramming methods on the GPU, developing the data parallellism of the string matchingalgorithms, and the charicteristics of general algorithms which are suitable to be ported to theGPU.The main tasks of the thesis include:(1) The thesis does the research on the system architecture and programming methods ofthe GPU, such as OpenGL, BROOK, CG, and the improvement approach of the data accesspattern. By utilizing the texture data structure in graphics processing elements, the datastructures in general computations, such as the string files in string matching algorithms, aremapped into the GPU. And the algorithms in GPU are also designed on the basis of texture.(2) BF algorithm is the basic algorithm in string matching field. But it is not paralleled,and does not match the system architecture of the GPU. Concerning the specific hardwarearchitecture of the GPU, a new method of data accessing and a parallel BF algorithm aredesigned. Because of fully utlizing the parallelism of the GPU, the experiments show that theapplication in the GPU can speed up much compared with that in the CPU.(3) Based on the BF string matching algorithm on GPU as a case study, the performanceimprovement approach is studied on the GPU. The performance influence factores of thealgorithm on the GPU are analyzed, and the possible bottlenecks of nowadays GPUarchitectures are studied. Also some conclusions of the characteristics of general algorithms,which can be performed on the GPU efficiently, are reached.