Poster : VEBO: A Vertex- and Edge-Balanced Ordering Heuristic to Load Balance Parallel Graph Processing
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Forthcoming
This work proposes Vertex- and Edge-Balanced Ordering (VEBO): balance the number of edges and the number of unique destinations of those edges. VEBO balances edges and vertices for graphs with a power-law degree distribution, and ensures an equal degree distribution between partitions. Experimental evaluation on three shared-memory graph processing systems (Ligra, Polymer and GraphGrind) shows that VEBO achieves excellent load balance and improves performance by 1.09× over Ligra, 1.41× over Polymer and 1.65× over GraphGrind, compared to their respective partitioning algorithms, averaged across 8 algorithms and 7 graphs. VEBO improves GraphGrind performance with a speedup of 2.9× over Ligra on average.
DOI
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming |
| Publisher | ACM |
| Number of pages | 2 |
| DOIs | |
| Publication status | Accepted - 14 Nov 2018 |
| Event | ACM International Symposium on Principles and Practice of Parallel Programming - Washington, United States Duration: 16 Feb 2019 → 20 Feb 2019 https://ppopp19.sigplan.org/ |
Conference
| Conference | ACM International Symposium on Principles and Practice of Parallel Programming |
|---|---|
| Abbreviated title | PPoPP |
| Country | United States |
| City | Washington |
| Period | 16/02/2019 → 20/02/2019 |
| Internet address |
ID: 162867959