Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Resource-efficient utilization of CPU/GPU-based heterogeneous supercomputers for Bayesian phylogenetic inference

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Bayesian inference is one of the most important methods for estimating phylogenetic trees in bioinformatics. Due to the potentially huge computational requirements, several parallel algorithms of Bayesian inference have been implemented to run on CPU-based clusters, multicore CPUs, or small clusters of CPUs and GPUs. To the best of our knowledge, however, none of the existing methods is able to simultaneously and fully utilize both CPUs and GPUs for the computations, leaving idle either the CPU part or the GPU part of modern heterogeneous supercomputers. Aiming at an optimized utilization of heterogeneous computing resources, which is a promising hardware architecture for future bioinformatics applications, we present a new hybrid parallel algorithm and implementation of Bayesian phylogenetic inference, which combines MPI, OpenMP, and CUDA programming. The novelty of our algorithm, denoted as oMC3, is its ability of using CPU cores simultaneously with GPUs for the computations, while ensuring a fair work division between the two types of hardware components. We have implemented oMC3 based on MrBayes, which is one of the most popular software packages for Bayesian phylogenetic inference. Numerical experiments show that oMC3 obtains 2.5× speedup over nMC3, which is a cutting-edge GPU implementation of MrBayes, on a single server consisting of two GPUs and sixteen CPU cores. Moreover, oMC3 scales nicely when 128 GPUs and 1536 CPU cores are in use.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Bader DA, Moret B, Vawter L (2001) Industrial applications of high-performance computing for phylogeny reconstruction. Proc SPIE 4528:159–168

    Article  Google Scholar 

  2. U.S. National Science Foundation (2004) Assembling the tree of life (ATOL): to construct a phylogeny for the 1.7 million described species of life. National Science Foundation, Program Solicitation, NSF 04-526

  3. Feng X, Cameron KW, Buell DA (2006) PBPI: a high performance implementation of Bayesian phylogenetic inference. In: Proceedings of the 2006 ACM/IEEE conference on supercomputing. IEEE, New York

    Google Scholar 

  4. Huelsenbeck JP, Ronquist F, Nielsen R, Bollback JP (2001) Bayesian inference of phylogeny and its impact on evolutionary biology. Science 294:2310–2314

    Article  Google Scholar 

  5. Altekar G, Dwarkadas S, Huelsenbeck JP, Ronquist F (2004) Parallel metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference. Bioinformatics 20(3):407–415

    Article  Google Scholar 

  6. Feng X, Buell DA, Rose JR, Waddell PJ (2003) Parallel algorithms for Bayesian phylogenetic inference. J Parallel Distrib Comput 63(7–8):707–718

    Article  Google Scholar 

  7. Feng X, Cameron KW, Sosa CP, Smith B (2007) Building the tree of life on terascale systems. In: Proceedings of the 21st international parallel and distributed processing symposium, Long Beach, CA, March 2007, pp 1–10.

    Google Scholar 

  8. Van der Wath RC, Van der Wath E, Carapelli A, Nardi F, Frati F, Milanesi L, Li P (2008) Bayesian phylogeny on grid. Bioinf Res Dev 13:404–416

    Article  Google Scholar 

  9. Pfeiffer W, Stamatakis A s (2010) Hybrid parallelization of the MrBayes & RAxML phylogenetics codes. http://sco.h-its.org/exelixis/Phylo100225.pdf

  10. Zhou J, Wang G, Liu X (2010) A new hybrid parallel algorithm for MrBayes. In: Proceedings ICA3PP 2010. LNCS, vol 6081, pp 102–112

    Google Scholar 

  11. Pratas F, Trancoso P, Stamatakis A, Sousa L (2009) Fine-grain parallelism using multi-core, cell/BE, and GPU systems: accelerating the phylogenetic likelihood function. In: Proceedings ICPP 2009. IEEE Computer Society, Los Alamitos, pp 9–17

    Google Scholar 

  12. Zhou J, Liu X, Stones DS, Xie Q, Wang G (2011) MrBayes on a graphics processing unit. Bioinformatics 27(9):1255–1261

    Article  Google Scholar 

  13. Suchard MA, Rambaut A (2009) Many-core algorithms for statistical phylogenetics. Bioinformatics 25(11):1370–1376

    Article  Google Scholar 

  14. Ayres DL, Darling A, Zwickl DJ, Beerli P, Holder MT, Lewis PO, Huelsenbeck JP, Ronquist F, Swofford DL, Cummings MP, Rambaut A, Suchard MA (2012) BEAGLE: an application programming interface and high-performance computing library for statistical phylogenetics. Syst Biol 61(1):170–173

    Article  Google Scholar 

  15. Ronquist F, Teslenko M, Van der Mark P, Ayres DL, Darling A, Höhna S, Larget B, Liu L, Suchard MA, Huelsenbeck JP (2012) MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space. Syst Biol 61(3):539–542

    Article  Google Scholar 

  16. Yang XJ, Liao XK, Lu K, Hu QF, Song JQ, Su JS (2011) The TianHe-1A supercomputer: its hardware and software. J Comput Sci Technol 26(3):344–351

    Article  Google Scholar 

  17. Top500. http://www.top500.org/lists/2010/11

  18. Jaguar. http://en.wikipedia.org/wiki/Jaguar_(supercomputer)

  19. Sun NH, Xing J, Huo ZG, Huo ZG, Tan GM, Xiong J, Li B, Ma C (2010) Dawning Nebulae: a PetaFLOPS supercomputer with a heterogeneous structure. J Comput Sci Technol 26(3):352–362

    Article  Google Scholar 

  20. Shimokawabe T, Aoki T, Takaki A, Yamanaka A, Nukada T, Endo N, Maruyama S, Matsuoka S (2011) Peta-scale phase-field simulation for dendritic solidification on the TSUBAME 2.0 supercomputer. In: Proceedings of the 2011 ACM/IEEE conference on supercomputing, Seattle, WA. IEEE, New York

    Google Scholar 

  21. Huelsenbeck JP, Ronquist F (2005) Bayesian analysis of molecular evolution using MrBayes. In: Statistical methods in molecular evolution. Springer, Berlin, pp 183–226

    Chapter  Google Scholar 

  22. MrBayes version3.1.2. http://sourceforge.net/projects/mrbayes/files/mrbayes/3.1.2/

  23. NVIDIA CUDA C programming guide version 4.1. http://developer.nvidia.com/cuda-downloads

  24. Optimal MrBayes (version 1.0) user manual. https://sourceforge.net/projects/optimal-mrbayes/

