@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",

note = "Publisher Copyright: {\textcopyright} 2019 ACM. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 48th International Conference on Parallel Processing, ICPP 2019 ; Conference date: 05-08-2019 Through 08-08-2019",

year = "2019",

month = aug,

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",

}