\section{Workflow Model}\label{sec:workflowmodel}

The design and implementation of a \emph{scientific workflow} consists of two parts: an \emph{abstract part} and a \emph{concrete part}. We give an overview of these two parts in the following subsections.

\subsection{Workflow Design: The Abstract Part}

\begin{figure}[ht]
 \centering
 \includegraphics[width=.8\textwidth]{./background/figures/workflow-abstractpart.pdf}
 \caption{An abstract part of a scientific workflow.}
 \label{fig:dag}
\end{figure}

The \emph{abstract part} of a scientific workflow specification comprises a hardware and middleware agnostic (and therefore easily portable) description of the workflow structure, the activities involved, and the data and control flow dependencies between the activities. The individual activities are treated as black-boxes such that only the input and the output signatures are known.

We define the structure of a Scientific Workflow $W$ as a \emph{Directed Acyclic Graph (DAG)} (see Figure~\ref{fig:dag}):
$W=(A, D, P_{in}, P_{out})$, where $A$ represents workflow activities, $D$ represents the dependencies between activities, $P_{in}$ represents the workflow's \emph{Data In-Ports} which define the input signature of the workflow, and $P_{out}$ represents the workflow's \emph{Data Out-Ports} which define the output signature of the workflow

There are usually two different types of workflow activities $A$:

An \emph{Atomic Activitity} $A_i=(N, P_{in}, P_{out}, T_A)$ is a basic indivisible unit of computational work which consists of an unique name $N$, data in-ports $P_{in}$, data out-ports $P_{out}$ and an \emph{Atomic Activitity Type} $T_A$.

A \emph{Composite Activity} $A_j=(N, P_{in}, P_{out}, T_C, W_{Sub}, C)$ consists of an unique name $N$, \emph{Data In-Ports} $P_{in}$, \emph{Data Out-Ports} $P_{out}$ and a \emph{Composite Activitity Type} $T_C$, and contains one or more sub-workflows $W_{Sub}=(A_{Sub}, D_{Sub})$ with activities $A_{Sub}$ and dependencies $D_{Sub}$, onto which it imposes an activity type dependend control-flow. $C$ denotes activity type specific parameters, e.g. for a for-loop activity $C=(Start, Stop, Step)$ denotes the initial value, the stop condition value and the stride of the loop counter. Typical composite activity types are sequential and parallel loops, conditional activities, and sub-workflows. 


A \emph{data dependency} $D_{ij}$ between workflow activities $A_i$ and $A_j$ is defined as:
\[D_{ij}=\left(P^i_{out_m}, P^j_{in_n}, Data_{ij}\right),\] where $Data_{ij}$ denotes the data exchanged between data out-port $P^i_{out_m}$ of activity $A_i$ and data in-port $P^j_{in_n}$ of activity $A_j$.

A \emph{control-flow dependency} $D_{ij}$ between workflow activities $A_i$ and $A_j$ is defined as:
\[D_{ij}=\left(A_i, A_j\right),\] which imposes a constraint on $A_j$ so that it can only be executed after $A_j$ has finished execution.


\subsection{Workflow Implementation: The Concrete Part}

The concrete part of a workflow contains the hardware and middleware-dependent implementations of the atomic activities and their accompanying meta-information. This part is often highly specific to each individual workflow system and the underlying DCI. It usually contains information about the available activity implementations, locations where they are installed, how they can be executed, and any other further information indented to help the workflow engine in selecting the most appropriate activity implementation.

In our workflow model we define the implementation $W_{Impl}$ of a workflow as a mapping \[W_{Impl}: T_A \rightarrow (A_{Impl}, I_{Meta})\] from atomic activity types to one or more tuples consisting of an \emph{Atomic Activity Implementations} $A_{Impl}$, which is the actual executable code, and accompanying meta information $I_{Meta}$. The meta information contains information needed by the scheduler for selecting an appropriate actvitity implementation, and by the execution subsystem for executing the activity implementation.

\subsection{Workflow Management System}

The software used for setting-up, managing, executing and monitoring workflows is called \emph{Workflow Management System} (WfMS). A WfMS usually covers all aspects of a workflow, from creating to execution, and consists of several components. 

\begin{figure}[ht]
 \centering
 \includegraphics[width=\textwidth,keepaspectratio=true]{./background/figures/workflow-managementsystem.pdf}
 \caption{Architecture of a Scientific Workflow Management System.}
 \label{fig:background-wfms}
\end{figure}

Figure \ref{fig:background-wfms} shows the architecture of a typical scientific WfMS for Grid and Cloud computing. It consists of the following core components:

