Fast iterative graph computation with block updates
Authors:
Open Access
- 1 September 2013
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 6 (14) , 2014-2025
Abstract
Scaling iterative graph processing applications to large graphs is an important problem. Performance is critical, as data scientists need to execute graph programs many times with varying parameters. The need for a high-level, high-performance programming model has inspired much research on graph programming frameworks. In this paper, we show that the important class of computationally light graph applications - applications that perform little computation per vertex - has severe scalability problems across multiple cores as these applications hit an early "memory wall" that limits their speedup. We propose a novel block-oriented computation model, in which computation is iterated locally over blocks of highly connected nodes, significantly improving the amount of computation per cache miss. Following this model, we describe the design and implementation of a block-aware graph processing runtime that keeps the familiar vertex-centric programming paradigm while reaping the benefits of block-oriented execution. Our experiments show that block-oriented execution significantly improves the performance of our framework for several graph applications.Keywords
This publication has 28 references indexed in Scilit:
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph PartitioningSIAM Journal on Computing, 2013
- Greedy and randomized versions of the multiplicative Schwarz methodLinear Algebra and its Applications, 2012
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- Fast Two-scale Methods for Eikonal EquationsSIAM Journal on Scientific Computing, 2012
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Optimistic parallelism requires abstractionsACM SIGPLAN Notices, 2007
- When cache blocking of sparse matrix vector multiply works and whyApplicable Algebra in Engineering, Communication and Computing, 2007
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004
- A bridging model for parallel computationCommunications of the ACM, 1990
- Domain decomposition on parallel computersIMPACT of Computing in Science and Engineering, 1989