11institutetext: School of Computing, Newcastle University, UK 11email:
<EMAIL_ADDRESS>
# Analysis of Reinforcement Learning for determining task replication in
workflows

Andrew Stephen McGough  Matthew Forshaw

###### Abstract

Executing workflows on volunteer computing resources where individual tasks
may be forced to relinquish their resource for the resource’s primary use
leads to unpredictability and often significantly increases execution time.
Task replication is one approach that can ameliorate this challenge. This
comes at the expense of a potentially significant increase in system load and
energy consumption. We propose the use of Reinforcement Learning (RL) such
that a system may ‘learn’ the ‘best’ number of replicas to run to increase the
number of workflows which complete promptly whilst minimising the additional
workload on the system when replicas are not beneficial. We show, through
simulation, that we can save 34% of the energy consumption using RL compared
to a fixed number of replicas with only a 4% decrease in workflows achieving a
pre-defined overhead bound.

###### Keywords:

Performance Reinforcement Learning Scheduling

##  1 Introduction

Workflows comprising several independent (computational) tasks under a strict
ordering (see Figure 1 for an example) have become one of the pillars of
computational research and industrial development. Users wish to enact these
as quickly as possible – within a factor of the critical path execution time –
referred to as the contingency. However, many organisations lack dedicated
resources, nor the operational expense for Cloud enactment for this work. Here
these users are required to ‘make do’ with computational resources which are
not dedicated to this purpose – often referred to as volunteer computing. One
of the common ways of providing this is through High Throughput Computing
(HTC), which exploits the idle time available on computing resources
provisioned for other purposes – examples of such systems include HTCondor
[32] and BOINC [1].

Although HTC systems allow workload to be performed on volunteer resources –
thus sharing one of the main advantages of Cloud computing of having no (or
marginal) capital expense – it does have the distinct disadvantage that
resources can (and often are) retracted without warning for their primary use.
This will lead to the termination of those tasks which are currently being
executed on that resource. Approaches to ameliorate this include suspension of
tasks until the resource is available again [30], relaunching the task on a
new resource to run from the beginning [23] or checkpointing and migration
[29]. These approaches ensure eventual task completion, but impact the overall
execution time of the task [27] – which can be compounded when enacting a
workflow.

Users will, in general, expect their workflows to finish in a “reasonable”
time, relative to execution time for the workflow. Given that the tasks within
the workflow will often have to relinquish the resource back to the primary
user there can be considerable variance to the workflow execution time (see
Section 2). Leading to users believing that their workflow has crashed or the
system is unfit for purpose. However, this could just be a consequence of ‘bad
luck’ for the particular workflow enactment. Ideally a workflows execution
time should be relative to the length of the workflow’s critical path (defined
as the shortest time from the start to the end of the workflow [15]) where a
subset of the workflow tasks form the critical path. We formally state the
users desire here that a given workflow will complete within time
$(1+p)CR(W),$ where the delay proportion $p\geq 0$ and $CR(W)$ is the time to
execute the critical path for workflow $W$.

Although a task may not initially form part of the critical path if it is
forced to relinquish a resource the delay to its completion may make it part
of a newly revised critical path. As such, the workflow enactment needs either
to reduce the chance of the task from becoming so delayed or compensate for
such a delay.

Task replication – running multiple copies of the same task – can ameliorate
the impact of such delays. However, running these extra tasks can quickly
impact other work on the cluster leading to all workflows taking longer to
complete and higher overall energy consumption – as all but one are wasted
work. Determining how many replicas to have is a difficult problem and is
related to the resources primary usage pattern, how critical the task is to
timely completion and other workloads on the system. We propose using
Reinforcement Learning (RL) [31] to ‘learn’ the number of replicas to deploy
based on the time of day and how critical a tasks is to the workflow finishing
within its contingency requirements.

Section 2 discusses the problem space and analyse the impact of running
workflows in non-dedicated environments. Related work is evaluated in Section
3. Our approach is presented in Section 4. Section 5 presents our simulation
model before presenting results in Section 6. We present our conclusions in
Section 7.

##  2 Problem Space Analysis

We define, without loss of generality, a workflow as a Directed Acyclic Graph
(DAG) comprising independent tasks (represented as nodes) with an associated
ordering on their execution (represented by directed links between nodes).
Tasks have an associated execution time, including time for setup, data
ingress and egress, whilst links have associated time required for scheduling.
A DAG may have more than one start/end node. Without compromising our model,
we assume that such DAGs have an extra ‘task’ at the start (end), providing a
single start (end) node. These tasks have zero execution time; however, the
link execution time may be non-zero – to cater for workflow setup or
termination. Figure 1 illustrates a simple DAG. The normal tasks (A – H) have
links to indicate their dependencies (e.g. task F can only execute once both
tasks C and D have completed). Extra tasks are added to give a single start
(S) and termination (T).