\begin{description}
 \item[Engine:] Responsible for executing the abstract part of a workflow, also called \emph{Workflow Enactment} (see Section \ref{sec:background-workflowenactment}).
 \item[Scheduler:] Responsible for mapping atomic activities to computing resources and selecting an approbriate activity implementation, also called \emph{Workflow Scheduling} (see Section \ref{sec:background-workflowscheduling}).
 \item[Execution Layer:] Keeps track of the available computing resources, manages the actual execution of activity implementations, and provides a unified interface for the scheduler and the individual execution sub-systems representing different hardware and middleware.
\end{description}

Furthermore, a WfMS may also contain following optional components:

\begin{description}
 \item[User Interface:] Interface which allows a user to interact with the workflow systems to, for example, create a workflow, start it, monitor its execution and retrieve the final results.
 \item[Prediction Service:] Predicts execution and data transfer times to aid the scheduler with scheduling the workflow. Some scheduling algorithms only work when a reliable prediction service is present. 
 \item[Monitoring/Logging Service:] Collects log messages and other information and presents them to the user, writes it into a log file or a data base for future use by e.g. the scheduler.
\end{description}


\subsection{Workflow Enactment}\label{sec:background-workflowenactment}

A workflow engine executes a workflow instance (operation usually called \emph{Workflow Enactment}) by traversing the DAG representing the workflow structure, determining the state of the individual activities, transferring data from finished activities to their successors in the dependency graph, unrolling composite activities and replacing them with the resulting subgraph, and delegating the actual execution of atomic activities to the scheduling and execution subsystems.
We call the resulting DAG where composite activities have been replaced with their contained subgraphs enriched with additional state information a \emph{Workflow Execution Plan} (WEP).

We distinguish between two types of workflow enactment modes:
\begin{itemize}
 \item In \emph{early enactment mode} the engine re-evaluates the WEP as soon as there are activity state changes, and tries to complete it as early as possible. This mode usually comes with a much higher overhead, but results in a more complete WEP comprising more information, which allows the scheduler to better plan the workflow execution on the underlying resources;
 \item In \emph{late enactment mode} (also called \emph{lazy evaluation mode}) the engine only re-evaluates and completes the WEP when it is absolutely necessary for the workflow enactment, and only partially completes it as far as it is required for continuing the enactment. This mode has less overhead, but also results in a less complete WEP with less information available for the scheduler to plan the workflow execution.
\end{itemize}


\subsection{Workflow Scheduling}\label{sec:background-workflowscheduling}

Scheduling describes the process of mapping atomic activities $A=\left(A_1, A_2, ..., A_m\right)$ to available computing resources $R=\left(R_1, R_2, ..., R_n\right)$  where they are executed. 
The resulting mapping \[S: A \rightarrow R,\] is called \emph{workflow schedule}. 
The scheduler usually tries to optimize the workflow schedule by maximising or minimizing a given utility function, typically the overall execution time. Some scheduler implementations take more than one objective into account, some of which may conflict with other objectives. This is called \emph{multi-objective optimization}.

To be able to produce an optimal mapping the scheduler need to know the resource requirements of an individual activity in advance. In this thesis we assume that the scheduler gets accurate knowledge of the resources required by an individual activity on a specific computing ressource from a third-party \emph{prediction service} we tread as black-box in the following. In practice obtaining this knowledge is still a steep challenge and subject to ongoing research.

Existing scheduling algorithms can be broadly divided into two categories~\cite{Wieczorek2009}:
\begin{itemize}
 \item \emph{Just-in-time scheduling algorithms} only consider the next activities to be scheduled when deciding on a mapping and ignore the rest of the WEP. They are usually linear in complexity with the number of activities (i.e. $O(N)$) and come with a low overhead, but due to limited information the generated schedule may not be that good;
 \item \emph{Full-ahead scheduling algorithms} use the entire WEP when deciding on a mapping and try to find an optimal schedule in the search space. They usually come with a much higher overhead, but consider more workflow information and therefore, produce in general better results. Generating a full-ahead schedule is an NP-hard problem~\cite{ullman1975np} and therefore, most existing full-ahead scheduling algorithms are approximate heuristic algorithms~\cite{heft02}.
\end{itemize}


\subsection{Parallelism in Workflows}

The most predominant form of parallelism found in scientific workflows is \emph{task parallelism} which means that different independent computational tasks operating on the same or different data are executed at the same time on different computing resources. On a conceptual level a scientific workflow is basically a collection of tasks with dependency relationships between them. The dependency relationships determine which tasks can be executed in parallel, and the scheduler distributes the tasks among the available computing resources so that a pre-set scheduling goal is satisfied. 

Other forms of parallelism like e.g. data parallelism can exist in workflows but are usually hidden away in atomic activity implementations which are considered black-boxes. A scientific workflow system can account for that fact by assuming that an atomic activity implementation may need more than one resource for execution.