Communication-Avoiding Recursive Aggregation
Communication-Avoiding Recursive Aggregation
复制标题
DOI：
10.1109/cluster52292.2023.00024
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Yihao Sun;Sidharth Kumar;Thomas Gilray;Kristopher K. Micinski
中科院分区：
文献类型：
--
作者：
Yihao Sun;Sidharth Kumar;Thomas Gilray;Kristopher K. Micinski
递归聚合由于其统一了广泛的演绎分析工作负载（包括社交媒体挖掘和图形分析）而引起了相当大的兴趣。例如，单源最短路径（SSSP）、连接组件（CC）和PageRank都可以通过递归聚合表示。实现递归聚合对算法提出了严峻的挑战，最先进的工作是确定充分的条件（例如，预映射性），在这些条件下，实现可以在递归中推动聚合，避免传统的基于可达性的方法（例如，Datalog）固有的严重的物化开销。由于将semi-naïve评估与分布混合在一起所带来的挑战，支持递归聚合的最先进的引擎实现主要集中在大型统一机器上。在这项工作中，我们提出了一种在高性能集群上实现递归聚合的方法，该方法避免了通信开销，抑制了当前分布式系统将递归聚合扩展到极高的进程数。我们的方法利用了聚合器形成功能依赖的观察结果，允许我们通过高并行的本地聚合实现递归聚合，以确保最大的吞吐量。此外，我们还提出了一种动态连接规划机制，该机制基于动态关系大小自定义每次迭代的连接顺序。我们在paramagg中实现了我们的方法，这是一个库，它允许声明性地实现使用递归聚合的查询，并使用基于mpi的运行时执行它们。我们在大型统一节点和领导级超级计算机上评估了paragg，展示了高达16,384个进程的可扩展性。
Recursive aggregation has been of considerable interest due to its unifying a wide range of deductive-analytic workloads, including social-media mining and graph analytics. For example, Single-Source Shortest Paths (SSSP), Connected Components (CC), and PageRank may all be expressed via recursive aggregates. Implementing recursive aggregation has posed a serious algorithmic challenge, with state-of-the-art work identifying sufficient conditions (e.g., pre-mappability) under which implementations may push aggregation within recursion, avoiding the serious materialization overhead inherent to traditional reachability-based methods (e.g., Datalog).State-of-the-art implementations of engines supporting recursive aggregates focus on large unified machines, due to the challenges posed by mixing semi-naïve evaluation with distribution. In this work, we present an approach to implementing recursive aggregates on high-performance clusters which avoids the communication overhead inhibiting current-generation distributed systems to scale recursive aggregates to extremely high process counts. Our approach leverages the observation that aggregators form functional dependencies, allowing us to implement recursive aggregates via a high-parallel local aggregation to ensure maximal throughput. Additionally, we present a dynamic join planning mechanism, which customizes join order per-iteration based on dynamic relation sizes. We implemented our approach in PARALAGG, a library which allows the declarative implementation of queries which utilize recursive aggregates and executes them using our MPI-based runtime. We evaluate PARALAGG on a large unified node and leadership-class supercomputers, demonstrating scalability up to 16,384 processes.