Bilkent University
Department of Computer Engineering
Ph.D Dissertation

 

Hypergraph Models for Parallel Sparse Matrix-Matrix Multiplication

 

Kadir Akbudak
PhD Candidate
(Supervisor: Prof. Dr. Cevdet Aykanat)
Computer Engineering Department
Bilkent University

Sparse matrix-matrix multiplication (SpGEMM) of the form C = AB is a widely used kernel in many applications such as molecular dynamics simulations, graph operations and linear programming. We identify parallel formulations of SpGEMM operation for distributed-memory architectures. Using these formulations, we propose two-phase parallel SpGEMM algorithms, where communication-free local SpGEMM computations constitute the multiplication phase and transfer of required input/output matrices constitute the communication phase. For these algorithms, three hypergraph models are proposed in order to achieve simultaneous partitioning of input and output matrices without any replication of input or output data. All of the three hypergraph models perform one-dimensional (1D) partitioning of the input matrices A and B, whereas the first hypergraph model performs two-dimensional (2D) nonzero-based partitioning of the output matrix C; and the second and third models perform 1D partitioning of the output matrix C. In these models, the partitioning constraint defined on weights of vertices encodes balancing computational loads of processors during the multiplication phase of the parallel SpGEMM algorithm. The partitioning objective of minimizing the cutsize defined over the cut nets encodes minimizing the total volume of communication that will occur during the communication phase of the parallel SpGEMM algorithm.

An MPI (Message Passing Interface) based parallel SpGEMM library is developed to verify validity of our models in practice. Parallel runs of the library for a wide range of realistic SpGEMM instances on a large-scale parallel system JUQUEEN (an IBM BlueGene/Q system) show that the proposed hypergraph models attain high speedup values.

 

DATE: 18 September, 2015, Friday @ 15:00
PLACE: EA-516