| Zheng (Eddy) Zhang |
| Mon 04 Dec 2017, 15:00 - 16:00 |
| IF 4.31/4.33 |
If you have a question about this talk, please contact: Allison Kruk (v1atayl6)
Title
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing
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. 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(d_{max}*sqrt(log(n)log(k))) apply to a restricted class of graphs. We further 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.
Biography
Zheng (Eddy) Zhang is an assistant professor in the Department of Computer Science at Rutgers University. She received the B.S. degree in Electronic Engineering from Shanghai Jiao Tong University, in 2004, and the M.S. and Ph.D. degrees in Computer Science from the College of William & Mary, in 2007 and 2012, respectively. Her research is generally in the area of compilers and programming systems, with a focus on development, compilation, and execution of large-scale application on many-core parallel architecture. She is the recipient of Google Faculty Research Award 2014, the Best Paper Award at PPoPP 2010, and the Best Student Paper Award at QEST 2008.