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

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

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

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

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

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