面向CPU-GPU异构平台的生物多序列比对算法的性能优化

《面向CPU-GPU异构平台的生物多序列比对算法的性能优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、面向CPU-GPU异构平台的生物多序列比对算法的性能优化ParallelOptimizationforMultipleSequenceAlignmentBasedonCPU-GPUHeterogeneousSystem学科专业：计算机科学与技术作者姓名：陈曦指导教师：于策副教授天津大学计算机科学与技术学院2017年11月摘要多序列比对（MSA）是一个在生物信息分析领域的经典和广泛应用的技术。随着生物数据集规模的急速增长，为了严格控制执行时间，提高系统效率，对多序列比对的优化研究成为重要的课题。在单用户多序列比对场景下，很多研究工作忽略了在序

2、列个数和长度上规模都较大的数据集，而且较少考虑基因序列的高相似度问题。另外，在之前的多序列比对并行研究工作中，只考虑到GPU的并行加速能力，较少关注空闲的CPU资源。对此，本文提出CMSA，一个处理大规模高相似度的生物序列比对问题的，利用CPU-GPU混合架构并行优化的系统。CMSA将Center-Star算法的第一步骤的时间复杂度从O(mn2)降至O(mn)；不需用户设定，自动根据硬件条件进行任务分配，参数设定等以达到最佳优化效果；充分利用CPU和GPU的计算资源，使两者协同合作。实验结果显示在一块GPUK40C的单节点环境中，CMSA在

3、保证准确度的情况下，相比串行的研究成果HAlign可达到11倍以上的加速比。在多用户多序列比对场景下，由于多序列比对算法的复杂性，如何高效处理多用户任务更是对整体系统提出了巨大挑战。对此，本文提出GMSA，一个针对多用户的多序列比对系统。GMSA关注多用户提交的具有相同数据和子任务的情况，提出基于共享思想的优化策略。GMSA基于ClustalW算法，针对其第一步骤的时间复杂度较高的问题，通过共享第一步骤结果避免重复计算，从而缩短了计算时间。实验结果显示GMSA在保证准确度的情况下，相比不采取共享思想的多序列比对软件CUDA-ClustalW

4、，在用户数量在12及以上时可达到32倍以上的加速效果。综上，本文主要针对大规模、高相似度基因的多序列比对问题，研究CPU-GPU混合架构软硬件技术、设计最大化系统资源利用率的CPU-GPU混合架构模型。另外，考虑到多用户任务的复杂性，基于共享策略，提出可行的优化策略。关键词：GPU，CUDA，混合，多用户，共享，生物序列比对IABSTRACTThemultiplesequencealignment(MSA)isaclassicalandpowerfultechniqueforsequenceanalysisinbioinformatics.

5、Withtherapidgrowthofbiologicaldatasets,MSAparallelizationbecomesnecessarytokeepitsrunningtimeinanacceptablelevel.Inthescenarioofsingleuseronmultiplesequencealignment,althoughthereareanumberofworkonMSAproblems,thelarge-scaledatasetsincludingthesizesofdatasetsandthelengthsof

6、sequencesareunfortunatelyignoredbylotsofpreviouswork.Besides,priorstudiesconsidertheMSAparallelizationonGPUdevicesonly,makingtheCPUsidleduringthecomputation.Thus,thispaperaimsattheproblemsaboveandpresentsCMSA,arobustandefficientMSAsystemforlarge-scaledatasetsontheheterogen

7、eousCPU-GPUplatform.Itperformsandoptimizesmultiplesequencealignmentautomaticallyforusers’submittedsequenceswithoutanyassumptions.CMSAadoptstheco-runcomputationmodelsothatbothCPUandGPUdevicesarefullyutilized.Moreover,CMSAproposesanimprovedcenterstarstrategythatreducesthetim

8、ecomplexityofitscentersequenceselectionprocessfromO(mn2)toO(mn).Theexperimentalresultssho