Algorithms for a Topology-aware Massively Parallel Computation Model

Xiao Hu, Paraschos Koutris, Spyros Blanas

TL;DR

This paper moves beyond the "flat" network assumptions of traditional parallel computing models to propose the first algorithms for fundamental data tasks—set intersection, cartesian product, and sorting—that are aware of the underlying network topology. By focusing on symmetric tree structures (like fat trees and star topologies), the authors provide simple, constant-round algorithms that achieve theoretically optimal performance based on how data is initially distributed across the network.

What Problem Does This Paper Address?

Most theoretical models for massively parallel computation (MPC) assume homogeneity: every compute node is identical, and any node can talk to any other node with the same latency and bandwidth. In reality, modern clusters are messy. They consist of different generations of CPUs and GPUs, and communication speeds vary wildly depending on whether nodes are in the same rack, different racks, or different datacenters.

Ignoring this "topology" leads to algorithms that might look good on paper but perform poorly in practice due to network bottlenecks. This paper tackles the challenge of designing algorithms that are topology-aware and distribution-aware, meaning they adapt their communication patterns based on the physical network layout and the initial location of the data.

Methods

The authors adopt a model where the network is a directed graph, and the cost of a computation round is determined by the most heavily loaded link (the "bottleneck"). They specifically focus on symmetric tree topologies, which are common in real-world data centers.

Key algorithmic techniques include:

  • Balanced Partitions for Set Intersection: To compute $R \cap S$, the authors developed a way to partition compute nodes into "balanced" blocks. This ensures that data is routed through the network such that no single link exceeds its capacity, matching lower bounds within a polylogarithmic factor.
  • Geometric Square Packing for Cartesian Product: Computing $R \times S$ is framed as a geometric problem. Each node is assigned a "square" in the product space. The size of the square is proportional to the node's network capacity. The challenge is "packing" these squares to cover the entire product space without overloading any network links.
  • Weighted TeraSort: The authors generalize the well-known TeraSort algorithm. Instead of splitting data uniformly, they split it proportionally to the initial data sizes at each node and use a "coordinator" approach that respects the tree hierarchy.

Datasets

Not discussed in the paper. This is a theoretical research paper focused on formal model analysis, complexity bounds, and algorithmic design. It uses mathematical proofs rather than empirical benchmarks on specific datasets to establish its results.

Key Insights and Ideas

  • Distribution-Aware Optimality: Unlike previous work that assumes a worst-case or uniform data distribution, these algorithms are optimal relative to the actual initial placement of data. This is crucial because data in real systems is often skewed or pre-partitioned.
  • The Power of Trees: While general graphs are hard to analyze, the authors show that tree topologies allow for "trivial" routing (there is only one path between any two nodes). This simplicity allows them to derive tight lower bounds using communication complexity theory.
  • Bandwidth Independence: Surprisingly, for some tasks like set intersection, the optimal routing strategy depends only on the network's connectivity and the data distribution, not the specific bandwidth of the links.
  • Constant Rounds: All proposed protocols run in a constant number of rounds (usually 1 or 4). This is vital for practical systems where synchronization between rounds is a major performance killer.

Key Results

The paper establishes matching (or nearly matching) upper and lower bounds for three core tasks on symmetric tree topologies:

Task Algorithm Type Rounds Optimality Guarantee
Set Intersection Randomized 1 $O(\log |V| \log N)$ factor from optimal
Cartesian Product Deterministic 1 $O(1)$ (Constant factor from optimal)
Sorting Randomized $O(1)$ $O(1)$ (Constant factor from optimal)

Note: $|V|$ is the number of nodes, and $N$ is the total data size.

Limitations and Future Work

The primary limitation is the focus on symmetric tree topologies. While trees cover many common setups (like star networks and fat trees), they don't capture more complex "mesh" or "torus" topologies where multiple paths exist between nodes. In those cases, the algorithm would need to decide not just what to send, but which path to take.

The authors suggest several future directions:

  1. Extending the model to non-symmetric links (where upload and download speeds differ).
  2. Moving to general, non-tree topologies (like grids), which introduces the challenge of multi-path routing.
  3. Applying these topology-aware principles to more complex database operations, such as multi-way joins.

Summary updated

Abstract

Most of the prior work in massively parallel data processing assumes homogeneity, i.e., every computing unit has the same computational capability and can communicate with every other unit with the same latency and bandwidth. However, this strong assumption of a uniform topology rarely holds in practical settings, where computing units are connected through complex networks. To address this issue, Blanas et al. \citeblanas2020topology recently proposed a topology-aware massively parallel computation model that integrates the network structure and heterogeneity in the modeling cost. The network is modeled as a directed graph, where each edge is associated with a cost function that depends on the data transferred between the two endpoints. The computation proceeds in synchronous rounds and the cost of each round is measured as the maximum cost over all the edges in the network. In this work, we take the first step into investigating three fundamental data processing tasks in this topology-aware parallel model: set intersection, cartesian product, and sorting. We focus on network topologies that are tree topologies, and present both lower bounds as well as (asymptotically) matching upper bounds. Instead of assuming a worst-case distribution as in previous results, the optimality of our algorithms is with respect to the initial data distribution among the network nodes. Apart from the theoretical optimality of our results, our protocols are simple, use a constant number of rounds, and we believe can be implemented in practical settings as well.
BibTeX
@inproceedings{hu2021algorithms,
  author = {Xiao Hu and Paraschos Koutris and Spyros Blanas},
  title = {{Algorithms for a Topology-aware Massively Parallel Computation Model}},
  booktitle = {PODS},
  year = {2021},
  url = {https://openreview.net/forum?id=ghX-CZigrmk},
}

Loading related content...

Figure