A Study of Parallel Graph Processing Paradigms

The Standard Template Adaptive Parallel Library (STAPL) is a parallel superset of the C++ Standard Template Library (STL); STAPL allows execution of programs on uniprocessor and multiprocessor architecture with both shared and distributed memory. Furthermore, STAPL allows ease of development as it provides parallel counterpart of STL containers, algorithms and iterators. STAPL Graph Library (SGL) is a library built on top of the STAPL framework. SGL provides parallel graph data structures, algorithms, and various tools which are helpful in graph processing at scale. In this paper I will discuss various paradigms of execution for parallel graph processing: KLA, Level-synchronous, Asynchronous, Hierarchical, and Hubs and their effect on various inputs like the Twitter network graph, the Kronecker graph and the USA road network. We will then analyze performance of different graph paradigms using various algorithms and list the correlations it has with the topological properties of the input data and machine size.