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

Gao, Guang R.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.University of Delaware, Department of Electrical and Computer EngineeringM.S