The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Poster Type: ACM Student Research Competition, Graduate
Author: Kalsuda Lapborisuth (Georgia Institute of Technology), Srinivas Aluru (Georgia Institute of Technology)
Supervisor: Srinivas Aluru (Georgia Institute of Technology)
Abstract: We tackle the challenge of breadth-first traversal (BFT) on sparse graphs with a high number of connected components. We propose a novel distributed-memory parallel algorithm that uses the label propagation (LP) algorithm to perform BFT on all connected components of the graph simultaneously. In synthetic benchmarks with RMAT-like graphs, we show that our LP-based algorithm can be up to 77x faster compared to the parallel direction-optimized BFS in the Combinatorial BLAS library, while scaling up to 1.5k CPU cores.
Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF