Graph partitioning for parallel applications in heterogeneous Grid environments

The problem of partitioning irregular graphs for parallel computations on homogeneous systems has been extensively studied. However these solutions fail when the target system architecture exhibits heterogeneity in resource characteristics. With the emergence of technologies such as the Grid, it is imperative to study the partitioning problem in the context of distributed heterogeneous systems. In our Grid model, the system consists of processors with varying computational power that are connected via a non-uniform communication network. We present a novel multilevel partitioning algorithm, called MiniMax, for irregular graphs that takes into account issues pertinent to Grid computing environments. The proposed scheme generates and maps partitions onto a heterogeneous system with the objective of minimizing the maximum execution time of the parallel distributed application. Simulation results for both synthetic and real workloads demonstrate that MiniMax generates high quality partitions for various classes of applications targeted for parallel execution in a distributed heterogeneous environment.