{"id":402,"date":"2019-02-05T17:18:00","date_gmt":"2019-02-05T17:18:00","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/vebo-a-vertex-and-edge-balanced-ordering-heuristic-to-load-balance-parallel-graph-processing-poster\/"},"modified":"2019-02-05T17:18:00","modified_gmt":"2019-02-05T17:18:00","slug":"vebo-a-vertex-and-edge-balanced-ordering-heuristic-to-load-balance-parallel-graph-processing-poster","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/vebo-a-vertex-and-edge-balanced-ordering-heuristic-to-load-balance-parallel-graph-processing-poster\/","title":{"rendered":"VEBO: a vertex- and edge-balanced ordering heuristic to load balance parallel graph processing (Poster)"},"content":{"rendered":"\n<p><\/p>\n\n\n\n<p><a href=\"https:\/\/doi.org\/10.1145\/3293883.3295703\">https:\/\/doi.org\/10.1145\/3293883.3295703<\/a><\/p>\n\n\n\n<p>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\u00d7 over Ligra, 1.41\u00d7 over Polymer and 1.65\u00d7 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\u00d7 over Ligra on average.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/doi.org\/10.1145\/3293883.3295703 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) [&hellip;]<\/p>\n","protected":false},"author":974,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[24],"tags":[26,27],"class_list":{"0":"post-402","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-graphgrind","7":"tag-locality","8":"tag-numa-2","9":"czr-hentry"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/402","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/974"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=402"}],"version-history":[{"count":0,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/402\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=402"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=402"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=402"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}