Stage-Warping Load Sharing Strategy for Fine Grain Applications over Grid Environments

Abstract

A Load sharing strategy is one of important keys to improve the performance of computing systems. Nowadays, large scale computing system can be created by aggregating multiple computing clusters from different organizations using Grid technology. However, it is difficult to define a practical load sharing strategy due to the computing heterogeneity and dynamic behavior of Grid resources. In this work, we introduce a load sharing strategy for distributing workloads among participating clusters. The proposed strategy implements a new job-stealing technique called “stage-warping”, for dynamically adjusting the amount of assigned workloads for each cluster during an execution. In our strategy, the entire workloads are divided into stages which enable the total control of workload assignment during an execution, while still being highly robust against performance fluctuation and information inaccuracy of the computing resources. During execution, faster-than-expected clusters which will finish the assigned workloads during each stage before other clusters will steal left-over workloads from other clusters and let them skip or warp to the foremost stage. This will make all clusters to be fully utilized by finishing their assigned workloads almost at the same time near the end of each stage, resulting in a better overall parallel performance of load sharing strategy. We evaluate our proposed strategy using a set of simulation experiments based on the parameters from the available computing resources in Thaigrid, as well as, fine-grain applications which can serve as an example of computationally intensive applications. The results show that our proposed strategy can achieve better parallel runtimes when being compared to other existing methods, especially when the estimator of the underlying system is not accurate.