Distributed-Memory Breadth-First Search on Massive Graphs

2017/05/10 by Buluc, Aydin, Beamer, Scott, Madduri, Kamesh +2
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1705.04590

Abstract

This chapter studies the problem of traversing large graphs using the breadth-first search order on distributed-memory supercomputers. We consider both the traditional level-synchronous top-down algorithm as well as the recently discovered direction optimizing algorithm. We analyze the performance and scalability trade-offs in using different local data structures such as CSR and DCSC, enabling in-node multithreading, and graph decompositions such as 1D and 2D decomposition.

Related

• Optimizations to the Parallel Breath First Search on Distributed Memory
• A Note on (Parallel) Depth- and Breadth-First Search by Arc Elimination
• Fast Breadth-First Search in Still Less Space
• Efficient Semi-External Breadth-First Search
• Accelerating Direction-Optimized Breadth First Search on Hybrid\n Architectures