GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms
Authors:
- Michael J. AndersonMAMichael J. Anderson
- Narayanan SundaramNSNarayanan Sundaram
- Nadathur SatishNSNadathur Satish
- Mostofa Ali PatwaryMPMostofa Ali Patwary
- Theodore L. WillkeTWTheodore L. Willke
- Pradeep DubeyPDPradeep Dubey
- 1 May 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 313-322
Abstract
The duality between graphs and matrices means that many common graph analyses can be expressed with primitives such as generalized sparse matrix-vector multiplication (SpMSpV) and sparse matrix-matrix multiplication (SpGEMM). Achieving high performance on these primitives is challenging due to limited arithmetic intensity, irregular memory accesses, and significant network communication requirements in the distributed setting. In this paper we implement four graph applications using GraphPad, our optimized multinode implementations of generalized linear algebra primitives such as SpMSpV and SpGEMM. GraphPad is highly flexible to accommodate multiple data layouts, partitioning strategies, and incorporates communication optimizations. Our performance at scale can exceed that of CombBLAS by up to 40×. In addition to GraphPad's performance in a distributed setting, it is also within 2× the performance of GraphMat, a high performance graph framework on a single node for four out of five benchmarks. We also show our communication optimizations and flexibility are critical for good performance on both HPC clusters and commodity cloud platforms.Keywords
This publication has 21 references indexed in Scilit:
- PGX.D2015
- One trillion edgesProceedings of the VLDB Endowment, 2015
- MapGraph2014
- GraphX2013
- Green-Marl2012
- Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and ExperimentsSIAM Journal on Scientific Computing, 2012
- What is Twitter, a social network or a news media?2010
- PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations2009
- Discovering regulatory and signalling circuits in molecular interaction networksBioinformatics, 2002
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted TranspositionACM Transactions on Mathematical Software, 1978