A 2D parallel triangle counting algorithm for distributed-memory architectures

Ancy Sarah Tom, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Triangle counting is a fundamental graph analytic operation that is used extensively in network science and graph mining. As the size of the graphs that needs to be analyzed continues to grow, there is a requirement in developing scalable algorithms for distributed-memory parallel systems. To this end, we present a distributed-memory triangle counting algorithm, which uses a 2D cyclic decomposition to balance the computations and reduce the communication overheads. The algorithm structures its communication and computational steps such that it reduces its memory overhead and includes key optimizations that leverage the sparsity of the graph and the way the computations are structured. Experiments on synthetic and real-world graphs show that our algorithm obtains an average relative speedup range between 3.24 to 7.22 out of 10.56 across the datasets using 169 MPI ranks over the performance achieved by 16 MPI ranks. Moreover, we obtain an average speedup of 10.2 times on comparison with previously developed distributed-memory parallel algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th International Conference on Parallel Processing, ICPP 2019
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450362955
DOIs
StatePublished - Aug 5 2019
Event48th International Conference on Parallel Processing, ICPP 2019 - Kyoto, Japan
Duration: Aug 5 2019Aug 8 2019

Publication series

NameACM International Conference Proceeding Series

Conference

Conference48th International Conference on Parallel Processing, ICPP 2019
CountryJapan
CityKyoto
Period8/5/198/8/19

    Fingerprint

Keywords

  • Distributed-memory
  • Graph analytics
  • Triangle counting

Cite this

Tom, A. S., & Karypis, G. (2019). A 2D parallel triangle counting algorithm for distributed-memory architectures. In Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019 [a45] (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3337821.3337853