Massively parallel breadth first search using a tree-structured memory model
Date
2013
Authors
St. John, Thomas
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
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.