A scheduling algorithm for grid workflow using bottleneck detection and load balancing. Issue 3 (19th August 2014) - Smanchat, Sucha; Sritawathon, Suchon
Abstract : Purpose: This paper proposes 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 distributed of tasks across available grid resources, which is referred to as 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 in order 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 having 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.