Accelerating Maximum Likelihood Based Phylogenetic Kernels Using Network-on-Chip - Majumder, Turbo; Pande, Partha; Kalyanaraman, Ananth (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 2011: Anais do XXIII International Symposium on Computer Architecture and High Performance Computing, 2011)
Probability-based approaches for phylogenetic inference, like Maximum Likelihood (ML) and Bayesian Inference, provide the most accurate estimate of evolutionary relationships among species. But they come at a high algorithmic and computational cost. Network-on-chip (NoC), being an emerging paradigm, has not been explored yet to achieve fine-grained parallelism for these applications. In this paper, we present the design and performance evaluation of an NoC architecture for RAxML, which is one of the most widely used ML software suites. Specifically, we implement the top three function kernels that account for more than 85% of the total run-time. Simulations show that through novel core design, allocation and placement strategies our NoC-based implementation can achieve function-level speedups of 388x to 786x and system-level speedups in excess of 5000x over state-of-the-art multithreaded software.