Scheduling parameter sweep workflow in the Grid based on resource competition

Smanchat, Sucha, Indrawan, Maria, Ling, Sea, Enticott, Colin and Abramson, David (2013) Scheduling parameter sweep workflow in the Grid based on resource competition. Future Generation Computer Systems, 29 5: 1164-1183. doi:10.1016/j.future.2013.01.005

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Smanchat, Sucha
Indrawan, Maria
Ling, Sea
Enticott, Colin
Abramson, David
Title Scheduling parameter sweep workflow in the Grid based on resource competition
Journal name Future Generation Computer Systems   Check publisher's open access policy
ISSN 0167-739X
Publication date 2013-07-01
Sub-type Article (original research)
DOI 10.1016/j.future.2013.01.005
Open Access Status Not yet assessed
Volume 29
Issue 5
Start page 1164
End page 1183
Total pages 20
Place of publication Amsterdam, Netherlands
Publisher Elsevier North-Holland
Language eng
Formatted abstract
Workflow technology has been adopted in scientific domains to orchestrate and automate scientific processes in order to facilitate experimentation. Such scientific workflows often involve large data sets and intensive computation that necessitate the use of the Grid. To execute a scientific workflow in the Grid, tasks within the workflow are assigned to Grid resources. Thus, to ensure efficient execution of the workflow, Grid workflow scheduling is required to manage the allocation of Grid resources.

Although many Grid workflow scheduling techniques exist, they are mainly designed for the execution of a single workflow. This is not the case with parameter sweep workflows, which are used for parametric study and optimisation. A parameter sweep workflow is executed numerous times with different input parameters in order to determine the effect of each parameter combination on the experiment. While executing multiple instances of a parameter sweep workflow in parallel can reduce the time required for the overall execution, this parallel execution introduces new challenges to Grid workflow scheduling. Not only is a scheduling algorithm that is able to manage multiple workflow instances required, but this algorithm also needs the ability to schedule tasks across multiple workflow instances judiciously, as tasks may require the same set of Grid resources. Without appropriate resource allocation, resource competition problem could arise.

We propose a new Grid workflow scheduling technique for parameter sweep workflow called the Besom scheduling algorithm. The scheduling decision of our algorithm is based on the resource dependencies of tasks in the workflow, as well as conventional Grid resource-performance metrics. In addition, the proposed technique is extended to handle loop structures in scientific workflows without using existing loop-unrolling techniques. The Besom algorithm is evaluated using simulations with a variety of scenarios. A comparison between the simulation results of the Besom algorithm and of the three existing Grid workflow scheduling algorithms shows that the Besom algorithm is able to perform better than the existing algorithms for workflows that have complex structures and that involve overlapping resource dependencies of tasks.

Highlights ► We propose a new Grid workflow scheduling algorithm for parameter sweep workflows. ► The Besom algorithm uses resource competition to schedule multiple workflow instances. ► A single-level feedback loop can be handled during workflow execution. ► The Besom algorithm performs better for workflows with complex structure and setting.
Keyword Grid workflow
Workflow scheduler
Workflow scheduling algorithm
Parameter sweep
Resource competition
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Non HERDC
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 5 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 11 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 17 Oct 2013, 02:27:19 EST by Ms Diana Cassidy on behalf of School of Information Technol and Elec Engineering