论文部分内容阅读
字符串相似性匹配是计算机领域最基础的技术之一,被广泛应用于网络安全、信息检索等领域,同时还被广泛应用于生物学信息处理,文本词根识别等应用。然而随着网络发展的日新月异,网络数据流量成倍增加以及匹配要求从精确匹配到模糊匹配的日益复杂。字符串的匹配处理速度慢,不足以适应当今大规模数据集任务的要求,迫切需要提出新的更有效以及质量更高的算法来满足大规模数据集的处理需求。当今GPU(图形处理器)更新换代提速,GPU功能越来越强大。NVIDIA公司于2007年推出CUDA(Compute Unified Device Architecture)架构,使显卡用于解决图像计算以外的任务。CUDA这一新的基础架构可以用来解决工业、商业以及科学计算方面的复杂问题。采用CUDA具有众多优点：便宜的价格,高效并行性,高密集运算,超长流水线。现在CPU+GPU(中央处理器+图形处理器)异构处理平台已逐渐成为主流的并行解决方案。本文旨在利用CPU+GPU异构处理平台的高效并行能力,更为有效的进行大规模数据集处理。本论文首先概述基于字符串核函数的SVM(支持向量机)的广泛应用及面临的挑战,同时论述了GPU的架构特点以及NVIDIA推出的专用平台CUDA(the Compute Unified Device Architecture,计算统一设备框架),详细论述了CUDA中线程的调度、内存的种类以及分配和充分发挥GPU计算能力的原则,并回顾了国内外基于CUDA的字符串处理研究。其次本文对经典的字符串核函数算法一一编辑距离核函数(Edit Distance Kerne)、p频谱核函数(P-spectrum Kernel)、序列间隔加权核函数(Gap-Weighted Subsequence Kernel1一一进行了GPU并行优化,结合CPU+GPU异构平台的特点将上述核函数算法使用CUDA平台并行化向GPU移植。使用Reuters-21578和SpamAssassin公共语料库对本文的gpuSKSVM进行评估,三种核函数的计算获得了比原系统7-33倍的速度提升。