Bilkent University
Department of Computer Engineering
CS 590/690 SEMINAR
DM-based Partition Refiner for Accelerating Parallel Graph Applications
Serdar Özata
Master Student
(Supervisor:Prof.Dr.Cevdet Aykanat)
Computer Engineering Department
Bilkent University
Abstract: Parallel graph applications, such as Sparse Matrix-Dense Matrix Multiplication (SpMM) and Graph Neural Network (GNN) training, rely on partitioning for distributed-memory execution. This partitioning creates irregular communication. Traditional solutions use homogeneous communication schemes, such as expand-only (sending only inputs) or reduce-only (sending only partial results). In contrast, heterogeneous communication schemes reduce data exchange by allowing each message to mix both types of data. The optimal mix for a message is encoded by a Minimum Vertex Cover (MVC) on its bipartite dependency graph. In this work, we introduce novel MVC models to further decrease the total communication volume of these irregular messages. For undirected graphs, we exploit symmetry to halve the computational overhead of this process. Experimental results on parallel SpMM show that our methods significantly reduce communication volume and improve application runtime compared to both standard expand-only schemes and base heterogeneous schemes.
DATE: November 17, Monday @ 15:30 Place: EA 502