Batch-Parallel Euler Tour Trees

Thomas Tseng, Laxman Dhulipala, Guy E. Blelloch

TL;DR

This paper introduces a novel parallel algorithm for maintaining dynamic forests, specifically addressing the challenge of efficiently handling large batches of edge updates. By parallelizing Euler tour trees using a new batch-parallel skip list data structure, the authors achieve asymptotically optimal work and improved depth bounds, demonstrating significant practical speedups on multi-core processors.

What Problem Does This Paper Address?

The dynamic trees problem is fundamental in computer science, dealing with maintaining a forest (a collection of trees) that can be modified by adding (linking) or removing (cutting) edges. This problem is crucial for various graph algorithms, including network flow and dynamic connectivity. While efficient sequential solutions exist, handling large batches of updates in parallel has been a significant challenge. Existing parallel solutions often require complex graph transformations or don't achieve optimal theoretical bounds. This paper aims to bridge this gap by parallelizing a simpler, yet powerful, data structure called Euler tour trees for batch updates.

Methods

The core innovation lies in the development of a batch-parallel skip list. Traditional skip lists are good for sequential operations, but efficiently handling batches of joins and splits (operations essential for Euler tour trees) in parallel was an open problem. The authors' batch-parallel skip list achieves:

  • O(k log(1 + n/k)) expected work and O(log n) depth with high probability for batch joins and splits, where 'k' is the batch size and 'n' is the number of elements. This is a significant improvement over performing operations one by one.
  • Augmented skip lists: They extend this to support efficient computation over contiguous subsequences, crucial for subtree queries in dynamic trees.

These batch-parallel skip lists are then used as the building blocks for batch-parallel Euler tour trees. By representing trees as cyclic sequences using these skip lists, batch link (adding edges) and batch cut (removing edges) operations can be efficiently implemented. The paper also details algorithms for batch connectivity queries and, with augmented skip lists, batch subtree queries.

Datasets

Not discussed in the paper. The experiments use synthetic graphs (path graph, random recursive tree, star graph) of varying sizes.

Key Insights and Ideas

  • Skip lists are surprisingly amenable to batch parallelism: While balanced binary trees are notoriously difficult to parallelize for batch joins/splits, skip lists, with their probabilistic structure and clever use of CAS operations, prove to be a good fit.
  • Batching is key to efficiency: The paper demonstrates that processing operations in batches, rather than individually, unlocks significant performance gains, both theoretically and practically. This is because it allows for amortizing overhead and exploiting parallelism more effectively.
  • Euler tour trees are a viable parallel primitive: The simplicity of Euler tour trees, combined with the power of batch-parallel skip lists, makes them a strong candidate for parallel dynamic graph algorithms.
  • Theoretical bounds translate to practical speedups: The paper not only provides strong theoretical guarantees but also backs them up with impressive experimental results.

Key Results

  • Theoretical Efficiency:
    • Batch-parallel skip lists achieve O(k log(1 + n/k)) expected work and O(log n) depth for batch joins/splits.
  • Batch-parallel Euler tour trees achieve O(k log(1 + n/k)) expected work and O(log n) depth for batch link, cut, and connectivity queries.
  • Practical Performance:
    • Achieved self-relative speedups of 67% to 96% on 72 cores with hyper-threading for large batch sizes.
  • Significantly outperformed the fastest existing sequential dynamic trees data structures empirically.
  • For augmented skip lists, speedups of 67x for joins and 78x for splits were observed on large batches.

Limitations and Future Work

  • Unaugmented Euler Tour Trees: For simplicity in implementation, the paper focuses on unaugmented Euler tour trees and does not support subtree queries directly.
  • Comparison with other parallel structures: The authors mention that they would like to compare their skip lists against other parallel data structures like (a,b)-trees in the future.
  • General Dynamic Connectivity: The paper suggests that their work is a stepping stone towards efficiently parallelizing algorithms for general dynamic graph problems, such as Holm et al.'s algorithm for dynamic connectivity, which is an interesting research direction.
  • Splay Tree Performance: The experimental setup sometimes gave splay trees an advantage due to locality when joining small batches after splitting, which is an artifact of the testing methodology.

Summary updated

Abstract

The dynamic trees problem is to maintain a forest undergoing edge insertions and deletions while supporting queries for information such as connectivity. There are many existing data structures for this problem, but few of them are capable of exploiting parallelism in the batch-setting, in which large batches of edges are inserted or deleted from the forest at once. In this paper, we demonstrate that the Euler tour tree, an existing sequential dynamic trees data structure, can be parallelized in the batch setting. For a batch of $k$ updates over a forest of $n$ vertices, our parallel Euler tour trees perform $O(k \log (1 + n/k))$ expected work with $O(\log n)$ depth with high probability. Our work bound is asymptotically optimal, and we improve on the depth bound achieved by Acar et al. for the batch-parallel dynamic trees problem. The main building block for parallelizing Euler tour trees is a batch-parallel skip list data structure, which we believe may be of independent interest. Euler tour trees require a sequence data structure capable of joins and splits. Sequentially, balanced binary trees are used, but they are difficult to join or split in parallel. We show that skip lists, on the other hand, support batches of joins or splits of size $k$ over $n$ elements with $O(k \log (1 + n/k))$ work in expectation and $O(\log n)$ depth with high probability. We also achieve the same efficiency bounds for augmented skip lists, which allows us to augment our Euler tour trees to support subtree queries. Our data structures achieve between 67--96x self-relative speedup on 72 cores with hyper-threading on large batch sizes. Our data structures also outperform the fastest existing sequential dynamic trees data structures empirically.
BibTeX
@inproceedings{tseng2019batch,
  author = {Thomas Tseng and Laxman Dhulipala and Guy E. Blelloch},
  title = {{Batch-Parallel Euler Tour Trees}},
  booktitle = {ALENEX},
  year = {2019},
  doi = {10.1137/1.9781611975499.8},
}
Figure