Title :
NoC-Based Hardware Accelerator for Breakpoint Phylogeny
Author :
Majumder, Turbo ; Sarkar, Souradip ; Pande, Partha Pratim ; Kalyanaraman, Ananth
Author_Institution :
Sch. of Electr. Eng. & Comput. Sci., Washington State Univ., Pullman, WA, USA
fDate :
6/1/2012 12:00:00 AM
Abstract :
Maximum Parsimony phylogenetic tree reconstruction is based on finding the breakpoint median, given a set of species, and is represented by a bounded edge-weight graph model. This reduces the breakpoint median problem to one of solving multiple instances of the Traveling Salesman Problem (TSP), which is a classical NP-complete problem in graph theory. Exponential time algorithms that apply efficient runtime heuristics, such as branch-and-bound, to dynamically prune the search space are used to solve TSP. In this paper, we present the design and performance evaluation of a network-on-chip (NoC)-based implementation for solving TSP under the bounded edge-weight model, as used in the computation of breakpoint phylogeny. Our approach takes advantage of fine-grain parallelism from the multiple processing elements (PEs) and uses efficient NoC architecture for inter-PE communication. To accelerate the application on hardware, our PE design optimizes a particular lower bound calculation operation which typically tends to be the serial bottleneck in computation of a TSP solution. We also explore two representative NoC architectures-mesh and quad-tree-and show that the latter is more energy-efficient for this application domain. Experimental results show that this new implementation is able to achieve speedups of up to three orders of magnitude over state-of-the-art multithreaded software implementations.
Keywords :
computational complexity; evolution (biological); network-on-chip; travelling salesman problems; trees (mathematics); NP-complete problem; NoC-based hardware accelerator; bounded edge-weight model; breakpoint phylogeny; exponential time algorithms; graph theory; inter-PE communication; maximum parsimony phylogenetic tree reconstruction; multiple processing elements; multithreaded software implementations; network-on-chip based implementation; quad-tree; traveling salesman problem; Algorithm design and analysis; Bioinformatics; Computer architecture; Genomics; Heuristic algorithms; Phylogeny; Vegetation; Phylogenetics; breakpoint-median problem; maximum parsimony; traveling salesman problem.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2011.100