Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.14778/2556549.2556581 | PVLDB |
Keywords | Field | DocType |
familiar vertex-centric programming paradigm,iterative graph processing application,graph program,computationally light graph application,block-oriented execution,block updates,block-aware graph processing runtime,graph programming framework,computation model,iterative graph computation,graph application,large graph | Vertex (geometry),Programming paradigm,Computer science,Parallel computing,Theoretical computer science,Graph bandwidth,Iterated function,Database,Graph (abstract data type),Scalability,Speedup,Computation | Journal |
Volume | Issue | ISSN |
6 | 14 | 2150-8097 |
Citations | PageRank | References |
34 | 0.97 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenlei Xie | 1 | 486 | 22.55 |
| Guozhang Wang | 2 | 403 | 17.55 |
| David Bindel | 3 | 427 | 29.24 |
| A J Demers | 4 | 8151 | 2084.66 |
| Johannes Gehrke | 5 | 13362 | 1055.06 |