Download references

Acknowledgements

The authors gratefully acknowledge the support from National Natural Science Foundation of China under NSFC Nos. 61033008, 60903041, and 61103080, Research Fund for the Doctoral Program of Higher Education of China under SRFDP No. 20104307110002, Hunan Provincial Innovation Foundation for Postgraduate under No. CX2010B028, Fund of Innovation in Graduate School of NUDT under No. B100603, and Research Grant No. 214113 from the Research Council of Norway. We also acknowledge the experimental platform support from the National Supercomputing Center in Changsha.

Author information

Authors and Affiliations

  1. School of Computer, National University of Defense Technology, 410073, Changsha, P.R. China

    Jun Chai, Huayou Su, Mei Wen, Nan Wu & Chunyuan Zhang

  2. Simula Research Laboratory, P.O. Box 134, 1325, Lysaker, Norway

    Xing Cai

  3. Department of Informatics, University of Oslo, P.O. Box 1080, Blindern, 0316, Oslo, Norway

    Xing Cai

Authors
  1. Jun Chai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huayou Su
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mei Wen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xing Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Nan Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Chunyuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jun Chai.

Additional information

The source code of our new hybrid implementation of MrBayes is available for download at https://sourceforge.net/projects/optimal-mrbayes/.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chai, J., Su, H., Wen, M. et al. Resource-efficient utilization of CPU/GPU-based heterogeneous supercomputers for Bayesian phylogenetic inference. J Supercomput 66, 364–380 (2013). https://doi.org/10.1007/s11227-013-0911-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-013-0911-1

Keywords

Search

Navigation