论文部分内容阅读
相似度计算是计算机学科中一个重要的问题,其应用遍及多个领域,如互联网、数据挖掘以及生物信息学等。随着信息技术的发展,每时每刻都会产生庞大的数据,使得相似度计算在海量信息的快速检索中显得非常重要。为了适应数据的急剧增长,迫切需要利用高性能的计算平台对已有方法进行改进和加速。GPU具有强大的计算能力和高内存带宽,可以很好地满足相似度计算并行化的需求。此外,GPU拥有很高的性能/价格比和性能/功耗比,使得GPU成为搭建超级计算机的良好选择,而其低廉的价格也使其普遍出现在桌面计算机中。利用GPU平台对相似度计算的性能进行优化,一方面要解决相似度计算的高维、数据稀疏性、数据依赖性等问题,另一方面要考虑GPU内部架构、执行模式的特殊性和局限性,如多级存储层次有效利用、访存优化、线程负载均衡、规避线程分支等。对于不同的相似度计算方法,存在着不同的问题,相应的性能优化机制也会有所不一样。当利用稀疏矩阵向量乘算法来计算相似度时,其性能往往受限于计算平台的内存带宽。为了解决这个问题,一种基于混合存储的稀疏矩阵存储格式从一些经典稀疏矩阵存储格式的数据布局、数据处理策略和存储空间开销入手,分析潜在的存储格式发展方向,从而采用行交错合并的方式来减少存储空间的开销,其相应的稀疏矩阵向量乘处理过程采用分段处理的方式来控制负载均衡。结果表明,新的存储格式无论在计算性能方面还是在存储空间开销方面,都优于NVIDIA公司实现的多种稀疏矩阵格式。当利用矩阵奇异值分解来计算相似度时,传统QR迭代分解法耗时严重,并且难以使用GPU并行化。考虑到很多计算机配备了多核CPU和多个GPU,基于分而治之模型的奇异值分解方法能充分发挥此类平台所有计算资源的计算能力。该方法采用两级分而治之模型,使得GPU尽量处于忙碌状态,达到GPU资源的最大化利用;同时CPU与GPU协同计算使得多GPU平台中的空闲CPU核心也利用起来。结果表明基于两级分而治之模型的奇异值分解算法比较适合大规模的矩阵计算,并且能在多GPU平台达到良好的加速效果。针对Smith-Waterman算法需要大量的计算和内存空间,并且当实现于GPU平台时受限于全局内存的访问速度等问题,一种基于压缩的多线程处理方法能利用有限的GPU内存来进行物种的序列比对。该方法使Smith-Waterman算法的两个阶段连续地在GPU上执行,提供所有比对序列的相似度和最优匹配片段。此外,该方法能满足生物学家对其研究领域内的一个或多个物种进行比对的需求。结果表明,对于中等规模的数据库,该方法能取得优于使用Ssearch回溯的CUDASW++2.0和DOPA。为加快大规模信息数据的相似拷贝检测,一种结合simhash与汉明距离的检测方法使用GPU平台并行执行。该方法包含三个内核,分别为指纹生成内核、候选指纹筛选内核和汉明距离计算内核。为了适应GPU平台,该方法采用两种优化策略:数据缓存策略可以减少全局内存的访问次数、内存动态分配策略用来改善内存的使用状况和后续线程的分配。结果表明,该GPU实现方案能达到很好的加速效果。综上所述,通过对若干相似度计算关键技术进行GPU并行化研究,形成了一些GPU通用计算的共通模式和优化策略,从而为更多其它类型的算法向GPU平台移植提供支持和依据,对于相似度计算和GPU在通用计算领域的发展都具有重大的研究意义。