模式识别并行算法与GPU高速实现研究

【作者】 张舒；

【导师】 窦衡；

【作者基本信息】 电子科技大学 ， 信息与通信工程， 2009， 硕士

【摘要】 随着多核、众核处理器成为计算设备的主流,模式识别在未来并行系统中的实现将需要对应的并行算法研究作为其理论基础。另一方面,基于GPU的通用计算能够提供强大的计算能力和存储器带宽,同时具有良好的可编程性,较低的成本和较短的开发周期。因此,模式识别并行算法与GPU高速实现研究,对高速并行模式识别系统的建立、完善和推广具有重要的意义。本文详细分析了Tesla GPU图形与计算架构和CUDA统一计算设备架构,详细描述了如何对计算任务进行并行分解,并通过CUDA的双层并行编程模型映射到Tesla GPU上。在本文的实现部分,以软件开发流程为主线,描述了如何利用CUDA实现模式识别中的三种常用算法:特征提取中的奇异值分解(Singular Value Decomposition,SVD)、近邻法中的核模糊C均值聚类(Kernel-based Fuzzy C-means, KFCM)和AC(Aho-Corasick)多模式匹配算法。奇异值分解作为矩阵计算、分析的强大工具之一,在统计分析、信号与图象处理、系统理论和控制中被广泛地应用。本文分析了SVD算法的常用数值算法,并比较了各算法在CUDA实现的可行性,从中选择了单边雅可比算法作为基于CUDA的SVD实现基础。在分析单边雅可比算法不足的基础上,提出了一种改进的SVD算法,并以测试结果说明了改进手段的有效性。模糊C均值(FCM, Fuzzy C-Means)算法是模糊聚类最流行和应用最广泛的一种算法,在许多领域都取得了非常成功的效果,核模糊C均值算法(KFCM)在FCM的基础上进行了改进,通过引入核函数提高了类别间的可分性。多模式匹配算法在模式识别、生物计算、搜索引擎、病毒防治、入侵检测等领域有许多重要应用。AC算法是目前使用较广的一种多模式匹配算法。本文针对KFCM算法和AC算法进行了讨论,给出了它们的数据并行形式和CUDA实现方案,以测试结果验证了并行算法的设计,并与基于CPU和FPGA的其他现有实现方案进行了比较。更多还原

【Abstract】 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.更多还原