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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Forthcoming

    View graph of relations

    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 languageEnglish
    Title of host publicationProceedings of the ACM International Symposium on Principles and Practice of Parallel Programming
    PublisherACM
    Number of pages2
    DOIs
    Publication statusAccepted - 14 Nov 2018
    EventACM International Symposium on Principles and Practice of Parallel Programming - Washington, United States
    Duration: 16 Feb 201920 Feb 2019
    https://ppopp19.sigplan.org/

    Conference

    ConferenceACM International Symposium on Principles and Practice of Parallel Programming
    Abbreviated titlePPoPP
    CountryUnited States
    CityWashington
    Period16/02/201920/02/2019
    Internet address

    ID: 162867959