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

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