SPIRIT: a runtime system for distributed irregular tree applications

Nikhil Hegde, Jianqiao Liu, and Milind Kulkarni

PPoPP 2016 · Principles and Practices of Parallel Programming · pp. 51:1-51:2

Poster

Abstract

Repeated, depth-first traversal of trees is a common algorithmic pattern in an important set of applications from diverse domains such as cosmological simulations, data mining, and computer graphics. As these applications operate over massive data sets, it is often necessary to distribute the trees to process all of the data.

In this work, we introduce SPIRIT, a runtime system to ease the writing of distributed tree applications. SPIRIT automates the challenging tasks of tree distribution, optimizing communication and parallelizing independent computations. The common algorithmic pattern in tree traversals is exploited to effectively schedule parallel computations and improve locality. As a result, pipeline parallelism in distributed traversals is identified, which is complemented by load-balancing, and locality-enhancing, message aggregation optimizations. Evaluation of SPIRIT on tree traversal in Point Correlation (PC) shows a scalable system, achieving speedups upto 38x on a 16-node, 64 process system compared to a 1-node, baseline configuration. We also find that SPIRIT results in substantially less communication and achieves significant performance improvements over implementations in other distributed graph systems.

BibTeX

@inproceedings{hegde16ppopp,
  author    = {Nikhil Hegde and Jianqiao Liu and Milind Kulkarni},
  title     = {{SPIRIT}: a runtime system for distributed irregular tree applications},
  booktitle = {Proceedings of the Principles and Practices of Parallel Programming (PPoPP)},
  pages     = {51:1--51:2},
  year      = {2016},
  doi       = {10.1145/3016078.2851177}
}

Group members