Figure 1: A workflow. Nodes are tasks to run and links represent dependencies.

We analyse the impact on a workflow when running it on volunteer resources
such as a University HTC system. We extend HTC-Sim [9] for workflows [25]. As
the original trace-log does not contain workflows we replace 10% of the
original tasks in the trace-log with synthetic workflows (Figure 1 with each
task taking 32 mins). For each workflow which completed we compute the value
of $p(W)$, the proportion of excess time to execute the workflow, as:

$p(W)=\frac{(c(W)-s(W))}{CR(W)}-1$ (1)

where $c(W)$, $s(W)$ are the finish and submission times of tasks T, S from W
and $CR(W)$ is the execution time for the critical path of $W$.

(a) CDF for $p$

(b) Probability of task completing based on length and time of submission

Figure 2: CDF and probability of task completion

Simple statistical analysis (mean 0.4467, standard deviation 0.8217) of the
40,054 workflows suggests little impact from running in a volunteer
environment. However, the Cumulative Density function (Figure 2(a))
illustrates the long-tail on these results. Very few workflows complete with a
value of p(W) less than 0.00004. With a significant ($\sim 30\%$) of workflows
having $p(W)\sim 0.000043$. On the other hand, 10% of the workflows take
double or more than their critical path time to run ($p(W)\geq 1$). These
would seem to match those situations where the system was under exceptional
load causing workflow tasks to be repeatedly forced to relinquish resources.
Our worst case was when $p(W)=17.1113$.

The probability of each individual task in a workflow completing given its
length and time of submission is presented in Figure 2(b). Short tasks
submitted early in the morning have the highest probability of success with
reasonable chances across most of the day. The discontinuity at 3am and the
reduction to zero probability for longer jobs later in the day is a
consequence of the nightly reboot at 3am. For this system we predict that
replicas are likely to be beneficial through the day, but less so in the early
morning or before the 3am reboot. In this work we propose an adaptive system
which ‘learns’ system-specific behaviours.

##  3 Related Work

###  3.1 Energy-aware workflow scheduling

The challenges of scheduling workflows to computational resources has received
extensive treatment in the literature. A detailed exposition of previous
efforts is presented by Yu et al. [34]. Existing approaches predominantly
focus on workflow scheduling performance, with comparatively few considering
the energy consumption as a primary optimisation goal. Durillo  _et al._ [8]
adapt the well-established HEFT [33] heuristic for workflow scheduling, and
demonstrate the potential for significant energy conservation, for a small
performance penalty.

Several approaches explore enacting workflows in the Cloud. Zhu  _et al._ [35]
propose _pSciMapper_ for energy-aware consolidation of workflow tasks in
virtualised environments. Li  _et al._ [20] adopt a particle swarm
optimisation (PSO) approach to workflow scheduling in the Cloud, with
consideration for financial cost and security. Calheiros  _et al._ [6] focus
on task replication to overcome issues introduced by performance variation of
public Cloud resources.

Our approach is distinct from those presented. Firstly, we consider workflow
enactments to non-dedicated resources shared with their primary users.
Secondly, we adopt a RL based approach to learn characteristics of the
environment to which the workflows are deployed.

###  3.2 Simulations with support for workflows

The benefits of using simulation frameworks to evaluate the performance of
scheduling policies in large-scale computing systems is well understood [10,
11]. There exist a number of simulators for Grid and Cluster computing
infrastructures [2, 4, 19], these lack modelling capabilities to evaluate the
energy consumption of the simulated infrastructure. Simulation tools including
[5, 18, 21, 28] have the ability to evaluate energy-performance. However,
these tools do not allow modelling of tasks needing to relinquish resources
and workflows. With the exception of SimGrid, which is capable of modelling
DAG-based workflows, these tools lack the capability to model dependencies
between jobs. Chen and Deelman [7] extend CloudSim [5] to model Workflows, and
evaluate the performance of several common workflow scheduling heuristics.

Previously we extended HTC-Sim [12], a Java-based trace-driven HTC simulation,
to support workflow execution [25]. This enhancement will be used here,
allowing us to explore the energy and performance impact of workflow enactment
schemes within a multi-use cluster environment.

##  4 Reinforcement Replication

We present our replication approach within a volunteer HTC environment,
however, it is equally applicable to other environments exhibiting
intermittent faults.

###  4.1 Approach overview

We augment an event based model [13] for workload enactment to support task
replication, in which every time the status of the workflow changes (e.g.
workflow starts, task completes) an event is triggered and the appropriate
actions are performed. We assume here that a user has defined $\phi$111Where
the user desires $p(W)\leq\phi$ their contingency proportion for workflow
execution. Our adaptations to these workflow event handlers are:

  * •

