Parallel Algorithms Of Pattern Recognition And Gpu High-speed Implementation

As multi-core and many-core processors have become the main stream of computing systems, it is necessery to research the parallel form of pattern recognition algorithms for realizations on future parallel systems. On the other hand, GPU general purpose computing based on CUDA is able to provide strong computing ability and high memory band width, and has a good performance on programmability, cost and development cycle. Accordingly, the research of parallel algorithms for pattern recognition and their CUDA implementations have an important practical significance.This dissertation analyzes the Tesla GPU graphics and computing architecture, and the CUDA computing unified device architecture. It described how to decompose a compute work load to parallel form, and map it to Tesla GPU through the leveled programming model of CUDA.In the implement part of this dissertation, according to the software development process, it tells how to implement three classic pattern recognition algorithms using CUDA. The algorithms are: Singular Value Decomposition (SVD) for feature extraction, Kernel-based Fuzzy C-Means (KFCM) nearest neighbor algorithm, and the Aho-Corasick multi-pattern matching algorithm.SVD is widely used as a powerful tool of matrix analysis and calculation in the fields include but not limited to statistical analysis, signal processing, image processing, system theory and control.This dissertation discusses the numerical algorithms for SVD, and implements the one-sided Jacobi method on GPU. Based on the analysis of the result of one-sided Jacobi method, it gives a improved SVD method, and validate its effectiveness.FCM (Fuzzy C-Means) is the most widely used fuzzy clulster algorithm, which has been successfully applied in many fileds. KFCM is a variant of FCM, improved the classifiability of clusters by employing kernel functions.Multi-pattern matching has many important applications in the fileds include but not limited to pattern recongniton, bio-computing, search engine, anti virus and invasion detection. AC multi-pattern matching is one of the most widely used multi-pattern matching algorithms.The parallel form and CUDA implementation for KFCM and Aho-Corasick algorithm is discussed, validated by test result, and compared with CPU and FPGA implementations.