| The problem of partitioning irregular (unstructured) graphs and meshes for parallel computations on homogeneous systems has been extensively studied. However, these partitioning schemes 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 taking into consideration the differing capabilities of such distributed heterogeneous systems. In our model, the heterogeneous system consists of processors with varying processing power and an underlying non-uniform communication network. In this thesis, we present a novel multilevel partitioning scheme for irregular graphs and meshes, that takes into account issues pertinent to Grid computing environments. Our partitioning algorithm, called MiniMax, generates and maps partitions onto a heterogeneous system with the objective of minimizing the execution time of the parallel distributed applications. We have considered both a realistic mesh problem from NASA as well as synthetic workloads in order to study the performance of the proposed scheme, Experimental results demonstrate that MiniMax generates high quality partitions for a wide class of application types targeted for parallel execution in a distributed heterogeneous environment. Comparison of MiniMax with Metis (a popular homogeneous partitioner) shows that MiniMax outperforms Metis on the quality of partitions produced for a heterogeneous environment. For a non-uniform workload on a fully heterogeneous system, we obtain an improvement factor between 1.86 and 3.70 for execution time of the application, between 1.63 and 2.44 for load imbalance, and between 219 and 11487 for standard deviation among execution time of individual processors. |
