X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Handling Recoverable Temporal Violations in Scientific Workflow Systems: A Workflow Rescheduling Based Strategy

Xiao Liu1, Jinjun Chen1, Zhangjun Wu2, Zhiwei Ni2, Dong Yuan1, Yun Yang1

1CS3, Swinburne University of Technology Melbourne, Australia

2Institute of Intelligent Management, Hefei University of Technology Hefei, China

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Outline

> Background

– Workflow Technology Group

– SwinDeW Family

– SwinGrid, SwinCloud

> Workflow Rescheduling

– Workflow Rescheduling

– Temporal Violations

– A Two Stage Workflow Local Rescheduling Strategy

– Evaluation

> Summary

2

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Workflow Technology Group Overview

> About Us: WT group is a part of CS3 (The Centre for Complex Software Systems and Services), a Tier-1 university research centre at Swinburne University of Technology. Our group conducts research into workflow technologies for complex software systems and services including peer-to-peer, grid, and cloud computing based e-science, e-business, transactional and inter-organisational workflows.

3

Leader:Prof Yun Yang

Visitors (7-8/09):Prof Lee OsterweilProf. Lori Clarke

Researchers:Dr Jinjun ChenNauman Saeed (PhD)Qiang He (PhD)Ke Liu (PhD)Xiao Liu (PhD)Dong Yuan (PhD)Zhangjun Wu (PhD - visitor)

Others:Prof Ryszard KowalczykProf Chengfei Liu

Dr Jun Yan (Wollongong)Prof Hai Jin (HUST)Prof Mingshu Li (ISCAS)Prof Qing Wang (ISCAS)Prof Zhiwei Ni (HFUT)Prof Jinpeng Huai (BUAA)

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

SwinDeW Family

SwinDeW – Swinburne Decentralised Workflow- foundation prototype based on p2p

> SwinDeW – past

> SwinDeW-A (for Agents) – ARC DP06

> SwinDeW-G (for Grid) – past

> SwinDeW-V (for Verification) – current (pending ARC DP)

> SwinDeW-E (for eScience) – current (pending ARC DP)

> SwinDeW-C (for cloud) – current (ARC LP)

> Others: SwinDeW-B / -S / -P / -G – past

4

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

SwinGrid to SwinCloud

5

Swinburne Computing Facilities

Astrophysics Supercomputer

VMware

Cloud Simulation Environment

Data Centres with Hadoop

· GT4· SuSE Linux

Swinburne CS3

…...

…...

· GT4· CentOS Linux

Swinburne ESR

…...

…...

· GT4· CentOS Linux

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Outline

> Background

– Workflow Technology Group

– SwinDeW Family

– SwinGrid, SwinCloud

> Workflow Rescheduling

– Workflow Rescheduling

– Temporal Violations

– A Two Stage Workflow Local Rescheduling Strategy

– Evaluation

> Summary

6

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Workflow Rescheduling

> A workflow scheduling is a process that maps the execution of inter-dependent workflow tasks on the distributed resources. It allocates suitable resources to workflow tasks so that the execution can be completed to satisfy objective functions imposed by users.

> Workflow rescheduling is a process to regenerate or modify the current scheduling plan, due to

– Changes of system environments: resource pool change, resource performance variance, resource break down, etc.

– Contract (constraint) violations: task execution failures, temporal violations, cost violations, etc.

– Many others: when the current scheduling plan cannot satisfy the pre-defined functional or non-functional objectives

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Workflow Rescheduling

> Workflow rescheduling plays an equally or even more important role as workflow scheduling in highly distributed and dynamic computing environments

– As a supplement function to workflow scheduling in the resource management component

– As a function in the exception handling component

> Example rescheduling strategy:

– Rescheduling by Stop and Restart

– Rescheduling by Processor Swapping

> Simple (little additional programming); high cost for resource reservation

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Temporal Violations

> Most scientific workflows are subjected to

– Local temporal constraints (milestones) for workflow segments

– Global temporal constraints (deadlines) for workflow instance

> Violations of local and global temporal constraints

– Detection: Temporal Checkpoint Selection (ICSE08, TOSEM10)

– Handling: Time deficits compensation (CCPE07, CCGrid10)

> Statistical recoverable temporal violations

– Probability based temporal consistency model (BPM08, ICSP09)

– Based on “3sigm” rule in statistics

– Details omitted, please refer the paper for details

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Outline

> Background

– Workflow Technology Group

– SwinDeW Family

– SwinGrid, SwinCloud

> Workflow Rescheduling

– Workflow Rescheduling

– Temporal Violations

– A Two Stage Workflow Local Rescheduling Strategy

– Evaluation

> Summary

10

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

A Two Stage Workflow Local Rescheduling Strategy

> For handling temporal violations

> Key objective: reduce or ideally remove the time deficit at the current checkpoint, i.e. to reduce the execution time of the subsequent activities after the checkpoint in the violated workflow segment as much as possible

> Requirement 1: fighting good balance between time deficit compensation and the completion time of other activities (workflow activities and general tasks, with or without temporal constraints) – from the overall makespan perspective

> Requirement 2: utilising available resources in the system rather than recruiting additional resources – from the overall cost perspective

11

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Integrated Task Resource List

12

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

13

Pseudo-code for An Abstract Strategy

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Evaluation

> Two example implementation of our strategy

– An ant colony optimisation based strategy

– A genetic algorithm based strategy

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Optimisation on Total Makespan

15

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Optimisation on Total Cost

16

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Compensation on Violated Workflow Segment

17

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Fitness Value

18

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

CPU Time

19

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Experiment Results on Temporal Violation Rates

20

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Outline

> Background

– Scientific Workflows

– Workflow Scheduling and Rescheduling

> Workflow Scheduling

– Classification

– Representative Scheduling Algorithms

> Workflow Rescheduling

– Classification

– A Two Stage Workflow Local Rescheduling Strategy

– Case Study 1:GA Based Rescheduling

– Case Study 2: ACO Based Rescheduling

– Comparison

> Summary

21

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

Summary

> Workflow Rescheduling – Exception Handling

> Exception Handling on Scientific Workflow Temporal Violations

– A Two Stage Workflow Local Rescheduling Strategy

• ACO, GA

– Automatic, Cost-Effective

> Future Work

– Data movement cost

– More scheduling algorithms

22

X. Liu , J. Chen , Z. Wu , Z. Ni , D. Yuan , Y. Yang, CCGrid10, 20-05-2010, Melbourne, Australia

The End – Thank You!

> Any questions or comments?

> Email: xliu@swin.edu.au

> Website: http://www.ict.swin.edu.au/personal/xliu/

> CS3: http://www.swinburne.edu.au/ict/research/cs3/

23