FPGA Acceleration of the phylogenetic likelihood function for Bayesian MCMC inference methods.
BACKGROUND
Likelihood (ML)-based phylogenetic inference has become a popular method for estimating the evolutionary relationships among species based on genomic sequence data. This method is used in applications such as RAxML, GARLI, MrBayes, PAML, and PAUP. The Phylogenetic Likelihood Function (PLF) is an important kernel computation for this method. The PLF consists of a loop with no conditional behavior or dependencies between iterations. As such it contains a high potential for exploiting parallelism using micro-architectural techniques. In this paper, we describe a technique for mapping the PLF and supporting logic onto a Field Programmable Gate Array (FPGA)-based co-processor. By leveraging the FPGA's on-chip DSP modules and the high-bandwidth local memory attached to the FPGA, the resultant co-processor can accelerate ML-based methods and outperform state-of-the-art multi-core processors.


RESULTS
We use the MrBayes 3 tool as a framework for designing our co-processor. For large datasets, we estimate that our accelerated MrBayes, if run on a current-generation FPGA, achieves a 10x speedup relative to software running on a state-of-the-art server-class microprocessor. The FPGA-based implementation achieves its performance by deeply pipelining the likelihood computations, performing multiple floating-point operations in parallel, and through a natural log approximation that is chosen specifically to leverage a deeply pipelined custom architecture.


CONCLUSIONS
Heterogeneous computing, which combines general-purpose processors with special-purpose co-processors such as FPGAs and GPUs, is a promising approach for high-performance phylogeny inference as shown by the growing body of literature in this field. FPGAs in particular are well-suited for this task because of their low power consumption as compared to many-core processors and Graphics Processor Units (GPUs).
Zierke
Stephanie
S
Department of Computer Science and Engineering, University of South Carolina, Columbia, SC, USA.
Bakos
Jason D
JD
D001499:Bayes Theorem; D016013:Likelihood Functions; D010802:Phylogeny; D012984:Software
Syst Biol. 2009 Apr;58(2):224-39
20525580
J Mol Evol. 1981;17(6):368-76
7288891
Proc Natl Acad Sci U S A. 1996 Aug 20;93(17):9188-93
8799176
Bioinformatics. 2009 Jun 1;25(11):1370-6
19369496
Mycologia. 2002 Jan-Feb;94(1):85-98
21156480
Mycologia. 2006 Nov-Dec;98(6):1018-28
17486977
Bioinformatics. 2003 Aug 12;19(12):1572-4
12912839
Mycologia. 2003 Jul-Aug;95(4):756-64
21148982
Bioinformatics. 2006 Nov 1;22(21):2688-90
16928733
Bioinformatics. 2005 Feb 15;21(4):456-63
15608047
BMC Bioinformatics. 2008 Jul 28;9:322
18662388
J Mol Evol. 2004 Mar;58(3):252-68
15045481
Mol Biol Evol. 2003 Feb;20(2):255-66
12598693
Mol Biol Evol. 2007 Aug;24(8):1586-91
17483113
Bioinformatics. 2002 Mar;18(3):502-4
11934758
Bioinformatics. 2004 Feb 12;20(3):407-15
14960467
Bioinformatics. 2005 Oct 1;21(19):3794-6
16046495
Bioinformatics. 2005 Apr 1;21(7):969-74
15513992