This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
This research develops novel techniques for applying the heterogeneous execution model, where a general-purpose processor is accelerated by a special-purpose co-processor, to optimization-based scientific computations. The result of this research is a library of computational building blocks that perform fundamental operations used in genome analysis, as well as a new design tool that uses this library to systematically synthesize complete co-processor architectures that are optimized for the characteristics of the input dataset of interest.
Traditional development methodologies for heterogeneous computing have focused on computations that are based on data-parallelized O(n) algorithms. This project demonstrates the use of heterogeneous computing for non-O(n) algorithms, which have complex behavior, internal state, temporal locality, and a high ratio of computation versus communication. Adapting this class of computation to heterogeneous platforms provides high-performance computing without the need for maintenance-intensive and power-inefficient traditional shared-memory and cluster-based supercomputers.
This project targets optimization-based phylogeny reconstruction as a application case study. This application uses combinatorial optimization for its search for optimal phylogenetic (evolutionary) trees, as well as for its procedure for scoring candidate trees.
