K-way Balanced Graph Partitioning for Parallel Computing

Abstract

In modern computing, high-performance computing (HPC) and parallel computing require most of the decision-making in terms of distributing the payloads (input) uniformly across the available set of resources, majorly processors; the former deals with the hardware and its better utilization. In parallel computing, a larger, complex problem is broken down into multiple smaller calculations and executed simultaneously on several processors. The efficient use of resources (processors) plays a vital role in achieving the maximum throughput which necessitates uniform load distribution across available processors, i.e. load balancing.
The load balancing in parallel computing is modeled as a graph partitioning problem. In the graph partitioning problem, the weighted nodes represent the computing cost at each node, and the weighted edges represent the communication cost between the connected nodes. The goal is to partition the graph G into k partitions such that: I) the sum of weights on the nodes is approximately equal for each partition, and, II) the sum of weights on the edges across different partitions is minimum.  In this paper, a novel node-weighted and edge-weighted k-way balanced graph partitioning (NWEWBGP) algorithm of  O(n x n)  is proposed. The algorithm works for all relevant values of k, meets or improves on earlier algorithms in terms of balanced partitioning and lowest edge-cut. For evaluation and validation, the outcome is compared with the ground truth benchmarks.