ABI Development: Increasing concurrency for improved performance of the BEAGLE library

估计生物体的进化史，系统发育推断，往往是了解生物体如何适应复杂生物系统的关键步骤。现代系统发育分析包括从一组生物体中获取DNA序列数据，并使用基于模型的方法来推断二叉树，该二叉树反映了生物体彼此之间的密切关系。这棵树代表了生物的进化史，可以追溯到它们最近的共同祖先，从本质上讲，它是整个生命树的一个子集。除了提供对生命进化的基本理解之外，这些系统发育关系对于理解许多致病生物体（如病毒（如艾滋病毒、流感和埃博拉病毒））的进化动力学、时间和传播非常重要。最有效的系统发育推断涉及统计方法，要么是最大似然分析，要么是贝叶斯分析。这两种方法都有相同的计算瓶颈，即计算提议树的可能性。这些可能性计算是非常密集的计算，因此准确的系统发育分析成为许多生命之树研究的瓶颈。因此，加快系统发育分析对于产生及时的结果至关重要，这些结果可以为公共卫生和疾病控制行动提供信息，也可以更广泛地理解进化生物学中的基本问题。这个项目提高了软件的性能和能力，从而提高了分析的速度，从而减少了获得科学结果的时间。BEAGLE（泛平台进化分析通用似然评估器）库和应用程序编程接口（API）是一个高性能的进化模型似然计算平台。它定义了一个统一的API，并包括一组有效的实现，用于在不同的硬件设备（如图形处理单元（gpu）和多核cpu）上计算各种基于似然的模型。该项目通过将以前需要多个BEAGLE实例的计算转移到单个实例中，从而配置并发通信，为进化分析中计算似然函数的问题提供了新的思路。在单个beagle实例下操作可以更好地协调并发通信，例如，通过减少内存传输以及跨潜在异构设备的负载平衡计算。对并发性的强调源于对计算问题（计算似然函数）的具体特征的深刻理解，以及如何将其用于领域科学（系统遗传学和种群遗传学）中的分析，并认识到处理器设计趋势为增加并发性所提供的机会。总体主题包括以下反复出现的子主题：i)重新表述-将计算识别并分解为实际的独立操作；最小化——减少操作，如内存传输和执行开销；iii)控制-配置流程和通信以最大限度地提高并发性，包括跨设备。该研究项目重新制定了库及其api，并通过以下研究计划将更多功能整合到单个库实例中：利用库实例中的额外并发性，从而通过重构和最小化来改进并发通信；2. 开发充分利用多设备系统的库，从而通过控制负载平衡来改善并发通信；3. 探讨并行计算环境下的数值精度和尺度和4。用统计系统遗传学和群体遗传学的新模型扩展文库的能力。

Estimating the evolutionary history of organisms, phylogenetic inference, is often a critical step for understanding how organisms adapt in complex biological systems. Modern phylogenetic analyses involve obtaining DNA sequence data from a set of organisms, and using model-based methods to infer a binary tree that reflects how closely the organisms are related to one another. This tree represents the evolutionary history of the organisms going back to their most recent common ancestor and is, in essence, a subset of the overall tree of life. In addition to providing a basic understanding of the evolution of life, these phylogenetic relationships are very important in understanding the evolutionary dynamics, timing, and spread of many disease-causing organisms, such as viruses (e.g., hiv, flu, and Ebola). The most effective phylogenetic inferences involve statistical methods, either maximum likelihood or Bayesian analysis. Both of these methods share the same computational bottleneck, which is the calculation of the likelihood of proposed trees. These likelihood calculations are extremely computationally intensive, and hence accurate phylogenetic analyses become a bottleneck in many studies of the tree of life. Therefore, accelerating phylogenetic analyses is critical to produce timely results that can inform public health and disease containment actions, as well as to understand fundamental problems in evolutionary biology more broadly. This project increases the performance and capabilities of software that will in crease the speed of analyses, and thus decrease the time to scientific results.The Broad-platform Evolutionary Analysis General Likelihood Evaluator (BEAGLE) library and Application Programming Interface (API) is a high-performance likelihood-calculation platform for evolutionary models. It defines a uniform API and includes a collection of efficient implementations for calculating a variety of likelihood-based models on different hardware devices, such as graphics processing units (GPUs) and multicore cpus. The project provides new thinking to the problem of computing the likelihood function in evolutionary analyses through configuring concurrent communication by moving computation that previously required multiple BEAGLE instances into a single instance. Operating under a single beagle instance allows better coordination of concurrent communication, by, for example, reducing memory transfers as well as by load-balancing the computation across potentially heterogeneous devices. The emphasis on concurrency originates from a deep understanding of the specific characteristics of the computational problem - computing the likelihood function - and how it is used for analyses within the domain sciences - phylogenetics and population genetics, and recognizing the opportunities presented by trends in processor design for increasing concurrency. The overarching theme comprises the following recurring sub-themes: i) reformulation - identifying and decomposing computation into practical independent operations; ii) minimization - reducing operations, such as memory transfers and execution overhead; and iii) control - configuring flow and communication to maximize concurrency, including across devices. The research project reformulates the library and its api, and focuses on consolidating more capabilities into a single library instance through the following research initiatives: 1. exploiting additional concurrency within a library instance, thus improving concurrent communication by reformulation and minimization; 2. developing the library to fully leverage multi-device systems, thus improving concurrent communication by controlling load-balancing; 3. exploring numerical precision and scaling in parallel computing context; and 4. extending the capabilities of the library with new models for statistical phylogenetics and population genetics.