Modeling and scheduling hybrid workflows of tasks and task interaction graphs on the cloud

Abstract

A workflow represents a complex activity that is often modeled as a Directed Acyclic Graph (DAG) in which each vertex is a task and each directed edge represents both precedence and possible communication from its originating vertex to its ending vertex. When the execution of a task is completed, the communication with its successor(s) can start and anticipated results are transferred. Only after all parents of a task are completed and their results (if any) are received by the task its execution can start. This constraint restricts a more general case in which some tasks could interact during their executions. In this paper, a task model composed of both interaction and precedence of tasks is introduced. It is shown that, under certain conditions, this kind of graph can be transformed into an extended DAG, called Hybrid DAG (HDAG), composed of tasks and super-tasks. With this, it becomes possible to model many applications in the form of hybrid workflows and go about scheduling them on the cloud. In this paper, validity conditions of such graphs are investigated and a verification algorithm is developed. The time used by this algorithm is evaluated. An algorithm for scheduling hybrid workflows is presented and its performance is evaluated.<br><br>The effect of different values for relative deadline on the schedulability of workflows is also presented.