Load Balancing In Parallel Computing Using Multilevel Graph Partitioning

Abstract

In parallel computing, many application problems need to efficiently decompose their computational
load on the available processors to optimize performance. This decomposition corresponds to the load
balancing in which the node weight represents cost of computational workload and the edge weight represents
cost of communication needed for node interactions. The goal is to divide graph into k-subgraphs such
that - i) the load (sum of the vertex weights) should be equal for each part to ensure an equal distribution of
load among all processors and, - ii) sum of the edge weights incident to vertices of different partitions should be
less in order to ensure minimum communication cost. In this work, multilevel graph partitioning, one of the
most important heuristic graph partitioning algorithm is discussed. Firstly, the graph is coarsened to a graph
with a small number of vertices using the Heavy Edge Matching (HEM) technique. The coarsened graph is then
partitioned using the Kernighan-Lin algorithm. The partition is finally projected back to the original graph in
the uncoarsen phase. The experimental work is analyzed and it shows promising results as compared to the
Metis tool for k-way graph partitioning in terms of a balance constraint and a minimum edge-cut constraint.
Further, it has been also observed that the results obtained by applying the Kernighan-Lin algorithm on the
coarsened graph are more time-efficient than heuristic Kernighan-Lin partitioning results on the original
graph.