VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing

Jiawen Sun; Hans Vandierendonck; Dimitrios S. Nikolopoulos

doi:10.1145/3293883.3295703

VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing

Jiawen Sun, Hans Vandierendonck, Dimitrios S. Nikolopoulos

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
Place of Publication	New York, NY, USA
Publisher	ACM
Pages	391-392
Number of pages	2
ISBN (Print)	978-1-4503-6225-2
DOIs	https://doi.org/10.1145/3293883.3295703
Publication status	Published - 16 Feb 2019
Event	Principles and Practice of Parallel Programming 2019 - Washington, United States Duration: 16 Feb 2019 → 20 Feb 2019 https://ppopp19.sigplan.org/home

Publication series

Name	PPoPP '19
Publisher	ACM

Conference

Conference	Principles and Practice of Parallel Programming 2019
Abbreviated title	PPoPP 2019
Country/Territory	United States
City	Washington
Period	16/02/19 → 20/02/19
Internet address	https://ppopp19.sigplan.org/home

Access to Document

10.1145/3293883.3295703

VEBOAccepted author manuscript, 560 KB

http://doi.acm.org/10.1145/3293883.3295703

Cite this

@inproceedings{33c42e5b3a53495f9a74b060de7d312e,

title = "VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing",

abstract = "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.",

author = "Jiawen Sun and Hans Vandierendonck and Nikolopoulos, {Dimitrios S.}",

year = "2019",

month = feb,

day = "16",

doi = "10.1145/3293883.3295703",

language = "English",

isbn = "978-1-4503-6225-2",

series = "PPoPP '19",

publisher = "ACM",

pages = "391--392",

booktitle = "Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming",

note = "Principles and Practice of Parallel Programming 2019, PPoPP 2019 ; Conference date: 16-02-2019 Through 20-02-2019",

url = "https://ppopp19.sigplan.org/home",

}

Sun, J, Vandierendonck, H & Nikolopoulos, DS 2019, VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing. in Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. PPoPP '19, ACM, New York, NY, USA, pp. 391-392, Principles and Practice of Parallel Programming 2019, Washington, District of Columbia, United States, 16/02/19. https://doi.org/10.1145/3293883.3295703

VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing. / Sun, Jiawen; Vandierendonck, Hans; Nikolopoulos, Dimitrios S.
Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. New York, NY, USA: ACM, 2019. p. 391-392 (PPoPP '19).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing

AU - Sun, Jiawen

AU - Vandierendonck, Hans

AU - Nikolopoulos, Dimitrios S.

PY - 2019/2/16

Y1 - 2019/2/16

N2 - 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.

AB - 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.

U2 - 10.1145/3293883.3295703

DO - 10.1145/3293883.3295703

M3 - Conference contribution

SN - 978-1-4503-6225-2

T3 - PPoPP '19

SP - 391

EP - 392

BT - Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

PB - ACM

CY - New York, NY, USA

T2 - Principles and Practice of Parallel Programming 2019

Y2 - 16 February 2019 through 20 February 2019

ER -

VEBO: A Vertex- and Edge-balanced Ordering Heuristic to Load Balance Parallel Graph Processing

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this