A scheduling algorithm for grid workflow using bottleneck detection and load balancing

摘要

Purpose - This paper aims to propose a scheduling technique for parameter sweep workflows, which are used in parametric study and optimization. When executed in multiple parallel instances in the grid environment, it is necessary to address bottleneck and load balancing to achieve an efficient execution. Design/methodology/approach - A bottleneck detection approach is based on commonly known performance metrics of grid resources. To address load balancing, a resource requirement similarity metric is introduced to determine the likelihood of the distribution of tasks across available grid resources, which is referred to as an execution context. The presence of a bottleneck and the execution context are used in the main algorithm, named ABeC, to schedule tasks selectively at run-time to achieve a better overall execution time or makespan. Findings - According to the results of the simulations against four existing algorithms using several scenarios, the proposed technique performs, at least, similarly to the existing four algorithms in most cases and achieves better performance when scheduling workflows have a parallel structure. Originality/value - The bottleneck detection and the load balancing proposed in this paper require only common resource and task information, rendering it applicable to most workflow systems. The proposed scheduling technique, through such selective behaviour, may help reduce the time required for the execution of multiple instances of a grid workflow that is to be executed in parallel.