Title :
Investigating Graph Algorithms in the BSP Model on the Cray XMT
Author :
Ediger, David ; Bader, David A.
Author_Institution :
Georgia Inst. of Technol., Atlanta, GA, USA
Abstract :
Implementing parallel graph algorithms in large, shared memory machines, such as the Cray XMT, can be challenging for programmers. Synchronization, deadlock, hot spotting, and others can be barriers to obtaining linear scalability. Alternative programming models, such as the bulk synchronous parallel programming model used in Google´s Pregel, have been proposed for large graph analytics. This model eases programmer complexity by eliminating deadlock and simplifying data sharing. We investigate the algorithmic effects of the BSP model for graph algorithms and compare performance and scalability with hand-tuned, open source software using GraphCT. We analyze the innermost iterations of these algorithms to understand the differences in scalability between BSP and shared memory algorithms. We show that scalable performance can be obtained with graph algorithms in the BSP model on the Cray XMT. These algorithms perform within a factor of 10 of hand-tuned C code.
Keywords :
graph theory; iterative methods; parallel algorithms; parallel programming; shared memory systems; BSP model; Cray XMT; GraphCT; bulk synchronous parallel programming model; data sharing; deadlock elimination; innermost iterations; large graph analytics; open source software; parallel graph algorithms; programmer complexity; shared memory machines; Clustering algorithms; Computational modeling; Parallel programming; Scalability; Software algorithms; System recovery;
Conference_Titel :
Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International
Conference_Location :
Cambridge, MA
Print_ISBN :
978-0-7695-4979-8
DOI :
10.1109/IPDPSW.2013.107