Workflow starts: The desired deadline $d$ for the workflow is computed:

$d=(\phi+1)CR(W)+s(W).$ (2)

Next, for each task $t$ within the workflow which can be run – effectively
those tasks linked to task ‘S’ – we determine their local
$\phi^{\prime}(t)$222To simplify presentation we omit the parameters
hereafter. – reflecting how ‘critical’ $t$ is to the timely completion of the
workflow and is computed by removing those tasks from $W$ which do not depend
on $t$ (to give $W^{\prime}$) and computing the new critical path
($CR(W^{\prime})$). Then $\phi^{\prime}$ can be computed using equation 1 with
$\phi^{\prime}=p(W)$, $s(W)=s_{t}$ (the submission time of task $t$), $c(W)=d$
and $CR(W)=CR(W^{\prime})$. Here $\phi^{\prime}$ will be the proportional
difference between the critical path and the time to the deadline $d$. Note
that $\phi^{\prime}\geq\phi$ with equality when $t$ is part of the critical
path for the whole workflow. The number of replicas to be run can now be
determined through the use of RL which is parameterised by both the time of
the day at which task $t$ is submitted and the value of $\phi^{\prime}$.

  * •

Task completes: We define task completion to be the time at which the first
replica of a given task completes. First all other replicas are terminated as
they are no longer of any use. We can then determine any new tasks for the
workflow which are now free to be executed – those task for which all prior
task have completed. For each of these tasks $t$ we can compute
$\phi^{\prime}$ (as above) and hence the number of replicas which should be
deployed at this time of day, until the workflow has completed.

###  4.2 Metrics

In order to evaluate the effectiveness of our approach and to provide metrics
for use by our approach we define the following metrics:

  * •

Number of workflows with an overall $p(W)\leq P$: Our users seek to have their
workflows finish within the shortest time which is proportional to the length
of the critical path of the workflow. We seek to identify the number of
workflows which complete with a contingency less than $P$.

  * •

Energy consumption from replicas: Here we report both the ‘good’ energy (that
was used for the successful task) and the ‘bad’ energy for replica tasks. In
the case of ‘bad’ energy this is the combination of both replicas which fail
to be the first to complete and any replica runs which are terminated before
completion. More formally for task $i$ this is defined as:

