Information Technology Reference
In-Depth Information
2 Robust Energy-Aware Scheduling under Uncertainty
This section describes the robust energy-aware scheduling problem in HC sys-
tems under conditions of uncertainty.
2.1 The Energy-Aware Scheduling Problem
In this article, we consider a multi-objective version of the scheduling problem in
multicore HC systems, taking into account the minimization of the makespan and
energy consumption. We call this problem the Makespan-Energy Heterogeneous
Computing Scheduling Problem (ME-HCSP). The mathematical formulation for
the problem considers the following elements:
-
A HC system composed of a set of multicore machines
P
=
;
each machine having
NC
(
m
i
) processing cores and processing speed
S
(
m
i
).
-
A collection of tasks
T
=
{
m
1
,...,m
M
}
{
t
1
,...,t
N
}
to be executed on the system, each
task arrives in time
ARR
(
t
i
).
-
An
execution time function ET
:
T
R
+
,where
ET
(
t
i
,m
j
)isthetime
required to execute task
t
i
on machine
m
j
.
-
An
execution time error function ʔ
ET
:
T
×
P
ₒ
R
+
,where
ʔ
ET
(
t
i
,m
j
)is
×
P
ₒ
the error introduced when estimating
ET
(
t
i
,m
j
).
-
An
energy consumption function EC
:
T
R
+
,where
EC
(
t
i
,m
j
)is
the energy required to execute task
t
i
on machine
m
j
,and
EC
IDLE
(
m
j
)is
the energy that machine
m
j
consumes in idle state.
-
An
energy consumption error function ʔ
EC
:
T
×
P
ₒ
×
P
ₒ
R
,where
ʔ
EC
(
t
i
,m
j
)
is the error introduced when estimating
EC
(
t
i
,m
j
).
The goal of the ME-HCSP is to find an assignment function
f
:
T
N
P
M
which simultaneously minimizes the
makespan
and the
total energy consumption
metrics. The assignment function
f
should schedule each task
t
i
to be executed
without preemption on some machine
m
j
at some time
ST
(
t
i
), with
ST
(
t
i
)
ₒ
≥
ARR
(
t
i
). The makespan metric is defined as the maximum completion time
C
max
=max
t
i
∈T
C
(
t
i
), where the completion time of task
t
i
is
C
(
t
i
)=
ST
(
t
i
)+
ET
(
t
i
,m
j
). The energy required to execute the task
t
i
in the machine
m
j
,given
by
EC
(
t
i
,m
j
), depends on the execution time of the task
t
i
in machine
m
j
,
ET
(
t
i
,m
j
), and the energy consumption of the machine
m
j
.The
total energy
consumption
is defined as shown in Equation 1.
EC
(
t
i
,m
j
)+
ʔ
EC
(
t
i
,m
j
)+
m
j
∈P
EC
IDLE
(
m
j
)
(1)
t
i
∈
T
:
f
(
t
i
)=
m
j
Regarding the energy consumption, in this work we apply the model for mul-
ticore computing systems introduced in our previous work [16]. In this model,
the energy consumption of a task is estimated by assuming the task is CPU-
bound and approximating its energy consumption by the energy consumption of
the CPU when executing that task. This was found to be an accurate approxi-
mation in an HPC systems where most tasks are CPU intensive and where the
