Bilkent University
Department of Computer Engineering

---

CS 590 SEMINAR

 

A two-phase methodology for capturing true communication volume in graph partitioning

 

Başak Ünsal
MS Student
Computer Engineering Department
Bilkent University

Graphs are common structures that are used to parallelize sparse matrix operations in scientific computing. For representing nonsymmetric matrices and partitioning them for parallel processing usually bipartite graphs are used. In partitioning with graphs, one of the most common objective is to minimize the inter-process communication for an efficient parallelization, which is also referred to as the total communication volume. This widely used standard graph model has a well-known flaw in which it fails to correctly capture the volume incurred in parallel operations. In this work, we propose a methodology that overcomes this shortcoming in two phases. The proposed model has other advantages over the standard graph model apart from capturing the true communication volume as it considers other communication cost metrics such maximum communication volume and an approximation of the number of messages. We test the validity of our methodology with matrices from different domains using the most common graph partitioner MeTiS.

 

DATE: 04 April, 2016, Monday @ 16:40
PLACE: EA-409