資源描述：
《面向CPU-GPU異構(gòu)平臺的生物多序列比對算法的性能優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、面向CPU-GPU異構(gòu)平臺的生物多序列比對算法的性能優(yōu)化ParallelOptimizationforMultipleSequenceAlignmentBasedonCPU-GPUHeterogeneousSystem學(xué)科專業(yè)：計算機(jī)科學(xué)與技術(shù)作者姓名：陳曦指導(dǎo)教師：于策副教授天津大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2017年11月摘要多序列比對（MSA）是一個在生物信息分析領(lǐng)域的經(jīng)典和廣泛應(yīng)用的技術(shù)。隨著生物數(shù)據(jù)集規(guī)模的急速增長，為了嚴(yán)格控制執(zhí)行時間，提高系統(tǒng)效率，對多序列比對的優(yōu)化研究成為重要的課題。在單用戶多序列比對場景下，很多研究工作忽略了在序
2、列個數(shù)和長度上規(guī)模都較大的數(shù)據(jù)集，而且較少考慮基因序列的高相似度問題。另外，在之前的多序列比對并行研究工作中，只考慮到GPU的并行加速能力，較少關(guān)注空閑的CPU資源。對此，本文提出CMSA，一個處理大規(guī)模高相似度的生物序列比對問題的，利用CPU-GPU混合架構(gòu)并行優(yōu)化的系統(tǒng)。CMSA將Center-Star算法的第一步驟的時間復(fù)雜度從O(mn2)降至O(mn)；不需用戶設(shè)定，自動根據(jù)硬件條件進(jìn)行任務(wù)分配，參數(shù)設(shè)定等以達(dá)到最佳優(yōu)化效果；充分利用CPU和GPU的計算資源，使兩者協(xié)同合作。實驗結(jié)果顯示在一塊GPUK40C的單節(jié)點環(huán)境中，CMSA在
3、保證準(zhǔn)確度的情況下，相比串行的研究成果HAlign可達(dá)到11倍以上的加速比。在多用戶多序列比對場景下，由于多序列比對算法的復(fù)雜性，如何高效處理多用戶任務(wù)更是對整體系統(tǒng)提出了巨大挑戰(zhàn)。對此，本文提出GMSA，一個針對多用戶的多序列比對系統(tǒng)。GMSA關(guān)注多用戶提交的具有相同數(shù)據(jù)和子任務(wù)的情況，提出基于共享思想的優(yōu)化策略。GMSA基于ClustalW算法，針對其第一步驟的時間復(fù)雜度較高的問題，通過共享第一步驟結(jié)果避免重復(fù)計算，從而縮短了計算時間。實驗結(jié)果顯示GMSA在保證準(zhǔn)確度的情況下，相比不采取共享思想的多序列比對軟件CUDA-ClustalW
4、，在用戶數(shù)量在12及以上時可達(dá)到32倍以上的加速效果。綜上，本文主要針對大規(guī)模、高相似度基因的多序列比對問題，研究CPU-GPU混合架構(gòu)軟硬件技術(shù)、設(shè)計最大化系統(tǒng)資源利用率的CPU-GPU混合架構(gòu)模型。另外，考慮到多用戶任務(wù)的復(fù)雜性，基于共享策略，提出可行的優(yōu)化策略。關(guān)鍵詞：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
