Efficient Execution of Dynamic Programming Algorithms on Apache Spark
Efficient Execution of Dynamic Programming Algorithms on Apache Spark
复制标题
DOI：
10.1109/cluster49012.2020.00044
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
M. Javanmard;Zafar Ahmad;J. Zola;L. Pouchet;R. Chowdhury;R. Harrison
中科院分区：
文献类型：
--
作者：
M. Javanmard;Zafar Ahmad;J. Zola;L. Pouchet;R. Chowdhury;R. Harrison
集群和计算云上的分布式计算系统（如 Apache Spark、Apache Hadoop 等）最重要的特性之一是能够通过向集群添加更多计算节点来扩展。只要计算（或算法）本身能够扩展，这一重要特性就能带来性能提升。换句话说，根据集群或云的硬件/软件配置，计算（或算法）应可轻松分解成较小的工作单位，并在工作者之间进行分配。此外，在此类集群上，通信成本、并行性和内存需求之间存在着重要的权衡。鉴于可扩展性需求和这种权衡，拥有一个可分解、自适应、可调整和可扩展的程序至关重要。可调性使程序员能够在权衡范围内找到最佳点，从而在特定集群上高效执行程序。我们从高斯消除范式（GEP）中设计并实现了可良好分解和可调整的动态编程算法，如 Floyd-Warshall 的全对最短路径和无支点高斯消除，以便在 Apache Spark 上执行。我们的实现基于参数多向递归分而治之算法。我们解释了如何将这些基于网格的并行算法的实现映射到 Spark 框架。最后，我们提供了实验结果，说明了 Spark 程序的性能、可扩展性和可移植性。我们表明，将计算卸载到 Spark 中的 OpenMP 环境（通过运行并行递归内核）至少是 DP 基准提速 2-5 倍的部分原因。
One of the most important properties of distributed computing systems (e.g., Apache Spark, Apache Hadoop, etc) on clusters and computation clouds is the ability to scale out by adding more compute nodes to the cluster. This important feature can lead to performance gain provided the computation (or the algorithm) itself can scale out. In other words, the computation (or the algorithm) should be easily decomposable into smaller units of work to be distributed among the workers based on the hardware/software configuration of the cluster or the cloud. Additionally, on such clusters, there is an important trade-off between communication cost, parallelism, and memory requirement. Due to the scalability need as well as this trade-off, it is crucial to have a well-decomposable, adaptive, tunable, and scalable program. Tunability enables the programmer to find an optimal point in the trade-off spectrum to execute the program efficiently on a specific cluster. We design and implement well-decomposable and tunable dynamic programming algorithms from the Gaussian Elimination Paradigm (GEP), such as Floyd-Warshall's all-pairs shortest path and Gaussian elimination without pivoting, for execution on Apache Spark. Our implementations are based on parametric multi-way recursive divide-&-conquer algorithms. We explain how to map implementations of those grid-based parallel algorithms to the Spark framework. Finally, we provide experimental results illustrating the performance, scalability, and portability of our Spark programs. We show that offloading the computation to an OpenMP environment (by running parallel recursive kernels) within Spark is at least partially responsible for a $2-5\times$ speedup of the DP benchmarks.