Poster : 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

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

Jiawen Sun, Hans Vandierendonck, Dimitrios S. Nikolopoulos

School of Electronics, Electrical Engineering and Computer Science

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

3 Citations (Scopus)

282 Downloads (Pure)

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 ACM International Symposium on Principles and Practice of Parallel Programming
Publisher	Association for Computing Machinery
Pages	391-392
Number of pages	2
ISBN (Electronic)	9781450362252
ISBN (Print)	978-1-4503-6225-2
DOIs	https://doi.org/10.1145/3293883.3295703 https://doi.org/10.1145/3293883.3295703
Publication status	Published - 17 Feb 2019
Event	24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019 - Washington, United States Duration: 16 Feb 2019 → 20 Feb 2019

Conference

Conference	24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019
Country/Territory	United States
City	Washington
Period	16/02/2019 → 20/02/2019

ASJC Scopus subject areas

Software

Access to Document

10.1145/3293883.3295703Licence: Unspecified
10.1145/3293883.3295703

Poster : VEBO: A Vertex- and Edge-Balanced Ordering Heuristic to Load Balance Parallel Graph Processing
Copyright 2018 ACM. This work is made available online in accordance with the publisher’s policies. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 559 KBLicence: Unspecified

Cite this

Sun, J., Vandierendonck, H., & Nikolopoulos, D. S. (2019). Poster : VEBO: A Vertex- and Edge-Balanced Ordering Heuristic to Load Balance Parallel Graph Processing. In Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming (pp. 391-392). Association for Computing Machinery. https://doi.org/10.1145/3293883.3295703, https://doi.org/10.1145/3293883.3295703

@inproceedings{8d31a0a49e4c47218192e849dbaf5986,

title = "Poster : 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 = "17",

doi = "10.1145/3293883.3295703",

language = "English",

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

pages = "391--392",

booktitle = "Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming",

publisher = "Association for Computing Machinery",

address = "United States",

note = "24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019 ; Conference date: 16-02-2019 Through 20-02-2019",

}

Sun, J, Vandierendonck, H & Nikolopoulos, DS 2019, Poster : VEBO: A Vertex- and Edge-Balanced Ordering Heuristic to Load Balance Parallel Graph Processing. in Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, pp. 391-392, 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019, Washington, United States, 16/02/2019. https://doi.org/10.1145/3293883.3295703, https://doi.org/10.1145/3293883.3295703

Poster : VEBO: A Vertex- and Edge-Balanced Ordering Heuristic to Load Balance Parallel Graph Processing. / Sun, Jiawen; Vandierendonck, Hans; Nikolopoulos, Dimitrios S.
Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, 2019. p. 391-392.

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

TY - GEN

T1 - Poster : 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/17

Y1 - 2019/2/17

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.

UR - http://www.scopus.com/inward/record.url?scp=85064211198&partnerID=8YFLogxK

U2 - 10.1145/3293883.3295703

DO - 10.1145/3293883.3295703

M3 - Conference contribution

AN - SCOPUS:85064211198

SN - 978-1-4503-6225-2

SP - 391

EP - 392

BT - Proceedings of the ACM International Symposium on Principles and Practice of Parallel Programming

PB - Association for Computing Machinery

T2 - 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019

Y2 - 16 February 2019 through 20 February 2019

ER -

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

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this