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

Abstract

Analysis of massive graphs has emerged as an important area for massively parallel computation. In this thesis, it is shown how the Fresh Breeze tree-based memory model may be used to perform breadth-first search of large undirected graphs. The main contributions of this thesis are: • We present the first case study demonstrating the power of the Fresh Breeze program execution model in the exploitation of fine-grain parallelism found in irregular applications such as graph algorithms. • We present a novel parallel breadth-first search algorithm 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 performance that might be achieved with a massively parallel system built according to Frech Breeze principles.