Architecture-Aware Graph (Re)Partitioning

Type PhD Proposal
Start Date August 4, 2016 11:30 AM
End Date August 4, 2016 12:30 PM
Location 6106 SENSQ
Organizer Name
Speaker Name Angen Zheng
Speaker Affiliation University of Pittsburgh Ph.D. Candidate
Abstract Graph partitioning and repartitioning has been studied for decades in literature. Yet, it is receiving more and more attention due to the increasing popularity of large graph datasets from various areas. Traditional well-studied graph (re)partitioners often scale poorly against these graphs. Recent work on streaming graph partitioning and lightweight graph repartitioning help address the problem to some extend. However, they usually assume a homogeneous computing environment. Unfortunately, modern parallel architectures often exhibit highly nonuniform network communication costs. A few solutions have been proposed to grouping neighbouring vertices as close as possible. However, the network may no longer be the only bottleneck due to the presence RDMA-enabled networks because RDMA-enable networks, nowadays, can deliver comparable network bandwidth as memory bandwidth. In contrast, putting too much data communication into partitions that are assigned to the same machines may lead to serious resource contention in the memory subsystems of modern multicore machines, causing adversary performance impact. This thesis aims to propose new scalable graph (re)partitioners that take both the communication heterogeneity and resource contention issue into account while (re)partitioning.