Monte Carlo Simulation-Based Robust Workflow Scheduling for Spot Instances in Cloud Environments

In the resource allocation step, each task from the list is sequentially allocated to a resource by comparing all the candidate resources. Although the computation resources offered by the cloud provider are claimed to be infinite, it is unnecessary to try each of them for resource selection as the unused resources of the same type can be regarded as the same. Hence, the resource candidates that need to be considered include all the resources that have been used in the current solution and those that have not been used but can be added at any time (one resource for each type).

For traditional workflow scheduling models aiming to optimize the makespan, the resource allocation criterion is usually set to select a resource from all the resource candidates, which allows the earliest finish time (e.g., HEFT^{[ 13 ]} and PEFT^{[ 48 ]}). The considered model aims to achieve deadline-constrained cost optimization, and the resource allocation step should be aware of the deadline constraint and cost. To this end, the user-specified deadline $D$ for the workflow is first distributed to each workflow task, and the criterion for selecting a resource for task $t_i$ is updated as follows: meet $t_i$ ’s sub-deadline and minimize the cost increment of adding $t_i$ . Specifically, the sub-deadline of each task is calculated based on ${\rho }_i$ via

(11) $${\delta }_i=D\times \frac{{\rho }_{\text{entry}}-{\rho }_i+w_i/s^{*}}{{\rho }_{\text{entry}}}$$

When no candidate resource meets the sub-deadline, the selection criterion turns to minimizing the finish time of the task instead. By doing so, the probability for the whole workflow to meet the overall deadline is increased.

For brevity, the stochastic list scheduling heuristic employing a ${\rho }_i$ -based task ordering before resource allocation is denoted as SLS-I, and the one employing a topological sort based ordering is denoted as SLS-II. A topological sort based ordering has greater uncertainty than a ${\rho }_i$ -based one, as the latter’s uncertainty only comes from whether to calculate transfer time.

Given the predicted interruption time $\mathrm{\Omega }$ in runtime for the used SIs in a schedule solution $S$ , the actual makespan $M(S)$ and cost $C(S)$ for the solution can be acquired. The detail is given in Algorithm 2, where the actual start time and finish time of each task are calculated individually based on the task list (Lines 1–6). For each task, the actual start time $AS{T}_i$ is first calculated via Eq. ( 4 ) based on the actual finish time of its parent tasks and the actual ready time of the resource $r_l$ where it is allocated (Lines 2 $\&$ 3).

When $AS{T}_i+w_i/s_l$ is less than the predicted interruption time $X_l$ of SI $r_l$ obtained from $\mathrm{\Omega }$ , $r_l$ can finish executing $t_i$ without interruption. Otherwise, the execution is interrupted, and $t_i$ is moved to an OI for re-execution. If there is an OI that has been launched and is currently free and it is not slower than $r_l$ , $t_i$ is moved to this OI; otherwise, a new OI is launched for re-executing $t_i$ . Then, $t_i$ ’s execution time and its actual finish time $AF{T}_i$ are calculated via Eqs. ( 2 ) and ( 5 ), respectively. After traversing all the tasks in a workflow, its actual makespan and cost are calculated and returned.

The main procedure of MCLS follows the Monte Carlo simulation framework, a popular approach for various problems which involve stochastic factors and are generally infeasible to resolve via deterministic computations. MCLS consists of two main phases, that is, “producing” and “selecting”. In the producing phase, an independent sample is randomly taken from the domain space for each random variable $X_l$ , a list scheduling method is leveraged to generate a schedule solution based on random samples, and the above steps are repeated until adequate candidate solutions are generated. Then, in the selecting phase, candidate solutions are evaluated, and the best one is returned. The whole algorithm of MCLS is described in Algorithm 3.

First, an empty solution pool $P$ is created, and SLS-I is performed to obtain a schedule solution $S$ , which is added to $P$ (Lines 1 $\&$ 2). In the producing phase with $N_p$ iterations, a sample of $X_l$ is taken for all used SIs in $S$ based on their distribution functions, which is denoted as $\mathrm{\Omega }$ , and then $S$ is evaluated based on $\mathrm{\Omega }$ via Algorithm 2 to compute its makespan and cost values (Lines 3 $\&$ 4).

Next, SLS-II is performed to produce a new solution $S^{\prime }$ . The makespan and cost of $S^{\prime }$ are calculated based on $\mathrm{\Omega }$ . A new solution $S^{\prime }$ is regarded as better than $S$ if they both meet the deadline constraint and $S^{\prime }$ incurs less cost or if one of them does not meet the deadline and the makespan of $S^{\prime }$ is less than $S$ . $S^{\prime }$ is added into $P$ if it is better than $S$ . Based on the samples $\mathrm{\Omega }$ , $N_d$ new solutions are built and evaluated, and this procedure is repeated for $N_p$ times.

In the selecting phase, when $|P|>P_{\min }$ , $N_s$ samples are taken from their distribution functions to evaluate the candidate solutions in $P$ (Lines 14–17). Then, for each solution, its satisfaction rate and average cost are calculated, and then the utility value is obtained (Line 18). Then, solutions in $P$ whose ranks in terms of utility value are lower than $|P|/2$ are removed. By doing so, half of the solutions in $P$ survive the evaluation in the next round. When $|P|⩽P_{\min }$ , the solution with the highest average utility value is returned as the final solution. The selection phase guarantees that the performance of the returned solution is robust toward various execution situations in runtime as it is the best one validated by a large number of samplings and evaluations.

MCLS builds $N_p\times N_d$ schedule solutions in total. To build each solution via list scheduling, the computational complexity is $O(n\times (n+t))$ , where $n$ is the number of tasks in a workflow and $t$ is the number of resource types. As $t$ is usually much less than $n$ , it can be simplified as $O\left(n^2\right)$ . The computational complexity of the producing phase is $O(N_p\times N_d\times n^2)$ . The computational complexity of the selecting phase is $O({\log }_2|P|\times |P|\times N_s\times n)$ because $P$ can be cut for ${\log }_2|P|$ times at most, and an $O(n)$ time complexity is required for a solution evaluation. Combining the above analysis, the computational complexity of MCLS can be deduced, i.e., $O\left(N_p\times N_d\times n^2+{\log }_2|P|\times |P|\times N_s\times n\right)$ .