Bilkent University
Department of Computer Engineering

---

CS 590/690 SEMINAR

 

2D graph partitioning models for load balancing

 

Erkin Aydın
Master Student
(Supervisor: Prof.Dr.Cevdet Aykanat)

Computer Engineering Department
Bilkent University

Abstract: In distributed-memory parallelization of irregularly sparse graphs, conventional one-dimensional (1D) partitioning models often exhibit poor scalability on scale-free graphs due to load imbalance induced by high-degree vertices. Two-dimensional (2D) partitioning alleviates this issue by providing additional degrees of freedom, thereby enabling better satisfaction of imbalance constraints and higher-quality partitions. This study introduces 2D graph and hypergraph partitioning models that achieve computational balancing on multiple metrics. Both formulations are compatible with existing partitioning tools without requiring any modification. To further reduce model complexity, a clustering scheme is proposed, lowering the size of 2D models. Experimental evaluations on approximately 180 graphs of varying skewness using GCN training on a Tier-0 HPC system demonstrate substantial scalability improvements, achieving efficient parallel performance up to 32K cores.

 

DATE: November 03, Monday @ 16:10 Place: EA 502