$bad_{i}=\sum_{r\in X_{i}}\sum_{j\in I_{i,r}}\left\\{\begin{array}[]{l
l}\tau_{i,r,j}E_{i,r,j}&\quad\textrm{if }G_{i,r,j}\neq 1\\\
0&\quad\textrm{otherwise}\\\ \end{array}\right.,$ (3)

where $X_{i}$ is the set of all replicas of the task $i$, $I_{i,r}$ is the set
of all invocations of replica $r$, $\tau_{i,r,j}$ is the execution time of
replica $r$ invocation $j$, $E_{i,r,j}$ is the energy consumption rate (Watts)
of the resource selected for replica $r$ invocation $j$ and $G_{i,r,j}$ is one
for the good replica invocation, else zero. Likewise:

$good_{i}=\tau_{i,r,j}E_{i,r,j},\ \ \ r\in X_{i},j\in I_{i,r},\text{ such that
}G_{i,r,j}=1.$

Note that only one $G_{i,r,j}=1$. Note that the total energy consumed for
running the replicated task will be $good+bad$.

###  4.3 Computation of $\phi^{\prime}$

In order to compute $\phi^{\prime}$ we must first determine the time remaining
before we reach the workflow deadline and the estimated time that the rest of
the workflow will take to complete. The first value can be computed as
$d-s_{t}$. The second value, the time to complete task $t$ and all those tasks
which are dependant on $t$, is computed as:

$L_{t}=\begin{cases}r_{t}+\max_{j\in C_{t}}L_{j}&\quad\text{if $|C_{t}|\neq
0$}\\\ r_{t}&\quad\text{otherwise}\\\ \end{cases},$ (4)

where $C_{t}$ is the set of tasks imediately dependant on task $t$, and
$r_{t}$ is the duration of task $t$. We consider $L_{t}$ to be the local
critical path from task $t$ to the end of the workflow. Note that for
simplicity here we assume $r_{t}$ includes any time for data ingress / egress
and setup time. Note also that if $t$ is the start task of the workflow then
$L_{S}$ is the duration of the critical path for the whole workflow.

Given that before workflow execution starts we do not know the values of
$r_{t}$ we can replace these with estimates ($e_{t}$) of the execution time.
At this stage we do not concern ourselves as to how these estimates are
derived except to note that this could be provided through a performance
repository used to predict task execution times [14] or the use of performance
prediction [26]. Equation 4 becomes:

$L^{\prime}_{t}=\begin{cases}e_{t}+\max_{j\in
C_{t}}L^{\prime}_{j}&\quad\text{if $|C_{t}|\neq 0$}\\\
e_{t}&\quad\text{otherwise}\\\ \end{cases}.$ (5)

The workflow will rarely follow this expected execution duration. Tasks may
take more or less time than their estimate – either due to miss-estimates of
their execution time or due to the fact that multiple submissions are required
before certain tasks complete. This can lead to tasks, which weren’t on the
critical path, becoming part of the new critical path. Before submitting each
task within the workflow we need to determine its potential impact on the
overall workflow and how we can minimise this impact – say by running multiple
copies of the task to increase its chance of completing within its own
expectation time ($(1+\phi)e_{t}$).

We have evaluated two approaches can be taken for determining the potential
impact of a task on the overall workflow – both based around $\phi$:

####  4.3.1 All remaining tasks balanced:

In this case we compute the spare time available for all task (including this
task) which depend on this task and divide this proportionally between all
these tasks. Thus we compute $\phi^{\prime}$ as the proportion we can allocate
to all remaining tasks that are dependant on task $t$:

$\phi^{\prime}=\frac{d-s_{t}}{L^{\prime}_{t}}-1.$

With three cases for the value of $\phi^{\prime}$:

  * •

$\phi\leq\phi^{\prime}$: Here, for this path of the workflow we are currently
not part of the critical path, or we are on the critical path but ahead of
schedule. There is currently no additional risk to completing the workflow by
$d$. Running replicas of task $t$ can be performed if deemed necessary by the
time of day.

  * •

$0\leq\phi^{\prime}<\phi$: We have fallen behind schedule for this path of the
workflow, though there is still a probability that the workflow can be
finished successfully. Remedial actions can be taken (such as running multiple
copies of the current task) to increase the chance of completing the workflow
by $d$.

  * •

$\phi^{\prime}<0$: The workflow is significantly behind schedule and this path
is likely to prevent the workflow from completing before $d$, remedial work is
required. Note that if the remaining tasks in this path complete faster than
their expected execution time it may still be possible to finish by $d$.

####  4.3.2 Balance on current task:

Instead of balancing all remaining slack time across the remaining tasks in
this path we assume all remaining tasks will still have their proportion
$\phi$ while the current task will do anything possible to get itself back on
track. We define $\phi^{\prime\prime}$ as the proportion of extra time
available to task $t$:

$\phi^{\prime\prime}=\frac{d-s_{t}-\max_{j\in C_{t}}L^{\prime}_{j}}{e_{t}}-1.$

The three cases for $\phi^{\prime}$ above also apply to $\phi^{\prime\prime}$,
though for $\phi^{\prime\prime}<0$ there is still slack time for the remaining
tasks so the workflow may still finish on time.

###  4.4 Reinforcement Learning

We wish to determine for a given task $t$, submitted at time $s_{t}$, and with
contingency proportion $\phi^{\prime}$333without loss of generality we use
$\phi^{\prime}$ to represent both $\phi^{\prime}$, and $\phi^{\prime\prime}$.
the number of replicas which should be submitted. We include here one as a
valid number of replicas. In order to tailor our approach to an individual HTC
system we use Reinforcement Learning (RL) [31], to train an agent to provide
the number of replicas which is expected to give the greatest reward (chance
that the task will complete in the minimal time). RL is a form of Machine
Learning which can learn the ‘best’ action to perform given a particular
system state. This can be achieved without training data – with training
coming from the interaction between an agent and a reward function which
provides feedback on the actions taken by the agent. Thus RL can, not only,
adapt itself to any given environment but also, as it continually trains,
adapt as the environment changes. RL has been previously used to solve control
problems such as elevator scheduling, resource allocation within a data centre
[3], reduction of energy consumption within volunteer computer systems [24]
and bidding stratergies for energy markets [17].

In order to use RL to optimise the number of replicas we use the approach of
an n-armed bandit [31]. Under this assumption each action – the number of
replicas to run – is independent of all other actions performed.

Each task $t\in\\{1,2,...\\}$ which we wish to replicate will observe the
system in a given state $s\in S$. Our state space here represents those
characteristics of the system over which decisions should be made – in this
case the time of day at which the task is to be submitted and the contingency
proportion available for the task. As these need to be discrete values we
round the time of submission to the hour of the day when submission took
place, thus giving 24 states for time. Likewise for contingency proportion we
discretise this to $n+2$ intervals. Namely:

$\\{\phi^{\prime}\leq
0,0<\phi^{\prime}\leq\frac{P}{n},...,\frac{P(n-1)}{n}<\phi^{\prime}\leq
P,P<\phi^{\prime}\\}.$

Thus our state space comprises of $24(n+2)$ states. In order to maintain our
n-armed bandit model we assume that a task which has to relinquish a resource
becomes a new task within the system when it is re-allocated. The set of
actions ($a\in A$) is the number of replicas which to be submitted to the
system. We determine the action $a$ to perform as:

$a=f(Q(s,A)),$ (6)

where $Q(s,A)$ is the set of all reward values for the actions $A$ available
when the system is in state $s$ and $f()$ is a selection policy. The true
reward values $Q(s,A)$ are unknown, but we can estimate $Q^{\prime}(s,A)$ from
the prior decisions which have been made and the associated rewards. This
becomes an estimator for $Q(s,A)$:

$Q^{\prime}_{t}(s,A)=\\{q^{\prime}_{t}(s,a)\\}\quad\forall a\in A,$ (7)
$q^{\prime}_{t}(s,a)=\overline{R_{i}(s,a^{\prime})}\quad\forall i\leq
t,a^{\prime}=a,$ (8)

where $R_{t}(s,a)\in[-k,k]$ is the reward for taking action $a$ in state $s$
for task $t$. A value, for $R_{t}(s,a)$, of $-k$ indicates this was the worst
possible choice of action whilst $+k$ indicates the best choice of action. The
value of $k$ can be chosen arbitrarily, however, it is normally a small number
to prevent buffer overflows. There are two possible outcomes when an action is
applied to a task. These are:

  * •

Task $t$ completed within the contingency proportion $\phi^{\prime}$: This is
seen as a success for action $a$ which should be rewarded thus increasing the
chance of this action being selected again in the future. However, if left
unchecked using just a reward for success here could lead to a system learning
that the highest reward is obtained by allocating the maximum number of
replicas to each task. We therefore need to diminish this reward proportional
to the wasted work completed for those replica tasks which have been run.

  * •

Task $t$ failed to complete within the contingency proportion $\phi^{\prime}$:
This is seen as a failure for the action $a$ chosen and requires a punishment
to reduce the chances of this action being selected again in the future.

Therefore we can define the reward function as follows for task $t$:

$R_{t}(s,a)=\left\\{\begin{array}[]{l l}+1-\sigma_{t}&\quad${$t$ completed
within $\phi^{\prime}e_{t}$}$\\\ -5&\quad${$t$ failed to complete within
$\phi^{\prime}e_{t}$}$\\\ \end{array}\right.,$

where the first term in the reward function is used to indicate that the
chosen action was good or not and the second term (if present) helps to steer
the replication task towards the minimum value. We set the value for failed
tasks to -5 to incur a large penalty for failure, the RL approach was not
significantly afected by changing this value. We set the value of
$\sigma_{t}\in[0,1]$ to be proportional to the wasted work performed by
replicas. We compute $\sigma_{t}$ using the energy consumption of the ‘bad’
replicas as a proxy for the wasted work:

$\sigma_{t}=\min(1,\frac{bad_{t}}{ad_{t}\Xi}),$

where $\Xi$ is the average energy consumption rate for the selected resource
when performing work – we assume 100% utilisation.

We can now define the selection policy $f()$ which is used to evaluate the
action to perform given the prior history reward set $Q^{\prime}(s,A)$. We
define two approaches, a greedy (exploitative) and an explorative selection
policy:

$f(Q^{\prime}(s,A))=\left\\{\begin{array}[]{l
l}max_{a}(Q^{\prime}(s,A))&\quad${with probability 1 -
$\epsilon$}$\quad${(exploitative)}$\\\ random(A)&\quad${with probability
$\epsilon$}$\;\;\quad\quad${(explorative)}$\\\ \end{array}\right.$ (9)

Here $max_{a}()$ selects the action $a$ with the highest expected reward,
whilst $random(A)$ will select an action uniformly at random from $A$.

By selecting the greedy policy we are exploiting prior knowledge to use the
action with the greatest expected reward, whilst an exploitive policy allows
us to search for potentially better actions. The dynamic and changing nature
of our system necessitate both exploitative and explorative policies. Being
too greedy can lead to poor choice of replica counts as the agent will keep
using sub-optimal actions, whilst being too explorative can lead to the use of
sub-optimal actions which are known to be bad. A careful selection of
$\epsilon$ is therefore required.

####  4.4.1 Vary $\epsilon$:

In most cases, like ours here, the RL system will start off in an uninitiated
state where each action has the same reward value. If the value of $\epsilon$
is too small then the system can keep choosing the wrong action, when in
exploitation mode, due to insufficient training. Likewise, if the underlying
system changes the ‘learned’ actions may no longer be valid – in which case we
should return to an explorative policy. We can therefore choose to vary
$\epsilon$ during execution to allow better training. Two common approaches
are:

  * •

Initially high $\epsilon$: Initially the value of $\epsilon$ is set high
($\epsilon_{1}$), then to a lower value $\epsilon_{2}$ after the first $l$
rewards have been observed. This allows the RL to be initially more
explorative and once the system has had a chance to ‘learn’ the best actions
it will revert to a more exploitative policy.

  * •

Vary $\epsilon$ when results of choosing an action vary from those expected:
Here a sliding window captures the results from the last $m$ selections of a
given action. If the average reward of this value deviates too far then the
value of $\epsilon$ can be increased for a time until it is deemed that the
system has been re-trained. This allows the RL to become more explorative when
the rewards move away from the expected range, to adapt to underlying changes.

###  4.5 Mechanisms of workflow task enactment

In this work we compare three mechanisms for workflow task enactment:

  * •

Single task execution: Each task within a workflow is submitted only once to
the HTC system. This provides a baseline for workflow execution times.

  * •

Fixed replica execution: The number of replicas is fixed. Although this can
lead to reduced execution time of the workflow it has two main disadvantages.
Firstly, tasks will be needlessly replicated at times of the day when this is
not required. Secondly, the extra replicas could lead to contention for
limited resources, hindering tasks which otherwise would have completed.

  * •

RL-based replica execution: The number of replicas is determined dynamically
at runtime. The likelihood of workflows finishing within the defined
contingency is increased, whilst minimising overheads and contention.

##  5 Experimental Setup

We extend the HTC-Sim simulation [9, 25] to model task replicas and
incorporate RL functionality. We use our trace logs [9] from the use of the
HTCondor [22] system and interactive users at Newcastle University during
2010. These logs represent 1,229,820 interactive user logins – the primary
users of the cluster of 1,400 computers. During the year a total of 561,851
HTC tasks were submitted. As our original trace-log lacks examples of
workflows, we randomly replace w% of the tasks within the trace-log with
synthetic workflows. Here we choose w = 10% and use the same modified trace-
log for all experiments to ensure consistency. We experiment with two workflow
types: the simple workflow from Figure 1 (each task taking 32 minutes), more
real-world workflows generated by Montage.

We have limited the maximum number of replicas, of each workflow task, to ten
as experiments have shown that values greater than this give no advantage and
often cause the cluster to become overloaded. Values of $\phi$ range between
0.1 and 1.0 in steps of 0.1 – we also evaluate the value of $\phi=2$. For our
state-space we have chosen $n=10$ thus matching in with the intervals used for
$\phi$. We varied $\epsilon_{1}\in[0.05,1]$ and $\epsilon_{2}\in[0.05,0.4]$
and the sliding window $m\in[10,10,000]$.

##  6 Results

We present here only the results for the “All remaining tasks balanced” case
for brevity as we observed no statistical difference between the two different
approaches. We used $\epsilon_{1}=0.5,\epsilon_{2}=0.05$. Table 1 presents the
base case, no task replication, indicating the number of workflows which
completed within $P$ contingency (Successful) and the energy consumed in these
cases (Energy in MWh). The number of workflows which complete successfully
increases with $P$ as expected. Although the values for energy are varying
this is more due to the randomness within the simulation (the time the
workflows are executed and which resources are used to run them).

$\phi$ | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | 2.0
---|---|---|---|---|---|---|---|---|---|---|---
Successful | 14,982 | 19,622 | 22,979 | 24,791 | 25,475 | 26,494 | 29,967 | 33,081 | 35,015 | 36,318 | 39,650
Energy | 28.83 | 30.86 | 30.87 | 29.86 | 29.08 | 29.78 | 30.98 | 30.25 | 28.92 | 28.49 | 30.72
Table 1: Baseline case

Figure 3a shows the increase in workflows which finish within a contingency
proportional to $P$ by using a fixed number of replicas, compared to our
baseline case (Table 1). We see favourable results in the two- and three-
replica case. This is particularly evident for contingency value $P$=0.1,
where over 20% more workflows are capable of meeting the target. Four or more
replicas lead to contention for resources and corresponding performance
degradation. However, if the number of replicas can vary, then it may be
beneficial to deploy more than four replicas at specific times of the day or
for particular contingency levels.

Figure 3: For fixed replicas: a) Percentage of workflows achieving users
desired contingency. b) Energy requirements for achieving users desired
contingency. c) Percentage increase in energy consumption by using RL.

