MrBayes MC3算法的并行化研究.pdf

1、MrBayes是一款在生物信息學(Bioinformatics)領域被廣泛使用的軟件。它使用Metropolis coupled Markov chain Monte Carlo(MC3)算法進行貝葉斯系統(tǒng)發(fā)育推斷(Bayesian phylogenetic inference)。
　　 隨著DNA測序技術的發(fā)展，研究人員可用的真實DNA數(shù)據(jù)越來越多。特別是在新一代的DNA測序技術--大規(guī)模并行測序(massively para

2、llelsequencing)--問世之后，可用的真實DNA數(shù)據(jù)的數(shù)量更是以指數(shù)方式增長，而且這些數(shù)據(jù)的規(guī)模越來越龐大，構成也越來越復雜。對這些大規(guī)模復雜的真實DNA數(shù)據(jù)進行分析是生物研究領域的一個熱門問題，更是研究人員的一個迫切需求。然而，迄今為止，無論是串行的MrBayes MC3算法，還是它的改進與并行版本，都無法滿足研究人員處理如此大規(guī)模數(shù)據(jù)的需求。幸運的是，越來越多新興的并行或分布式平臺可以為研究人員提供幫助，譬如多核中央處理

3、器(CPU)與圖形處理器(GPU)。特別是GPU，作為一個協(xié)處理器(確切的說，是一個加速器)，已經在許多領域展示了自己強大的能力。
　　 本文描述了兩種新的針對MrBayes MC3的并行算法：一種是針對多核CPU集群的hMC3算法，另一種是針對CPU－GPU異構平臺的nMC3算法。hMC3算法將一種針對MrBayes MC3的鏈間(inter-chain)并行技術與一種鏈內(intra-chain)并行技術結合在一起，以期獲得

4、更高的并發(fā)度。在一個異構的多核CPU集群上分析四個真實DNA數(shù)據(jù)集的實驗結果表明，與單純的鏈間和鏈內并行算法相比，hMC3算法的確將更多的CPU核心轉化為更高的加速比。nMC3算法從兩個層次上并行MrBayes MC3：CPU端的鏈間并行與GPU端的鏈內并行。nMC3算法使用一種流水線模型協(xié)調這兩個層次的并行。這個流水線模型能夠有效隱藏CPU與GPU之間的通信開銷。而且，借助于這個流水線模型，在新一代的Fermi CUDA架構上，nMC