Communication-Avoiding Recursive Aggregation

Yihao Sun, Sidharth Kumar, Thomas Gilray, Kristopher Micinski

Research output: Chapter in Book/Entry/PoemConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE International Conference on Cluster Computing, CLUSTER 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages197-208
Number of pages12
ISBN (Electronic)9798350307924
DOIs
StatePublished - 2023
Externally publishedYes
Event25th IEEE International Conference on Cluster Computing, CLUSTER 2023 - Santa Fe, United States
Duration: Oct 31 2023Nov 3 2023

Publication series

NameProceedings - IEEE International Conference on Cluster Computing, ICCC
ISSN (Print)1552-5244

Conference

Conference25th IEEE International Conference on Cluster Computing, CLUSTER 2023
Country/TerritoryUnited States
CitySanta Fe
Period10/31/2311/3/23

Keywords

  • aggregation
  • communication-avoiding algorithms
  • relational algebra

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Signal Processing

Fingerprint

Dive into the research topics of 'Communication-Avoiding Recursive Aggregation'. Together they form a unique fingerprint.

Cite this