MrBayes is a popular software package for Bayesian phylogenetic inference, which uses an iterative approach to derive an evolutionary tree for a collection of species whose DNA sequences are known. Computationally, MrBayes is characterized by a large number of iterations, each composed of a set of tasks that isolated are not very time-consuming, but are globally computationally demanding. To accelerate the latest MrBayes 3.2, this paper presents MrBayes sMC3, which relies on the computational power of an heterogeneous CPU+GPU platform. For this, MrBayes sMC3 exploits both task and data-level parallelism while minimizing the overheads associated with kernel launches and CPU-GPU data transfers. Experimental results indicate that the proposed parallel approach, together with the proposed set of optimizations, allow for an application acceleration of up to 10× regarding the original MrBayes, and up to 3× regarding the Beagle Library. Furthermore, by analyzing the convergence rate of MrBayes sMC3 with that of the state-of-the-art approaches, a significant reduction in execution time is observed.
Gómez-LunaJGonzález-LinaresJMBenavidesJI. (2012) Performance models for CUDA streams on NVIDIA GeForce series. Journal of Parallel and Distributed Computing72(9): 1117–1126.
6.
GuerreiroJIlicARomaN. (2015) Multi-kernel auto-tuning on GPUs: Performance and energy-aware optimization. In: 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pp.438–445, 4–6 March 2015. Turku, Finland: IEEE.
7.
HarrisM (2007) Optimizing parallel reduction in CUDA. NVIDIA Developer Technology2(4).
8.
HastingsWK (1970) Monte Carlo sampling methods using Markov chains and their applications. Biometrika57(1): 97–109.
9.
HuelsenbeckJPRonquistF (2001) MRBAYES: Bayesian inference of phylogenetic trees. Bioinformatics17(8): 754–755.
KuanLNevesJPratasF. (2014) Accelerating Phylogenetic Inference on GPUs: an OpenACC and CUDA comparison. In: Proceedings of the 2014 international work-conference on bioinformatics and biomedical engineering (IWBBIO 2014), volume 1, pp.589–600, 7–9 April. Granada, Spain: Copicentro Editorial.
12.
LeacheADMulcahyDG (2007) Phylogeny, divergence times and species limits of spiny lizards (sceloporus magister species group) in western north american deserts and baja california. Molecular Ecology16(24): 5216–5233.
13.
LingCHamadaTBaiJ. (2013) MrBayes tgMC3: A Tight GPU Implementation of MrBayes. PloS One8(4): e60667.
14.
PratasFSousaL (2009) Applying the stream-based computing model to design hardware accelerators: A case study. In: BertelsKDimopoulosNSilvanoCWongS (eds) Embedded Computer Systems: Architectures, Modeling, and Simulation, pp.237–246. Berlin: Springer.
15.
PratasFTrancosoPStamatakisA. (2009) Fine-grain Parallelism Using Multi-core, Cell/BE, and GPU Systems: Accelerating the Phylogenetic Likelihood Function. In: International Conference on Parallel Processing (ICPP), pp.9–17, 22–25 September. Vienna, Austria: IEEE.
16.
RambautAGrassNC (1997) Seq-gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Computer Applications in the Viosciences: CABIOS13(3): 235–238.
17.
RannalaBYangZ (2008) Phylogenetic inference using whole genomes. Annual Review of Genomics and Human Genetics9: 217–231.
18.
RonquistFTeslenkoMvan der MarkP. (2012) MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space. Systematic Biology61(3): 539–542.
19.
StamatakisA (2006) RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics22(21): 2688–2690.
20.
TaniçaLIlicATomásP. (2014) Schedmon: A performance and energy monitoring tool for modern multi-cores. In: 7th International Workshop on Multi/Many-Core Computing Systems (MuCoCoS), pp.230–241, 25–29 AugustPorto, Portugal: Springer.
21.
TorresYGonzalez-EscribanoALlanosDR (2011) Understanding the impact of CUDA tuning techniques for Fermi. In: 2011 International Conference on High Performance Computing and Simulation, pp.631–639, 4–8 July 2011. Istanbul, Turkey: IEEE.
22.
TorresYGonzalez-EscribanoALlanosDR (2013) Ubench: exposing the impact of CUDA block geometry in terms of performance. The Journal of Supercomputing65(3): 1150–1163.
23.
Van WerkhovenBMaassenJSeinstraF. (2014) Performance models for CPU-GPU data transfers. In: 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), pp.11–20, 26–29 May 2014. Chicago, IL: IEEE.
24.
XieQBuWZhengL (2005) The Bayesian phylogenetic analysis of the 18S rRNA sequences from the main lineages of Trichophora (insecta: heteroptera: pentatomomorpha). Molecular Phylogenetics and Evolution34(2): 448–451.
25.
XieQTianYZhengL. (2008) 18S rRNA hyper-elongation and the phylogeny of Euhemiptera (insecta: hemiptera). Molecular Phylogenetics and Evolution47(2): 463–471.
26.
XieQWangYLinJ. (2012) Potential key bases of ribosomal RNA to kingdom-specific spectra of antibiotic susceptibility and the possible archaeal origin of eukaryotes. PloS one7(1): e29468.
27.
YangZ (1994) Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites: approximate methods. Journal of Molecular Evolution39(3): 306–314.
28.
YangZ (1997) PAML: a program package for phylogenetic analysis by maximum likelihood. Computer Applications in the Biosciences: CABIOS13(5): 555–556.
29.
ZhouJLiuXStonesDS. (2011) MrBayes on a graphics processing unit. Bioinformatics27(9): 1255–1261.
