A Unifying Programming Model for Parallel Graph Algorithms

Abstractions and programming models simplify the writing of programs by providing a clear mental framework for reasoning about problem domains and for isolating program expression from irrelevant implementation details. This paper focuses on the domain of graph algorithms, where there are several classes of details that we would like to hide from the programmer, including execution model, granularity of decomposition, and data representation. Most current systems expose some or all of these issues at the same level as their graph abstractions, constraining portability and extensibility while also negatively impacting programmer productivity. To address these challenges, this paper presents a unifying generalized SIMD-like programming model (and corresponding C++ implementation) that can be used to uniformly express graph and other irregular applications on a wide range of types of parallelism, decompositions, and data representations. With respect to these issues, we develop a detailed analysis of our approach and compare it to a number of popular alternatives.