Asynchrony versus bulk-synchrony for a generalized N-body problem from genomics
Asynchrony versus bulk-synchrony for a generalized N-body problem from genomics
复制标题
DOI：
10.1145/3437801.3441580
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Marquita Ellis;A. Buluç;K. Yelick
中科院分区：
文献类型：
--
作者：
Marquita Ellis;A. Buluç;K. Yelick
这项工作研究了来自基因组学的数据密集型不规则应用，一个长读到长读比对问题，它代表了一种广义N体问题，NRC大数据主题的“七大巨人”之一[5]。在这个问题中，计算（基因组比对）是在稀疏和数据依赖的输入对上进行的，具有可变的成本计算和可变的数据大小。特别是，与基于模拟的N体问题不同，成对交互中没有固有的局部性，交互稀疏性取决于输入的特定参数，这也会影响输出的质量。我们研究两个极端的分布式内存并行化这个问题，批量同步和同步，与真实的工作负载。我们的批量同步实现使用MPI中的集体通信，而我们的异步实现使用UPC++中的跨节点RPC。我们表明，异步版本有效地隐藏通信成本，内存占用通常比批量同步版本低得多。我们的应用程序虽然简单到可以作为基因组学或更广泛的数据分析应用程序的代理，但也是真实的应用程序管道的一部分。它显示了对真实的输入问题的良好扩展，同时揭示了扩展这种类型的数据密集型不规则应用程序的一些编程和架构挑战。
This work examines a data-intensive irregular application from genomics, a long-read to long-read alignment problem, which represents a kind of Generalized N-Body problem, one of the "seven giants" of the NRC Big Data motifs [5]. In this problem, computations (genomic alignments) are performed on sparse and data-dependent pairs of inputs, with variable cost computation and variable datum sizes. In particular, there is no inherent locality in the pairwise interactions, unlike simulation-based N-Body problems, and the interaction sparsity depends on particular parameters of the input, which can also affect the quality of the output. We examine two extremes to distributed memory parallelization for this problem, bulk-synchrony and asynchrony, with real workloads. Our bulk-synchronous implementation, uses collective communication in MPI, while our asynchronous implementation uses cross-node RPCs in UPC++. We show that the asynchronous version effectively hides communication costs, with a memory footprint that is typically much lower than the bulk-synchronous version. Our application, while simple enough to be a kind of proxy for genomics or data analytics applications more broadly, is also part of a real application pipeline. It shows good scaling on real input problems, and at the same time, reveals some of the programming and architectural challenges for scaling this type of data-intensive irregular application.