SHF: Small: Co-Processors for High-Performance Genome Analysis

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。本研究开发了应用异构执行模型的新技术，其中通用处理器由专用协处理器加速，以优化为基础的科学计算。这项研究的结果是一个执行基因组分析中使用的基本操作的计算构建块库，以及一个新的设计工具，该工具使用该库系统地合成完整的协处理器架构，该架构针对感兴趣的输入数据集的特征进行了优化。异构计算的传统开发方法侧重于基于数据并行的O(n)算法的计算。该项目展示了非o (n)算法的异构计算的使用，这些算法具有复杂的行为、内部状态、时间局部性和计算与通信的高比率。将这类计算适应于异构平台可以提供高性能计算，而不需要维护密集型和低功耗的传统共享内存和基于集群的超级计算机。本项目以基于优化的系统发育重建为应用案例。这个应用程序使用组合优化来搜索最优的系统发育（进化）树，以及为候选树评分的过程。

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.