An Efficient Load Balancing Scheme for Grid-based High Performance Scientific Computing

With the emergence of computational grids, there has been a dramatic increase in the number of available processing and storing resources available for parallel execution of large-scale compute and data intensive scientific applications. However, large computing power in itself is not sufficient for high performance computing (HPC). In this context, (application) partitioning and load balancing strategies play a critical role in meeting the high performance requirements and in achieving high processor utilization. In HPC applications such as molecular simulations, protein synthesis, drug design et cetera parallel loops constitute the greatest percentage of program parallelism. The degree to which parallelism can be exploited during parallel execution of a nested loop directly depends on partitioning and load balance, i.e., the number of iterations mapped onto each processor, between the different processors. Thus, partitioning of parallel loops is of key importance for grid-based high performance scientific computing. Although a significant amount of work has been done in partitioning of iteration spaces of nested loops, both rectangular and non-rectangular iteration spaces, for homogeneous multiprocessor systems, the problem of partitioning of iteration spaces for heterogeneous systems has not been given enough attention so far. In this paper, we present a geometric approach for partitioning N-dimensional non-rectangular iteration spaces for optimizing performance on heterogeneous parallel processor systems. Speedup measurements for kernels (loop nests) of linear algebra packages, scientific applications such as climate modeling and literature are presented