Bilkent University
Department of Computer Engineering
M.S.THESIS PRESENTATION
Models and methods for 2D graph partitioning encoding simultaneous edge and vertex load balancing
Erkin Aydın
Master Student
(Supervisor: Prof. Dr. Cevdet Aykanat )
Computer Engineering Department
Bilkent University
Abstract: Standard 1D vertex partitioning models face scalability bottlenecks in distributed-memory graph applications because exceptionally high-degree vertices in scale-free graphs hinder balanced computational load distribution. In contrast, while 2D edge-based partitioning introduces greater degrees of freedom to relax load-balancing constraints and yield higher-quality solutions, it requires balancing edge and vertex computation loads simultaneously. A recent work proposed 2D bipartite graph models to address this issue; however, these models fail to accurately encode the communication volume. This thesis proposes novel 2D hypergraph models designed to achieve simultaneous edge and vertex load balancing. The main contributions of this work are an edge-hypergraph model that correctly encodes both computation loads of edges and communication volume, an Inverse Vertex Load Distribution (IVLD) heuristic to encode computation loads of vertices, an a priori edge-clustering technique that constructs a medium-grain hypergraph model to improve initial coarsening, and a refinement scheme to improve partition quality by completing the uncoarsening phase. We selected GCN training as a sample application since it utilizes highly scale-free graphs and necessitates computations on both edges and vertices at different algorithmic stages. The proposed models are evaluated against baseline 1D and existing 2D bipartite models based on computational load balance, communication volume, and parallel runtime across hundreds of real-world, skewed GNN instances. Parallel runtime experiments, conducted on a Tier-0 supercomputer, LUMI, using up to 32K cores, demonstrate the importance of accurately encoding communication costs and computation loads.
DATE: August 10, Monday @ 15:00
Place: Zoom
https://zoom.us/j/3559981145?pwd=Z25NWU5ra2FGVEptZ0pSeG5GVkZ3Zz09&omn=94715590631
Join Zoom
https://zoom.us/launch/jc/94715590631