High-performance Implementation Of MrBayes MC~3on Multi-GPU

MrBayes is a widely-used program for phylo genetic inference, which uses Metropolis-coupled Markov chain Monte Carlo (MC3) to estimate the posterior probability of a phylogenetic tree.Next generation DNA sequencing technology not only makes the scale of real-world DNA data grow exponentially but also reduces the time and improves the DNA quality significantly. But neither the original MrBayes nor its improved and parallel versions are fast enough for Biologists to analyze large real-world DNA data. Graphics Processor Unit (GPU) as an innovative technology has drawn much attentions in scientific computing.We put forward an optimization algorithm called aMC3on the basis of nMC3. To start with, by changing task scheduling strategy and recombining computing sequence, we improve the concurrence between CPU and GPU. Then we adjust the task granularity to adapt the DNA sequence size, which can make full use of GPU. Finally we propose a task scheduling among GPUs to make an optimized utilization of heterogeneous computing resources.Experiments on a desktop with one GPU card show that aMC3achieves up to90x speedup, it achieves up to249x speedup on a quad-GPU cluster, and up to345x speedup is achieved with16nodes on TH-1A. All above shows that aMC3not only has remarkable speedup, but also scales well. The proposed algorithm both saves researchers’ time and brings the opportunity for data analyzing and data mining in the rise of big data.