@conference{10.1145/3078505.3078520,
title = {A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing},
author = {Lingda Li and Robel Geda and Ari B Hayes and Yanhao Chen and Pranav Chaudhari and Eddy Z Zhang and Mario Szegedy},
url = {https://doi.org/10.1145/3078505.3078520},
doi = {10.1145/3078505.3078520},
isbn = {9781450350327},
year = {2017},
date = {2017-01-01},
booktitle = {Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (Sigmetrics 2017)},
pages = {6},
publisher = {Association for Computing Machinery},
address = {Urbana-Champaign, Illinois, USA},
series = {SIGMETRICS ’17 Abstracts},
abstract = {Graph edge partition models have recently become an appealing alternative to graph vertex partition models for distributed computing due to both their flexibility in balancing loads and their performance in reducing communication cost.In this paper, we propose a simple yet effective graph edge partitioning algorithm. In practice, our algorithm provides good partition quality while maintaining low partition overhead. It also outperforms similar state-of-the-art edge partition approaches, especially for power-law graphs. In theory, previous work showed that an approximation guarantee of O(dmax√(log n log k)) apply to the graphs with m=Ω(k2) edges (n is the number of vertices, and k is the number of partitions). We further rigorously proved that this approximation guarantee hold for all graphs.We also demonstrate the applicability of the proposed edge partition algorithm in real parallel computing systems. We draw our example from GPU program locality enhancement and demonstrate that the graph edge partition model does not only apply to distributed computing with many computer nodes, but also to parallel computing in a single computer node with a many-core processor.},
keywords = {Data sharing, Edge-partition, GPU, Graph model, Program locality},
pubstate = {published},
tppubtype = {conference}
}