Figures 3b and 3c indicate the extra energy required when we run a fixed
number and RL chosen replica count for each task within a workflow. As can be
seen from this figure the energy consumption increases linearly with the
increase in replicas (for the RL case this is the maximum number of replicas
it can select). As such this will quickly lead to excessive extra computation
and wasted work. However, the RL case effectively halves the energy
consumption.

Figure 4 shows how much we can reduce the energy consumption of running
replicas by allowing RL to select the number of replicas to enact. For fair
comparison, RL is bounded by the same maximum number of replicas as the fixed
case. The percentage decrease in energy is presented in Figure 3c. We see our
approach achieves promising energy savings for all replication scenarios
(replica count $\geq$ 2), successfully identifying system conditions requiring
the use of replication, while minimising unnecessary replication during
periods of low utilisation which would lead to wasted energy. Although we can
significantly reduce the energy consumption of enacting replicas, we must also
consider the performance impact of this additional replication. Figure 5
illustrates the proportion of workflows able to complete within time
contingency $P$. We observe favourable improvement in workflow completion,
particularly when considering small contingency values. Most importantly, we
see improvements across a much wider range of replica counts. This shows our
approach to be far less susceptible to sub-optimal replica count selection.

Figure 4: Comparison between energy increase for fixed replicas and RL
replicas Figure 5: Increase in number of workflows which can be performed when
using RL Figure 6: Using RL for Montage. a) Percentage increase in workflows
achieving users’ desired contingency. b) Percentage change in energy
consumption.

