Massively parallel breadth first search using a tree-structured memory model

Analysis of massive graphs has emerged as an important area for massively parallel computation. In this paper, it is shown how the Fresh Breeze trees-of-chunks memory model may be used to perform breadth-first search of large undi-rected graphs. Overall, the computation can be expressed as a data flow process wherein a set of vertices to be searched is partitioned into a set of sub-domains and processed inde-pendently by many concurrent tasks. The main contributions of the paper are listed below. • We present the first case study demonstrating the power of the Fresh Breeze program execution model (PXM) in the exploitation of fine-grain parallelism found in irregular applications such as graph algorithms. • We present a novel parallel breadth-first search algo-rithm which is fully determinate. • We describe a unique sparse vector representation that represents the set of adjacencies for each vertex. • We provide an experimental study and analysis of our implementation. An estimate is also made of the per-formance that might be achieved with a massively par-allel system built according to Fresh Breeze principles