A low-cost rescheduling policy for efficient mapping of workflows on grid systems

Issue title: AxGrids 2004

Article type: Research Article

Authors: Sakellariou, Rizos | Zhao, Henan

Affiliations: School of Computer Science, University of Manchester, Oxford Road, Manchester M13 9PL, UK. E-mail: {rizos, hzhao}@cs.man.ac.uk

Abstract: Workflow management is emerging as an important service in Grid computing. A simple model that can be used for the representation of certain workflows is a directed acyclic graph. Although many heuristics have been proposed to schedule such graphs on heterogeneous environments, most of them assume accurate prediction of computation and communication costs. This limits their direct applicability to a dynamically changing environment, such as the Grid. In this environment, an initial schedule may be built based on estimates, but run-time rescheduling may be needed to improve application performance. This paper presents a low-cost rescheduling policy, which considers rescheduling at a few, carefully selected points during the execution. This policy achieves performance results, which are comparable with those achieved by a policy that dynamically attempts to reschedule before the execution of every task.

Journal: Scientific Programming, vol. 12, no. 4, pp. 253-262, 2004