We now validate our approach for the well-established Montage workflow [16].
Figure 6a shows our approach can improve the number of successful workflows.
This seems to be irrespective of the choice of replica count, however, this is
most likely a consequence of the newly successful workflows only using a small
number of replicas. The biggest impact comes from the choice of contingency –
with lower contingency giving better results. Likely a consequence of RL not
over-provisioning for cases where it can’t complete on time, thus keeping the
system idle for other workflows. Figure 6b confirms that the energy impact is
reduced significantly compared to a fixed replication scheme. We are able to
conserve 34% energy consumption with only a 4% decrease in workflows achieving
contingency.

##  7 Conclusions

In this paper we have explored, through trace-driven simulation, how the
performance and energy consumption of workflow enactments in an HTC
environment can be improved through task replication. We demonstrate that
fixed replication schemes, if tuned correctly, can deliver significant
performance improvements, but impose a considerable overhead in energy
consumption. In contrast, our proposed Reinforcement Learning approach
curtails the energy consumption while retaining the performance benefits. We
show our approach to be less susceptible to poor performance due to sub-
optimal replica count selection.

Future work will explore the broader applicability of RL approaches in
workflow enactment; e.g. an RL-based overlay to the HEFT scheduling heuristic.

## References

  * [1] Anderson, D.P.: Boinc: A system for public-resource computing and storage. In: Grid Computing, 2004. pp. 4–10. IEEE (2004)
  * [2] Bell, W.H., Cameron, D.G., Capozza, L., Millar, A.P., Stockinger, K., Zini, F.: Optorsim - a grid simulator for studying dynamic data replication strategies. International Journal of High Performance Computing Applications (2003)
  * [3] Bodík, P., Griffith, R., Sutton, C., Fox, A., Jordan, M., Patterson, D.: Statistical machine learning makes automatic control practical for internet datacenters. In: USENIX HotCloud (2009)
  * [4] Buyya, R., Murshed, M.: Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurrency and Computation: Practice and Experience 14(13), 1175–1220 (2002)
  * [5] Buyya, R., Ranjan, R., Calheiros, R.N.: Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities. In: HPCS’09. pp. 1–11. IEEE (2009)
  * [6] Calheiros, R.N., Buyya, R.: Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE TPDS 25(7), 1787–1796 (2014)
  * [7] Chen, W., Deelman, E.: Workflowsim: A toolkit for simulating scientific workflows in distributed environments. In: IEEE e-Science’12. pp. 1–8. IEEE (2012)
  * [8] Durillo, J.J., Nae, V., Prodan, R.: Multi-objective workflow scheduling: An analysis of the energy efficiency and makespan tradeoff. In: Cluster, Cloud and Grid Computing (CCGrid), 2013 13th IEEE/ACM International Symposium on. pp. 203–210. IEEE (2013)
  * [9] Forshaw, M., McGough, A., Thomas, N.: HTC-Sim: a trace-driven simulation framework for energy consumption in high-throughput computing systems. Concurrency and Computation: Practice and Experience 28(12), 3260–3290 (2016)
  * [10] Forshaw, M.: Operating Policies for Energy Efficient Large Scale Computing. Ph.D. thesis, Newcastle University, UK (2015)
  * [11] Forshaw, M., Thomas, N., McGough, A.S.: The case for energy-aware simulation and modelling of internet of things (iot). In: Proceedings of the 2nd International Workshop on Energy-Aware Simulation. pp. 5:1–5:4. ENERGY-SIM, ACM (2016)
  * [12] Forshaw, M., Thomas, N., McGough, S.: Trace-driven simulation for energy consumption in high throughput computing systems. In: IEEE/ACM DS-RT (2014)
  * [13] Georgakopoulos, D., Hornick, M., Sheth, A.: An overview of workflow management: From process modeling to workflow automation infrastructure. Distributed and Parallel Databases 3(2), 119–153 (1995)
  * [14] Hiden, H., Woodman, S., Watson, P.: A framework for dynamically generating predictive models of workflow execution. In: Proceedings of the 8th Workshop on Workflows in Support of Large-Scale Science. WORKS ’13 (2013)
  * [15] J. E. Kelley, J., Walker, M.R.: Critical-path planning and scheduling. Managing Requirements Knowledge, International Workshop on 0, 160 (1959)
  * [16] Jacob, J.C., Katz, D.S., Berriman, G.B., Good, J.C., Laity, A., Deelman, E., Kesselman, C., Singh, G., Su, M.H., Prince, T., et al.: Montage: a grid portal and software toolkit for science-grade astronomical image mosaicking. International Journal of Computational Science and Engineering 4(2), 73–87 (2009)
  * [17] Kell, A.J.M., Forshaw, M., Stephen McGough, A.: Exploring market power using deep reinforcement learning for intelligent bidding strategies. In: 2020 IEEE International Conference on Big Data (Big Data). pp. 4402–4411 (2020). https://doi.org/10.1109/BigData50022.2020.9378137
  * [18] Kliazovich, D., Bouvry, P., Audzevich, Y., Khan, S.U.: Greencloud: A packet-level simulator of energy-aware cloud computing data centers. In: GLOBECOM (2010). https://doi.org/10.1109/GLOCOM.2010.5683561
  * [19] Legrand, A., Marchal, L.: Scheduling distributed applications: The simgrid simulation framework. In: In Proceedings of the Third IEEE International Symposium on Cluster Computing and the Grid. pp. 138–145 (2003)
  * [20] Li, Z., Ge, J., Yang, H., Huang, L., Hu, H., Hu, H., Luo, B.: A security and cost aware scheduling algorithm for heterogeneous tasks of scientific workflow in clouds. Future Generation Computer Systems (2016)
  * [21] Lim, S.H., Sharma, B., Nam, G., Kim, E.K., Das, C.: Mdcsim: A multi-tier data center simulation, platform. In: Cluster Computing and Workshops, 2009. CLUSTER ’09. IEEE International Conference on. pp. 1–9 (2009)
  * [22] Litzkow, M., Livney, M., Mutka, M.W.: Condor-a hunter of idle workstations. In: ICDCS (1988)
  * [23] McGough, A.S., Forshaw, M., Gerrard, C., Wheater, S.: Reducing the number of miscreant tasks executions in a multi-use cluster. In: Cloud and Green Computing (CGC), 2012 Second International Conference on. pp. 296–303 (Nov 2012)
  * [24] McGough, A.S., Forshaw, M.: Reduction of wasted energy in a volunteer computing system through reinforcement learning. Sustainable Computing: Informatics and Systems 4(4), 262 – 275 (2014)
  * [25] McGough, A.S., Forshaw, M.: Energy-aware simulation of workflow execution in high throughput computing systems. In: IEEE/ACM DS-RT (2015)
  * [26] McGough, A.S., Afzal, A., Darlington, J., Furmento, N., Mayer, A., Young, L.: Making the grid predictable through reservations and performance modelling. Comput. J. 48(3), 358–368 (May 2005)
  * [27] McGough, A.S., Forshaw, M., Gerrard, C., Robinson, P., Wheater, S.: Analysis of power-saving techniques over a large multi-use cluster with variable workload. CCPE 25(18), 2501–2522 (2013). https://doi.org/10.1002/cpe.3082
  * [28] Méndez, V., García, F.: Sicogrid: A complete grid simulator for scheduling and algorithmical research, with emergent artificial intelligence data algorithms.
  * [29] Niu, S., Zhai, J., Ma, X., Liu, M., Zhai, Y., Chen, W., Zheng, W.: Employing checkpoint to improve job scheduling in large-scale systems. In: Job Scheduling Strategies for Parallel Processing. pp. 36–55. Springer (2013)
  * [30] Roy, A., Livny, M.: Condor and preemptive resume scheduling. In: Grid resource management, pp. 135–144. Springer (2004)
  * [31] Sutton, R., Barto, A.: Reinforcement Learning: An Introduction. A Bradford book, Bradford Book (1998)
  * [32] Tannenbaum, T., Wright, D., Miller, K., Livny, M.: Condor: a distributed job scheduler. In: Beowulf cluster computing with Linux. pp. 307–350. MIT press (2001)
  * [33] Topcuoglu, H., Hariri, S., Wu, M.y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on 13(3), 260–274 (2002)
  * [34] Yu, J., Buyya, R., Ramamohanarao, K.: Workflow scheduling algorithms for grid computing. In: Metaheuristics for scheduling in distributed computing environments, pp. 173–214. Springer (2008)
  * [35] Zhu, Q., Zhu, J., Agrawal, G.: Power-aware consolidation of scientific workflows in virtualized environments. In: Proceedings of the ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (2010)