Distributed-Memory Breadth-First Search on Massive Graphs
Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Distributed-Memory Breadth-First Search on Massive Graphs

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.


Top