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

Memory architecture
Data storage equipment
Communication
Parallel algorithms
Decomposition
Experiments

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

A 2D parallel triangle counting algorithm for distributed-memory architectures. / Tom, Ancy Sarah; Karypis, George.

Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019. Association for Computing Machinery, 2019. a45 (ACM International Conference Proceeding Series).

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

Tom, AS & 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, 48th International Conference on Parallel Processing, ICPP 2019, Kyoto, Japan, 8/5/19. https://doi.org/10.1145/3337821.3337853
Tom AS, Karypis G. A 2D parallel triangle counting algorithm for distributed-memory architectures. In Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019. Association for Computing Machinery. 2019. a45. (ACM International Conference Proceeding Series). https://doi.org/10.1145/3337821.3337853
Tom, Ancy Sarah ; Karypis, George. / A 2D parallel triangle counting algorithm for distributed-memory architectures. Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019. Association for Computing Machinery, 2019. (ACM International Conference Proceeding Series).
@inproceedings{6c216f858917456c8cd95854768e9223,
title = "A 2D parallel triangle counting algorithm for distributed-memory architectures",
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.",
keywords = "Distributed-memory, Graph analytics, Triangle counting",
author = "Tom, {Ancy Sarah} and George Karypis",
year = "2019",
month = "8",
day = "5",
doi = "10.1145/3337821.3337853",
language = "English (US)",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
booktitle = "Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019",

}

TY - GEN

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

AU - Tom, Ancy Sarah

AU - Karypis, George

PY - 2019/8/5

Y1 - 2019/8/5

N2 - 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.

AB - 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.

KW - Distributed-memory

KW - Graph analytics

KW - Triangle counting

UR - http://www.scopus.com/inward/record.url?scp=85071096572&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071096572&partnerID=8YFLogxK

U2 - 10.1145/3337821.3337853

DO - 10.1145/3337821.3337853

M3 - Conference contribution

T3 - ACM International Conference Proceeding Series

BT - Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019

PB - Association for Computing Machinery

ER -