基于混合并行計(jì)算的遺傳退火多序列比對(duì)算法研究.pdf

1、信息技術(shù)的高速發(fā)展使得生物序列數(shù)據(jù)呈爆炸性增長(zhǎng),如何高效處理和分析這些海量數(shù)據(jù),是當(dāng)前要面對(duì)的一個(gè)挑戰(zhàn)。序列比對(duì)是生物信息分析最基本的處理方法,由于比對(duì)過(guò)程耗時(shí)極大,利用并行計(jì)算技術(shù)對(duì)計(jì)算加速成為重要研究課題。而混合并行模型是近年來(lái)通用并行計(jì)算平臺(tái)的新熱點(diǎn),它可充分發(fā)揮并行系統(tǒng)的綜合計(jì)算能力。因此結(jié)合基于消息傳遞MPI、共享內(nèi)存的OpenMP和CUDA并行編程模型,實(shí)現(xiàn)基于多機(jī)、多核CPU、眾核GPU的并行模型,將該模型應(yīng)用于序列比對(duì)研

2、究是一個(gè)很有前景的研究方向。
　　基于遺傳模擬退火多序列比對(duì)(GSA-MSA)算法是全局比對(duì)算法,論文主要對(duì)混合并行下的GSA-MSA算法進(jìn)行并行化研究。為了實(shí)現(xiàn)并行加速,對(duì)混合并行系統(tǒng)的硬件架構(gòu)、執(zhí)行模型、混合編程編譯方法和并行性能指標(biāo)等進(jìn)行詳細(xì)研究,剖析GSA-MSA算法的實(shí)現(xiàn)原理和串行算法特點(diǎn),對(duì)其潛在多層次并行性進(jìn)行挖掘。針對(duì)該算法在多種的混合并行模型下進(jìn)行全面的多級(jí)并行化設(shè)計(jì)與實(shí)現(xiàn),分別設(shè)計(jì)單節(jié)點(diǎn)內(nèi)CUDA并行算法、多節(jié)

3、點(diǎn)間的MPI+OpenMP、MPI+CUDA、MPI+OpenMP+CUDA的混合并行算法,并且從通信、任務(wù)劃分、負(fù)載均衡、存儲(chǔ)方式方面進(jìn)行優(yōu)化處理。
　　在并行算法的性能評(píng)估中,利用5種參數(shù)模型測(cè)試分析算法的適應(yīng)度結(jié)果、執(zhí)行時(shí)間、加速比和可拓展性;對(duì)混合并行算法的通信代價(jià)、負(fù)載均衡和內(nèi)存容量耗用進(jìn)行算法的適用性測(cè)試分析;最后綜合分析評(píng)估各種參數(shù)模型下多種GSA-MSA混合并行算法的整體性能。實(shí)驗(yàn)取得了以下的研究結(jié)果:
　　

4、1、各個(gè)混合模型的 GSA-MS A并行算法都能保持和串行算法的結(jié)果誤差小于0.15％,在序列數(shù)量越大、長(zhǎng)度越小時(shí),并行算法的執(zhí)行速度越具有明顯優(yōu)勢(shì)。
　　2、在加速比測(cè)試中,五個(gè)參數(shù)模型的并行算法都有較好加速效果,單節(jié)點(diǎn)內(nèi)CUDA算法最高加速比達(dá)到113.60;4節(jié)點(diǎn)MPI+OpenMP達(dá)到13.88以上;由于測(cè)試環(huán)境各節(jié)點(diǎn)內(nèi)只有一個(gè)GPU,MPI+CUDA與MPI+OpenMP+CUDA的加速比相差不大,OpenMP加速效果不

5、明顯。三層混合算法對(duì)長(zhǎng)序列的加速比達(dá)到256.86,短序列可高達(dá)393.42。另外,并行算法擁有較好的可拓展性,在增大種群數(shù)量和溫度控制時(shí),加速效果更為明顯,增大遺傳迭代次數(shù)時(shí),各參數(shù)模型的加速效果基本一致。
　　3、并行算法適用性評(píng)估中,三層混合并行算法能很好的控制通信代價(jià),通信耗時(shí)占總時(shí)間的2.23%以下。節(jié)點(diǎn)間的計(jì)算時(shí)間差不大于總時(shí)間的6.69%,負(fù)載均衡較為理想,節(jié)點(diǎn)內(nèi)也實(shí)現(xiàn)了良好的動(dòng)態(tài)線(xiàn)程塊和線(xiàn)程分配方式。此外,測(cè)試中,