论文部分内容阅读
随着多核、众核处理器成为计算设备的主流,模式识别在未来并行系统中的实现将需要对应的并行算法研究作为其理论基础。另一方面,基于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的其他现有实现方案进行了比较。