# Energy-Efficient Reliability-Aware Scheduling Algorithm on Heterogeneous Systems

Authors: Xiaoyong Tang; Weizhen Tan
Journal: Scientific Programming
 (2016)

---

## Abstract

The amount of energy needed to operate high-performance computing systems increases regularly since some years at a high pace, and the energy consumption has attracted a great deal of attention. Moreover, high energy consumption inevitably contains failures and reduces system reliability. However, there has been considerably less work of simultaneous management of system performance, reliability, and energy consumption on heterogeneous systems. In this paper, we first build the precedence-constrained parallel applications and energy consumption model. Then, we deduce the relation between reliability and processor frequencies and get their parameters approximation value by least squares curve fitting method. Thirdly, we establish a task execution reliability model and formulate this reliability and energy aware scheduling problem as a linear programming. Lastly, we propose a heuristic Reliability-Energy Aware Scheduling (REAS) algorithm to solve this problem, which can get good tradeoff among system performance, reliability, and energy consumption with lower complexity. Our extensive simulation performance evaluation study clearly demonstrates the tradeoff performance of our proposed heuristic algorithm.


---

## Body

## 1. Introduction

For a long time, energy consumption has simply been ignored in the performance evaluation in large-scale parallel computing systems. However, Intelligence (DCDi) Industry Census reported that the amount of electricity consumed by global data centers ran up to 40 GW in 2013, and it was also with a7
% increase [1]. According to the latest world’s Top 500 supercomputers Ranking, the power consumption of first supercomputer “Tianhe-2” is 17.808 MW and average power consumption for Top 10 systems in Ranking list is 6.2939 MW, respectively [2]. Thus, it is obvious that high energy cost is a key feature of designing and applying heterogeneous systems.On the other hand, computing systems are a group of heterogeneous processors connectedvia a high-speed network that supports the execution of parallel applications. For example, the Top supercomputer “Tianhe-2” in Top 500 lists consists of Intel Xeon® E5-2692 12C 2.200 GHz and Intel Xeon Phi 31S1P (MIC) [2]. For each processor, the number of transistors integrated into today’s Intel Xeon EX processor reaches to nearly 2.3 billion and its power consumption over 130 W [3]. This implies the possibility of worsening single processor reliability, eventually resulting in poorness of the whole heterogeneous system reliability. Furthermore, the modern large-scale computing systems usually have a lot of processors, such as “Tianhe-2” with 3,120,000 cores and “Titan” with 560,640 cores [2]. One of the main problems existing in this situation is system reliability, which drastically decreases as the number of processor cores increases [4]. Even when the single processor’s one-hour reliability becomes very high, such as 0.999999, as the system size approaches 10,000 cores, the system’s MTTF (the Mean Time to Failure) drops to less than 10 hours [4]. This also allows us to focus primarily on the main problem of this paper, which is thesimultaneous management of system performance, reliability, and energy consumption.In recognition of this, we first build a reliability and energy aware task scheduling architecture including precedence-constrained parallel applications and energy consumption model on heterogeneous systems. Then, we propose the single processor failure rate model based on DVFS technique and deduce the application reliability of systems. Finally, to provide an optimum solution for this problem, we propose a heuristic Reliability-Energy Aware Scheduling (REAS) algorithm, which adopts a novel scheduling objective RE. The overall objective of this paper is trying to get good tradeoff among performance, reliability, and energy consumption.The rest of the paper is organized as follows: the related work is summarized in Section2. We describe the task scheduling system model in Section 3. In Section 4, we provide a system reliability model. To solve this problem, a heuristic reliability and energy aware task scheduling algorithm is proposed in Section 5. In Section 6, we verify the performance of the proposed algorithm by comparing the results obtained from performance evaluation. Finally, we summarize the contributions and make some remarks on further research in Section 7.


## 2. Related Work

The high-performance parallel application running on computing systems is usually composed of intercommunicated tasks, which are scheduled to run over different processors in the systems. In most cases, the main objective of scheduling strategies is to map the multiple interacting program tasks onto processors and order their executions so that task precedence requirements are satisfied and, in the meanwhile, the minimum schedule length (makespan) can be achieved. The problem of finding the optimal schedule is NP-complete in general [5–9]. There are many scheduling algorithms that have been proposed to deal with this problem, for example, dynamic-level scheduling (DLS) algorithm [6] and heterogeneous earliest-finish-time (HEFT) algorithm [5, 8, 10, 11].As the energy consumption has become important issue in designing large-scale computing systems in the last few years, many techniques including dynamic voltage-frequency scaling (DVFS), dynamic powering on/off, slack reclamation, resource hibernation, and memory optimizations have been investigated and developed to reduce energy consumption [12–14]. DVFS, which is a technique in which a processor runs at a less-than-maximum frequency when it is not fully utilized in order to conserve power, is perhaps the most appealing method for reducing energy consumption [14, 15]. Most of the early DVFS-enabled researches focused on the single processor of embedded and real-time computing systems [14, 16, 17]. Recently, there has been a significant amount of work on task scheduling for heterogeneous systems using DVFS-enabled techniques. For instance, Rountree et al. focused on energy optimization of MPI program in HPC environment and proposed a linear programming (LP), which incorporates allowable time delays, communication slack, and memory pressure into its scheduling using DVFS (i.e., slack reclamation) [18]. Rizvandi et al. proposed a method to find the best frequencies of processor to obtain the optimal energy consumption [19]. Lee and Zomaya addressed the problem of scheduling precedence-constrained parallel applications on multiprocessor computer systems and their scheduling decisions are made using the relative superiority metric (RS) devised as a novel objective function [20]. In [21], Zong et al. proposed two energy-efficient scheduling algorithms (EAD and PEBD) for parallel tasks on homogeneous clusters based on duplication strategy.All of this work demonstrated that dynamic adjusting the processor’s voltage and frequency can effectively reduce system energy consumption. However, recent researches have illustrated that scaling the processor’s voltage and frequency has negative impact of nanoscale semiconductor circuits’s cosmic ray radiations, electromagnetic interference, and alpha particles, which enforce the unreliability of processor [22–24]. Thus, it is a good way to incorporate the reliability into energy aware scheduling based on DVFS. Recently, Zhu etc. focused on reducing energy consumption while preserving the system reliability for periodic real-time tasks [25, 26]. They proposed a reliability model that the processor’s reliability decreases as scaling their voltage and frequency from max to min and incorporated the reliability requirements into heuristic energy aware task scheduling strategies. However, their techniques are not suitable for precedence-constrained parallel applications on heterogeneous systems based on DVFS-enabled processors.Many researches had dealt with the reliability on heterogeneous systems. For example, Dogan and Özgüner introduced three reliability cost functions that were incorporated into making dynamic level (DL) and proposed a reliable dynamic level scheduling algorithm (RDLS) [27]; the goal was to minimize not only the execution time but also the failure probability of the application. In our previous work [8], we propose a scheduling algorithm which considers the task’s execution reliability. Qin and Jiang investigated a dynamic and reliability-cost-driven (DRCD) scheduling algorithms for precedence-constrained tasks in heterogeneous clusters [28]. Unfortunately, those works did not consider the energy consumption and the reliability of scaling the processor’s voltage and frequency. In recognition of this, we focus on the reliability and energy consumption on DVFS-enabled heterogeneous systems.


## 3. System Models

### 3.1. Scheduling Architecture

Various task scheduling architectures are proposed in literature [5, 8, 9, 14, 28, 29]. However, the energy consumption and system reliability are not effectively incorporated into scheduling. In this paper, we propose a reliability and energy aware task scheduling architecture, as depicted in Figure 1(a). It is assumed that all parallel applications, along with information provided by user, are submitted to system by a special user command. First, the parallel applications are divided as a task DAG byTask  DAG  Model. Then, the estimate energy consumption of tasks, which are executed on the DVFS-enabled heterogonous processors, is computed by theEneregy  Consumption  Estimator. At the same time,reliability  analysis computes the processors’ reliability according to different frequency to get the whole system reliability. Finally, theScheduler schedules tasks based on the above task energy consumption and system reliability.Figure 1
(a) The reliability and energy aware task scheduling architecture. (b) A parallel application task graph.
(a)
(b)


### 3.2. Heterogeneous Systems

The target system used in this work consists of a set ofP
=
{
p
1
,
p
2
,
…
,
p
m
} heterogeneous processors/machines [5, 8, 9, 14, 29], which are connected by high-speed interconnects, such as Infiniband and Myrinet. Each DVFS-enabled processor p
k
∈
P can adjust its operational voltage and frequency [14]. Therefore, they can be executed on discrete set of frequency-voltage pairs, (
f
k
,
l
,
V
k
,
l
), in which (
f
k
,
1
<
f
k
,
2
<
⋯
<
f
k
,
M
k
) and (
V
k
,
1
,
V
k
,
2
<
⋯
<
V
k
,
M
k
), where M
k is processor p
k’s operation level [14, 30]. For example, the quad-core AMD Phenom II supports 4 different frequencies (0.8 GHz, 2.1 GHz, 2.5 GHz, and 3.2 GHz) and voltages ranging from 0.85 V to 1.425 V [30]. Since clock frequency transition overheads take a negligible amount of time (e.g., 10 us–150 us), these overheads are not considered in our study.The heterogeneous processor’s failure is assumed to follow a Poisson process and each processor has a constant failure rateλ [8, 9, 29]. For example, λ
k denotes a processor p
k failure rate when it works at normal voltage and frequency [8, 9, 27, 29]. These failure rates can be derived from system’s profiling, system log, and statistical prediction techniques [31]. For demonstration purposes, we illustrate two heterogeneous processors, one has 3 frequency levels and the other has 2 frequency levels, and the parameters are listed in Table 1.Table 1
The parameters of heterogeneous processors.
λ
k
P
s
[
k
]
α
[
k
]
(f
k
,
l, V
k
,
l)
1
2
3
p
1
1.4 × 10−4
73.6
3.663 × 10−8
(0.8 × 109, 0.93)
(2.1 × 109, 1.23)
(3.2 × 109, 1.43)
p
2
1.62 × 10−4
57.1
4.95 × 10−8
(2.3 × 109, 0.85)
(3.0 × 109, 1.36)


### 3.3. Applications Model

The precedence-constrained tasks of parallel application are usually denoted as a Directed Acyclic Graph (DAG)G
=
V
,
R
,
[
d
i
,
j
,
w
i
,
k
,
l
] [5, 8–10, 29], where V
=
{
v
1
,
v
2
,
…
,
v
n
} is the set with n tasks that can be scheduled to any available DVFS-enabled processors [5, 8–10, 29]; R represents the precedence relation that defines a partial order on the task set V, such that v
i
R
v
j implies that the task v
i must be finished, before v
j can start execution [5, 8–10, 29]. [
d
i
,
j
] is n
×
n communication matrix that denotes the communication time between tasks v
i and v
j for 1
≤
i, j
≤
n. [
w
i
,
k
,
l
] is n
×
m
×
M
max
⁡ computation matrix in which each w
i
,
k
,
l gives the estimated time to execute task v
i on processor p
k at frequency f
k
,
l. Here, M
max
⁡ is the maximal operation level on systems. The communication cost and computation cost can be evaluated by building a historic table and using code profiling or statistical prediction techniques [31]. Figure 1(b) shows a parallel application DAG, Table 2 lists the tasks execution time on two heterogeneous DVFS-enabled processors listed in Table 1, and the communication time among these tasks is listed in Table 3.Table 2
Task estimated execution matrix[
w
i
,
k
,
l
].
Task
p
1
p
2
p
1,1
p
1,2
p
1,3
p
2,1
p
2,2
v
1
11.12
2.28
2.87
3.89
3
v
2
36.29
13.82
9.12
12.7
9.78
v
3
15.46
5.91
3.92
5.45
4.21
v
4
5.33
2.01
1.4
1.94
1.49
v
5
66.77
25.44
16.77
23.28
17.83
v
6
13.82
5.3
3.53
4.84
3.75
v
7
7.43
2.86
1.89
2.68
2.04
v
8
8.48
3.19
2.09
2.91
2.31Table 3
Estimated communication matrix[
d
i
,
j
].
Task
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
1
6.99
15.48
6.69
v
2
10.86
v
3
1.25
12.56
v
4
6.93
0.3
v
5
0.11
v
6
6.535
v
7
6.2Generally, the common objective of task scheduling is to map tasks with precedence constrained onto processors and get a minimum schedule length (which is also called makespan) [10, 11]. Before presenting the schedule length, it is necessary to define the scheduling attributes EST and EFT of task v
i. EST
(
v
i
,
f
k
,
l
) denotes the earliest execution starting time of task v
i
∈
V on DVFS-enabled processor p
k
∈
P at frequency f
k
,
l, which is constrained by tasks precedence relation and the available time of processor p
k [5, 8–10, 29]. EFT
(
v
i
,
f
k
,
l
) is the earliest execution finish time of task v
i on processor p
k at frequency f
k
,
l, which is described as(1)
EFT
v
i
,
f
k
,
l
=
EST
v
i
,
f
k
,
l
+
w
i
,
k
,
l
.In this paper, letX
i
,
k
l
=
1 denote the task v
i scheduled on processor p
k at frequency f
k
,
l; otherwise X
i
,
k
l
=
0. Thus, the schedule length is defined as follows:(2)
makespan
=
Max
⁡
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
EFT
v
i
,
f
k
,
l
.


### 3.4. Energy Model

The major energy consumption of computing systems depends on its memory, disks, CPUs, and other components. This paper only considers DVFS-enabled CPUs, which consume the largest proportion of energy on systems [14, 19, 20, 32]. The power consumption of DVFS-enabled microprocessor based on complementary metal-oxide semiconductor (CMOS) logic circuits mainly consists ofstatic  power anddynamic  power  dissipation, which can be modeled as [25, 26](3)
P
=
P
s
+
∅
P
d
,where P
s is thestatic  power, which is a constant and the power used to maintain basic circuits and keep the clock running, andfrequency-independent  active  power. ∅ denotes the processor’s model, if processor is atexecution model, ∅
=
1; otherwise, ∅
=
0. P
d is the most significant factor of processor power consumption and can be estimated as [14, 16, 19, 20, 32](4)
P
d
=
α
V
2
f
,where α represents the switched capacitance, V is the supply voltage, f represents processor’s working frequency, and σ stands for circuit dependent constant. The example of such processor parameters is listed in Table 1.LetEN
(
v
i
,
f
k
,
l
) be the energy consumption caused by task v
i running on DVFS-enabled processor p
k at frequency f
k
,
l, of which it is determined by task execution time and processor power consumption:(5)
EN
v
i
,
f
k
,
l
=
w
i
,
k
,
l
×
P
k
=
w
i
,
k
,
l
×
P
s
k
+
w
i
,
k
,
l
×
P
d
f
k
,
l
,where P
d
(
f
k
,
l
) denotesdynamic  power  dissipation of processor p
k at frequency f
k
,
l (see (4)). Thus, for an application G, the energy consumption EN
(
V
) is the summation of all tasks of energy consumption:(6)
EN
V
=
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
EN
v
i
,
f
k
,
l
=
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
w
i
,
k
,
l
×
P
s
k
+
X
i
,
k
l
w
i
,
k
,
l
×
P
d
f
k
,
l
.At the same time, for heterogeneous systems, all processors are power-on; they are sleep or execution model. That is to say, all processors of systems consumes
t
a
t
i
c
p
o
w
e
r all the time. Thus, the computing systems energy consumption EN
(
P
) is the summation of all processorsstatic  power anddynamic  power  dissipation of application energy consumption:(7)
EN
P
=
makespan
×
∑
k
=
1,2
,
…
,
m
P
s
k
+
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
w
i
,
k
,
l
×
P
d
f
k
,
l
.Obviously, systems energy consumptionEN
(
P
) is greater than application energy consumption EN
(
V
). In this paper, one of our main objectives is to minimize systems energy consumption EN
(
P
).


## 3.1. Scheduling Architecture

Various task scheduling architectures are proposed in literature [5, 8, 9, 14, 28, 29]. However, the energy consumption and system reliability are not effectively incorporated into scheduling. In this paper, we propose a reliability and energy aware task scheduling architecture, as depicted in Figure 1(a). It is assumed that all parallel applications, along with information provided by user, are submitted to system by a special user command. First, the parallel applications are divided as a task DAG byTask  DAG  Model. Then, the estimate energy consumption of tasks, which are executed on the DVFS-enabled heterogonous processors, is computed by theEneregy  Consumption  Estimator. At the same time,reliability  analysis computes the processors’ reliability according to different frequency to get the whole system reliability. Finally, theScheduler schedules tasks based on the above task energy consumption and system reliability.Figure 1
(a) The reliability and energy aware task scheduling architecture. (b) A parallel application task graph.
(a)
(b)


## 3.2. Heterogeneous Systems

The target system used in this work consists of a set ofP
=
{
p
1
,
p
2
,
…
,
p
m
} heterogeneous processors/machines [5, 8, 9, 14, 29], which are connected by high-speed interconnects, such as Infiniband and Myrinet. Each DVFS-enabled processor p
k
∈
P can adjust its operational voltage and frequency [14]. Therefore, they can be executed on discrete set of frequency-voltage pairs, (
f
k
,
l
,
V
k
,
l
), in which (
f
k
,
1
<
f
k
,
2
<
⋯
<
f
k
,
M
k
) and (
V
k
,
1
,
V
k
,
2
<
⋯
<
V
k
,
M
k
), where M
k is processor p
k’s operation level [14, 30]. For example, the quad-core AMD Phenom II supports 4 different frequencies (0.8 GHz, 2.1 GHz, 2.5 GHz, and 3.2 GHz) and voltages ranging from 0.85 V to 1.425 V [30]. Since clock frequency transition overheads take a negligible amount of time (e.g., 10 us–150 us), these overheads are not considered in our study.The heterogeneous processor’s failure is assumed to follow a Poisson process and each processor has a constant failure rateλ [8, 9, 29]. For example, λ
k denotes a processor p
k failure rate when it works at normal voltage and frequency [8, 9, 27, 29]. These failure rates can be derived from system’s profiling, system log, and statistical prediction techniques [31]. For demonstration purposes, we illustrate two heterogeneous processors, one has 3 frequency levels and the other has 2 frequency levels, and the parameters are listed in Table 1.Table 1
The parameters of heterogeneous processors.
λ
k
P
s
[
k
]
α
[
k
]
(f
k
,
l, V
k
,
l)
1
2
3
p
1
1.4 × 10−4
73.6
3.663 × 10−8
(0.8 × 109, 0.93)
(2.1 × 109, 1.23)
(3.2 × 109, 1.43)
p
2
1.62 × 10−4
57.1
4.95 × 10−8
(2.3 × 109, 0.85)
(3.0 × 109, 1.36)


## 3.3. Applications Model

The precedence-constrained tasks of parallel application are usually denoted as a Directed Acyclic Graph (DAG)G
=
V
,
R
,
[
d
i
,
j
,
w
i
,
k
,
l
] [5, 8–10, 29], where V
=
{
v
1
,
v
2
,
…
,
v
n
} is the set with n tasks that can be scheduled to any available DVFS-enabled processors [5, 8–10, 29]; R represents the precedence relation that defines a partial order on the task set V, such that v
i
R
v
j implies that the task v
i must be finished, before v
j can start execution [5, 8–10, 29]. [
d
i
,
j
] is n
×
n communication matrix that denotes the communication time between tasks v
i and v
j for 1
≤
i, j
≤
n. [
w
i
,
k
,
l
] is n
×
m
×
M
max
⁡ computation matrix in which each w
i
,
k
,
l gives the estimated time to execute task v
i on processor p
k at frequency f
k
,
l. Here, M
max
⁡ is the maximal operation level on systems. The communication cost and computation cost can be evaluated by building a historic table and using code profiling or statistical prediction techniques [31]. Figure 1(b) shows a parallel application DAG, Table 2 lists the tasks execution time on two heterogeneous DVFS-enabled processors listed in Table 1, and the communication time among these tasks is listed in Table 3.Table 2
Task estimated execution matrix[
w
i
,
k
,
l
].
Task
p
1
p
2
p
1,1
p
1,2
p
1,3
p
2,1
p
2,2
v
1
11.12
2.28
2.87
3.89
3
v
2
36.29
13.82
9.12
12.7
9.78
v
3
15.46
5.91
3.92
5.45
4.21
v
4
5.33
2.01
1.4
1.94
1.49
v
5
66.77
25.44
16.77
23.28
17.83
v
6
13.82
5.3
3.53
4.84
3.75
v
7
7.43
2.86
1.89
2.68
2.04
v
8
8.48
3.19
2.09
2.91
2.31Table 3
Estimated communication matrix[
d
i
,
j
].
Task
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
1
6.99
15.48
6.69
v
2
10.86
v
3
1.25
12.56
v
4
6.93
0.3
v
5
0.11
v
6
6.535
v
7
6.2Generally, the common objective of task scheduling is to map tasks with precedence constrained onto processors and get a minimum schedule length (which is also called makespan) [10, 11]. Before presenting the schedule length, it is necessary to define the scheduling attributes EST and EFT of task v
i. EST
(
v
i
,
f
k
,
l
) denotes the earliest execution starting time of task v
i
∈
V on DVFS-enabled processor p
k
∈
P at frequency f
k
,
l, which is constrained by tasks precedence relation and the available time of processor p
k [5, 8–10, 29]. EFT
(
v
i
,
f
k
,
l
) is the earliest execution finish time of task v
i on processor p
k at frequency f
k
,
l, which is described as(1)
EFT
v
i
,
f
k
,
l
=
EST
v
i
,
f
k
,
l
+
w
i
,
k
,
l
.In this paper, letX
i
,
k
l
=
1 denote the task v
i scheduled on processor p
k at frequency f
k
,
l; otherwise X
i
,
k
l
=
0. Thus, the schedule length is defined as follows:(2)
makespan
=
Max
⁡
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
EFT
v
i
,
f
k
,
l
.


## 3.4. Energy Model

The major energy consumption of computing systems depends on its memory, disks, CPUs, and other components. This paper only considers DVFS-enabled CPUs, which consume the largest proportion of energy on systems [14, 19, 20, 32]. The power consumption of DVFS-enabled microprocessor based on complementary metal-oxide semiconductor (CMOS) logic circuits mainly consists ofstatic  power anddynamic  power  dissipation, which can be modeled as [25, 26](3)
P
=
P
s
+
∅
P
d
,where P
s is thestatic  power, which is a constant and the power used to maintain basic circuits and keep the clock running, andfrequency-independent  active  power. ∅ denotes the processor’s model, if processor is atexecution model, ∅
=
1; otherwise, ∅
=
0. P
d is the most significant factor of processor power consumption and can be estimated as [14, 16, 19, 20, 32](4)
P
d
=
α
V
2
f
,where α represents the switched capacitance, V is the supply voltage, f represents processor’s working frequency, and σ stands for circuit dependent constant. The example of such processor parameters is listed in Table 1.LetEN
(
v
i
,
f
k
,
l
) be the energy consumption caused by task v
i running on DVFS-enabled processor p
k at frequency f
k
,
l, of which it is determined by task execution time and processor power consumption:(5)
EN
v
i
,
f
k
,
l
=
w
i
,
k
,
l
×
P
k
=
w
i
,
k
,
l
×
P
s
k
+
w
i
,
k
,
l
×
P
d
f
k
,
l
,where P
d
(
f
k
,
l
) denotesdynamic  power  dissipation of processor p
k at frequency f
k
,
l (see (4)). Thus, for an application G, the energy consumption EN
(
V
) is the summation of all tasks of energy consumption:(6)
EN
V
=
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
EN
v
i
,
f
k
,
l
=
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
w
i
,
k
,
l
×
P
s
k
+
X
i
,
k
l
w
i
,
k
,
l
×
P
d
f
k
,
l
.At the same time, for heterogeneous systems, all processors are power-on; they are sleep or execution model. That is to say, all processors of systems consumes
t
a
t
i
c
p
o
w
e
r all the time. Thus, the computing systems energy consumption EN
(
P
) is the summation of all processorsstatic  power anddynamic  power  dissipation of application energy consumption:(7)
EN
P
=
makespan
×
∑
k
=
1,2
,
…
,
m
P
s
k
+
∑
1
≤
i
≤
n
,
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
w
i
,
k
,
l
×
P
d
f
k
,
l
.Obviously, systems energy consumptionEN
(
P
) is greater than application energy consumption EN
(
V
). In this paper, one of our main objectives is to minimize systems energy consumption EN
(
P
).


## 4. System Reliability Analysis and Problem Statement

In this section, we first provide the single DVFS-enabled processor failure rate model. Then, we analyze heterogeneous systems reliability. At last, we formulate the reliability and energy aware task scheduling as a linear programming problem.


### 4.1. Single DVFS-Enabled Processor Failure Rate

Among various sources of unreliability in a semiconductor circuit processor, it is predicted that the failure rate due to cosmic ray radiation-induced soft errors dominates all other reliability issues [24]. Transient fault occurs when a high energy particle such as alpha or neutron strikes a sensitive region in a semiconductor device and flips the logical state of the struck node [33]. Most of the modern DVFS-enabled processor is the integration of multibillion transistors on a single chip leading to increasing number of sensitive devices in submicron technologies which is vulnerable to soft error and consequently raises theSoft Error Rate (SER) [34]. These phenomena become more and more serious with the continued scaling of processor’s voltage and frequency [23, 25].Traditionally, the modern DVFS-enabled processor’s reliability has been modeled as the following Poisson distribution with a failure rateλ when it works at normal voltage and frequency [8, 9, 27, 29, 35]. Moreover, it has been shown that DVFS has a direct and negative effect on failure rates as blindly applying DVFS to scale the supply voltage and processing frequency for energy savings, which may cause significant degradation in processor’s reliability [23, 25, 26]. Therefore, for the DVFS-enabled heterogonous processor p
k
∈
P to be considered in this paper, the failure rate at a reduced frequency f
k
,
l (and the corresponding voltage V
k
,
l) can be modeled as(8)
λ
k
f
k
,
l
=
λ
k
·
H
k
f
k
,
l
,where λ
k is the failure rate corresponding to the normal processing frequency f
nm (and corresponding to normal voltage V
nm). Prior researches which studied the effect of normal voltage on processor’s reliability have revealed that the failure rates generally increase with scaled processing frequencies (and supply voltages) away from normal voltage [24, 36]. On the other hand, the fault rates are exponentially related to the circuit’s critical charge (which is the threshold voltage). Thus, we have the following equations:(9)
H
k
f
k
,
l
=
e
ψ
k
V
t
k
10
ξ
k
f
k
,
l
-
f
nm
/
f
max
⁡
-
f
min
⁡
f
nm
≤
f
k
,
l
≤
f
max
⁡
e
ψ
k
V
t
k
10
ξ
k
f
nm
-
f
k
,
l
/
f
max
⁡
-
f
min
⁡
f
min
⁡
≤
f
k
,
l
≤
f
nm
,where the exponent ψ
k is the parameter of threshold voltage and ξ
k is a constant, representing the sensitivity of fault rates to frequency scaling, and f
min
⁡ and f
max
⁡ denote the minimum and maximum frequency, respectively.In order to get the precision value of parametersψ
k and ξ
k, we use least squares curve fitting method [37]. Therefore, the natural logarithm of both sides for (9) is(10)
ln
⁡
H
k
f
k
,
l
=
ψ
k
V
t
k
+
ξ
k
ln
⁡
10
f
k
,
l
-
f
nm
f
max
⁡
-
f
min
⁡
f
nm
≤
f
k
,
l
≤
f
max
⁡
ψ
k
V
t
k
+
ξ
k
ln
⁡
10
f
nm
-
f
k
,
l
f
max
⁡
-
f
min
⁡
f
min
⁡
≤
f
k
,
l
≤
f
nm
.Let y
=
ln
⁡
(
H
k
(
f
k
,
l
)
), A
=
ψ
k
V
t
k, B
=
ξ
k
ln
⁡
10
(
1
/
(
f
max
⁡
-
f
min
⁡
)
), and C
=
ξ
k
ln
⁡
10
(
f
nm
/
(
f
max
⁡
-
f
min
⁡
)
). Then, (10) becomes(11)
y
=
A
+
B
f
k
,
l
-
C
f
nm
≤
f
k
,
l
≤
f
max
⁡
A
-
B
f
k
,
l
+
C
f
min
⁡
≤
f
k
,
l
≤
f
nm
.Thus, we can get the parameters ψ
k and ξ
k approximation value by using least squares linear fitting method.


### 4.2. Application Reliability Analysis

Assume that the taskv processing time has taken place during the time interval [
A
,
B
] on heterogeneous DVFS-enabled processor p
k at frequency f
k
,
l, where A denotes the task start execution time and B denotes the task finish time [5, 8, 9, 29]. Thus, the task execution reliability can be given by(12)
P
v
=
P
X
B
-
X
A
=
0
=
P
X
B
-
A
+
A
-
X
A
=
0
=
exp
⁡
-
λ
k
f
k
,
l
B
-
A
.For a taskv
i of application G on processor p
k at frequency f
k
,
l, its reliability P
[
v
i
,
f
k
,
l
] is equal to all of its immediate parent tasks and its execution reliability, which can be defined by(13)
P
v
i
,
f
k
,
l
=
∏
v
j
∈
pred
v
i
P
v
j
×
exp
⁡
-
λ
k
f
k
,
l
×
w
i
,
k
,
l
,where pred
(
v
i
) denotes all direct predecessors of v
i and P
[
v
j
] is the reliability of task v
j that is equal to the reliability of task v
i executing on processor p
k at frequency f
k
,
l
(14)
P
v
j
=
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
1
,
k
l
P
v
j
,
f
k
,
l
.For the entry taskv
1 of application, which is executed on processor p
k at frequency f
k
,
l and pred
(
v
1
)
=
ϕ, its reliability(15)
P
v
1
,
f
k
,
l
=
exp
⁡
-
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
1
,
k
l
λ
k
f
k
,
l
×
w
1
,
k
,
l
.Generally, applicationG has one exit task v
exit. The reliability of application P
[
G
] is equal to the exit task v
exit:(16)
P
G
=
P
v
exit
=
∏
v
j
∈
pred
v
exit
P
v
j
×
P
v
exit
,
f
k
,
l
.This is the other objective of this paper, in which we try to improve the application reliabilityP
[
G
]. From the above analysis, we know that allocating tasks with less execution times to more reliable processors might be a good heuristic to increase the reliability.


### 4.3. Problem Statement

As simultaneous management of scheduling performance, system reliability, and energy consumption is the main problem of this paper, we formulate it as follows:(17)
M
i
n
i
m
i
z
e
makespan
Minimize
EN
P
M
a
x
i
m
i
z
e
P
G
s.t.
X
i
,
k
l
=
1
Or
X
i
,
k
l
=
0
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
=
1
∀
v
i
∈
V
v
i
R
v
j
∀
v
i
,
v
j
∈
V
.


## 4.1. Single DVFS-Enabled Processor Failure Rate

Among various sources of unreliability in a semiconductor circuit processor, it is predicted that the failure rate due to cosmic ray radiation-induced soft errors dominates all other reliability issues [24]. Transient fault occurs when a high energy particle such as alpha or neutron strikes a sensitive region in a semiconductor device and flips the logical state of the struck node [33]. Most of the modern DVFS-enabled processor is the integration of multibillion transistors on a single chip leading to increasing number of sensitive devices in submicron technologies which is vulnerable to soft error and consequently raises theSoft Error Rate (SER) [34]. These phenomena become more and more serious with the continued scaling of processor’s voltage and frequency [23, 25].Traditionally, the modern DVFS-enabled processor’s reliability has been modeled as the following Poisson distribution with a failure rateλ when it works at normal voltage and frequency [8, 9, 27, 29, 35]. Moreover, it has been shown that DVFS has a direct and negative effect on failure rates as blindly applying DVFS to scale the supply voltage and processing frequency for energy savings, which may cause significant degradation in processor’s reliability [23, 25, 26]. Therefore, for the DVFS-enabled heterogonous processor p
k
∈
P to be considered in this paper, the failure rate at a reduced frequency f
k
,
l (and the corresponding voltage V
k
,
l) can be modeled as(8)
λ
k
f
k
,
l
=
λ
k
·
H
k
f
k
,
l
,where λ
k is the failure rate corresponding to the normal processing frequency f
nm (and corresponding to normal voltage V
nm). Prior researches which studied the effect of normal voltage on processor’s reliability have revealed that the failure rates generally increase with scaled processing frequencies (and supply voltages) away from normal voltage [24, 36]. On the other hand, the fault rates are exponentially related to the circuit’s critical charge (which is the threshold voltage). Thus, we have the following equations:(9)
H
k
f
k
,
l
=
e
ψ
k
V
t
k
10
ξ
k
f
k
,
l
-
f
nm
/
f
max
⁡
-
f
min
⁡
f
nm
≤
f
k
,
l
≤
f
max
⁡
e
ψ
k
V
t
k
10
ξ
k
f
nm
-
f
k
,
l
/
f
max
⁡
-
f
min
⁡
f
min
⁡
≤
f
k
,
l
≤
f
nm
,where the exponent ψ
k is the parameter of threshold voltage and ξ
k is a constant, representing the sensitivity of fault rates to frequency scaling, and f
min
⁡ and f
max
⁡ denote the minimum and maximum frequency, respectively.In order to get the precision value of parametersψ
k and ξ
k, we use least squares curve fitting method [37]. Therefore, the natural logarithm of both sides for (9) is(10)
ln
⁡
H
k
f
k
,
l
=
ψ
k
V
t
k
+
ξ
k
ln
⁡
10
f
k
,
l
-
f
nm
f
max
⁡
-
f
min
⁡
f
nm
≤
f
k
,
l
≤
f
max
⁡
ψ
k
V
t
k
+
ξ
k
ln
⁡
10
f
nm
-
f
k
,
l
f
max
⁡
-
f
min
⁡
f
min
⁡
≤
f
k
,
l
≤
f
nm
.Let y
=
ln
⁡
(
H
k
(
f
k
,
l
)
), A
=
ψ
k
V
t
k, B
=
ξ
k
ln
⁡
10
(
1
/
(
f
max
⁡
-
f
min
⁡
)
), and C
=
ξ
k
ln
⁡
10
(
f
nm
/
(
f
max
⁡
-
f
min
⁡
)
). Then, (10) becomes(11)
y
=
A
+
B
f
k
,
l
-
C
f
nm
≤
f
k
,
l
≤
f
max
⁡
A
-
B
f
k
,
l
+
C
f
min
⁡
≤
f
k
,
l
≤
f
nm
.Thus, we can get the parameters ψ
k and ξ
k approximation value by using least squares linear fitting method.


## 4.2. Application Reliability Analysis

Assume that the taskv processing time has taken place during the time interval [
A
,
B
] on heterogeneous DVFS-enabled processor p
k at frequency f
k
,
l, where A denotes the task start execution time and B denotes the task finish time [5, 8, 9, 29]. Thus, the task execution reliability can be given by(12)
P
v
=
P
X
B
-
X
A
=
0
=
P
X
B
-
A
+
A
-
X
A
=
0
=
exp
⁡
-
λ
k
f
k
,
l
B
-
A
.For a taskv
i of application G on processor p
k at frequency f
k
,
l, its reliability P
[
v
i
,
f
k
,
l
] is equal to all of its immediate parent tasks and its execution reliability, which can be defined by(13)
P
v
i
,
f
k
,
l
=
∏
v
j
∈
pred
v
i
P
v
j
×
exp
⁡
-
λ
k
f
k
,
l
×
w
i
,
k
,
l
,where pred
(
v
i
) denotes all direct predecessors of v
i and P
[
v
j
] is the reliability of task v
j that is equal to the reliability of task v
i executing on processor p
k at frequency f
k
,
l
(14)
P
v
j
=
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
1
,
k
l
P
v
j
,
f
k
,
l
.For the entry taskv
1 of application, which is executed on processor p
k at frequency f
k
,
l and pred
(
v
1
)
=
ϕ, its reliability(15)
P
v
1
,
f
k
,
l
=
exp
⁡
-
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
1
,
k
l
λ
k
f
k
,
l
×
w
1
,
k
,
l
.Generally, applicationG has one exit task v
exit. The reliability of application P
[
G
] is equal to the exit task v
exit:(16)
P
G
=
P
v
exit
=
∏
v
j
∈
pred
v
exit
P
v
j
×
P
v
exit
,
f
k
,
l
.This is the other objective of this paper, in which we try to improve the application reliabilityP
[
G
]. From the above analysis, we know that allocating tasks with less execution times to more reliable processors might be a good heuristic to increase the reliability.


## 4.3. Problem Statement

As simultaneous management of scheduling performance, system reliability, and energy consumption is the main problem of this paper, we formulate it as follows:(17)
M
i
n
i
m
i
z
e
makespan
Minimize
EN
P
M
a
x
i
m
i
z
e
P
G
s.t.
X
i
,
k
l
=
1
Or
X
i
,
k
l
=
0
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
X
i
,
k
l
=
1
∀
v
i
∈
V
v
i
R
v
j
∀
v
i
,
v
j
∈
V
.


## 5. Proposed Reliability-Energy Aware Scheduling Algorithm

This section presents a Reliability-Energy Aware Scheduling algorithm on heterogeneous systems called REAS, which aims at achieving lower energy consumption, high reliability, and shorter schedule length. Its scheduling decisions are made using the hybrid metric including energy consumption, reliability, and schedule length, devised as a novel objective function. The pseudocode of the algorithm is shown in Algorithm1. The algorithm is complete in three main phases as described in the following sections.Algorithm 1:The pseudocode for REAS algorithm.
Input: The task DAG of parallel applications
Output: The scheduling of task-processor pairs
(1) Calculate each task b_level of DAG
(2) Sort tasks in a scheduling list by non-increasing order of b_level
(3) while  the scheduling list isnot empty  do
(4)  Remove the first task v
i from the scheduling list
(5)  Set min
⁡
F
(
v
i
), min
⁡
E
(
v
i
) as maximum value
(6)  for  each processor-frequency
f
k
,
l
in systems  do
(7)   Compute the earliest finish time E
F
T
(
v
i
,
f
k
,
l
) use (22)
(8)
if  min
⁡
F
(
v
i
)
>
E
F
T
(
v
i
,
f
k
,
l
)  then
(9)
min
⁡
F
(
v
i
)
=
E
F
T
(
v
i
,
f
k
,
l
)
(10)  end
(11)  Compute task energy consumption E
N
(
v
i
,
f
k
,
l
) use (5)
(12)
if  min
⁡
E
(
v
i
)
>
E
N
(
v
i
,
f
k
,
l
)  then
(13)
min
⁡
E
(
v
i
)
=
E
N
(
v
i
,
f
k
,
l
)
(14)
end
(15) end
(16) Set min
⁡
R
E
(
v
i
) as maximum value
(17) for  each processor-frequency  f
k
,
l  in systems  do
(18)  Compute the earliest finish time E
F
T
(
v
i
,
f
k
,
l
) use (22)
(19)  Compute task energy consumption E
N
(
v
i
,
f
k
,
l
) use (5)
(20)  Compute metric R
E
(
v
i
,
f
k
,
l
) use (24)
(21)
if  min
⁡
R
E
(
v
i
)
>
R
E
(
v
i
,
f
k
,
l
)  then
(22)
min
⁡
R
E
(
v
i
)
=
R
E
(
v
i
,
f
k
,
l
)
(23)
end
(24) end
(25) Assign task v
i to the corresponding processor-frequency
(26) Update the processor execution finish time
(27) end
(28) “Slack reclamation
(29) for  each task in scheduling task-processor pairs  do
(30) Compute task slack time S
l
a
c
k
(
v
i
) use (25)
(31)
for  each frequency of processor
k  do
(32)  Compute the optimal frequency f
k
,
l use (26)
(33)
end
(34) Reassign task v
i and update corresponding data
(35) end
(36) Compute the schedule length, application reliability P
[
G
], systems energy consumption E
N
(
P
)


### 5.1. Task Priorities Phase

This step is essential for list scheduling algorithms. A task processing list is generated by sorting the task by decreasing order of some predefined rank function, such ast
_
level, b
_
level, Rank, CP, and DL [5, 6, 8–10, 29]. Here, we use the average computation capacity, which is defined as(18)
w
v
i
¯
=
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
w
i
,
k
,
l
∑
1
≤
k
≤
m
M
k
.In this research, we useb
_
level as the rank function. The b
_
level of task v
i is the sum of the path weight from task v
i to exit task. We can compute this value recursively traversing DAG from exit task, and it is defined as follows:(19)
b
_level
v
i
=
w
v
i
¯
+
Max
⁡
v
j
∈
succ
v
i
⁡
d
i
,
j
+
b
_level
v
j
+
RC
v
i
,where succ
(
v
i
) is the set of immediate successors of task v
i. RC
(
v
i
) is the average reliability overhead of task v
i and can be computed by(20)
RC
v
i
=
1
-
exp
⁡
-
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
λ
k
f
k
,
l
∑
1
≤
k
≤
m
M
k
×
w
v
i
¯
×
w
v
i
¯
.For the exit taskv
exit, the b
_
level is equal to(21)
b
_
level
v
exit
=
w
v
exit
¯
+
RC
v
exit
.Basically,b
_
level
(
v
i
) is the length of the critical path from task v
i to the exit task, including the average computation cost and reliability overhead of task v
i. For example, considering the application DAG in Figure 1(b), heterogeneous systems parameters in Table 1, task execution time matrix in Table 2, and communication matrix in Table 3, the task b
_
level value which is recursively computed by (19) and (21) is shown in Table 4.Table 4
Theb_level value of task.
Task
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
b_level
73.4
61.4
42.4
26
34.15
16.6
13.7
3.8
Seq
1
2
3
5
4
6
7
8


### 5.2. Task Assignment Phase

In this phase, tasks are assigned to the processors with earliest execution finish timeEFT
(
v
i
), high reliability, and minimum task energy consumption EN
(
v
i
). However, for heterogeneous systems, these performance metrics are conflicted most of the time. Here, we introduce a novel objective as R
E, which can get good tradeoff among these metrics. We first redefine task v
i earliest execution finish time on processor p
k at frequency f
k
,
l as(22)
EFT
v
i
,
f
k
,
l
=
EST
v
i
,
f
k
,
l
+
w
i
,
k
,
l
+
RO
v
i
,
f
k
,
l
,where RO
(
v
i
,
f
k
,
l
) is the reliability overhead of task v
i on processor p
k at frequency f
k
,
l and is computed by(23)
RO
v
i
,
f
k
,
l
=
1
-
P
v
i
,
f
k
,
l
×
w
i
,
k
,
l
.On the other hand, we letMin
⁡
F
(
v
i
),   Min
⁡
E
(
v
i
) denote the earliest execution finish time and minimum task energy consumption on all processors of heterogeneous systems. Thus, the novel metric R
E of task v
i on processor p
k at frequency f
k
,
l is(24)
RE
v
i
,
f
k
,
l
=
θ
×
EFT
v
i
,
f
k
,
l
-
Min
⁡
F
v
i
EFT
v
i
,
f
k
,
l
+
1
-
θ
×
EN
v
i
,
f
k
,
l
-
Min
⁡
E
v
i
EN
v
i
,
f
k
,
l
,where θ is the weight of task earliest execution finish time. If the task execution time is more important than energy consumption, we can give higher value to θ; otherwise, θ value is lower. Moreover, the scheduling objective of this problem is minimum in both schedule length and energy consumption. Thus, in each task assignment step, we try to get the minimum R
E
(
v
i
,
f
k
,
l
) and assign task v
i to the corresponding processor frequency.


### 5.3. Slack Reclamation

Tasks of parallel application may have some slack time for their execution due primarily to communication events, for example, “multidimensional” intertask communication (or intertask data dependencies), and these processor slacks are an obvious source of energy wastage. Slack reclamation was studied to reduce energy consumption using the slack left by some completed task instances. The idea behind the slack reclamation for the reducing of energy consumption is to exploit the slack time to slow down the execution speeds of the remaining tasks [12, 20]. In this paper, we adopt this technique to reduce energy consumption after making the scheduling decision. The slack time of task v
i is defined by(25)
Slack
v
i
=
Min
⁡
v
j
∈
succ
v
i
⁡
Sch
v
j
,
s
T
-
Sch
v
i
,
f
T
if
v
i
,
v
j
on  same  processor
Sch
v
j
,
s
T
-
d
i
,
j
-
Sch
v
i
,
f
T
otherwise
,where Sch
(
v
i
,
s
T
) is the task v
i earliest start time in scheduling processor-frequency pairs and Sch
(
v
i
,
f
T
) is the earliest finish time.If task slack timeSlack
(
v
i
)
>
0, we can scale down the execution frequency to save energy consumption. Thus, the optimal frequency f
k
,
l is satisfied with(26)
w
i
,
k
,
l
+
RO
v
i
,
f
k
,
l
<
Sch
v
i
,
f
T
+
Slack
v
i
,
EN
v
i
,
f
k
,
l
<
EN
v
i
,
f
k
,
orig
,where f
k
,
orig is the original scheduling processor-frequency pairs. At last step, we reassign task v
i to the optimal frequency f
k
,
l.


## 5.1. Task Priorities Phase

This step is essential for list scheduling algorithms. A task processing list is generated by sorting the task by decreasing order of some predefined rank function, such ast
_
level, b
_
level, Rank, CP, and DL [5, 6, 8–10, 29]. Here, we use the average computation capacity, which is defined as(18)
w
v
i
¯
=
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
w
i
,
k
,
l
∑
1
≤
k
≤
m
M
k
.In this research, we useb
_
level as the rank function. The b
_
level of task v
i is the sum of the path weight from task v
i to exit task. We can compute this value recursively traversing DAG from exit task, and it is defined as follows:(19)
b
_level
v
i
=
w
v
i
¯
+
Max
⁡
v
j
∈
succ
v
i
⁡
d
i
,
j
+
b
_level
v
j
+
RC
v
i
,where succ
(
v
i
) is the set of immediate successors of task v
i. RC
(
v
i
) is the average reliability overhead of task v
i and can be computed by(20)
RC
v
i
=
1
-
exp
⁡
-
∑
1
≤
k
≤
m
1
≤
l
≤
M
k
λ
k
f
k
,
l
∑
1
≤
k
≤
m
M
k
×
w
v
i
¯
×
w
v
i
¯
.For the exit taskv
exit, the b
_
level is equal to(21)
b
_
level
v
exit
=
w
v
exit
¯
+
RC
v
exit
.Basically,b
_
level
(
v
i
) is the length of the critical path from task v
i to the exit task, including the average computation cost and reliability overhead of task v
i. For example, considering the application DAG in Figure 1(b), heterogeneous systems parameters in Table 1, task execution time matrix in Table 2, and communication matrix in Table 3, the task b
_
level value which is recursively computed by (19) and (21) is shown in Table 4.Table 4
Theb_level value of task.
Task
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
b_level
73.4
61.4
42.4
26
34.15
16.6
13.7
3.8
Seq
1
2
3
5
4
6
7
8


## 5.2. Task Assignment Phase

In this phase, tasks are assigned to the processors with earliest execution finish timeEFT
(
v
i
), high reliability, and minimum task energy consumption EN
(
v
i
). However, for heterogeneous systems, these performance metrics are conflicted most of the time. Here, we introduce a novel objective as R
E, which can get good tradeoff among these metrics. We first redefine task v
i earliest execution finish time on processor p
k at frequency f
k
,
l as(22)
EFT
v
i
,
f
k
,
l
=
EST
v
i
,
f
k
,
l
+
w
i
,
k
,
l
+
RO
v
i
,
f
k
,
l
,where RO
(
v
i
,
f
k
,
l
) is the reliability overhead of task v
i on processor p
k at frequency f
k
,
l and is computed by(23)
RO
v
i
,
f
k
,
l
=
1
-
P
v
i
,
f
k
,
l
×
w
i
,
k
,
l
.On the other hand, we letMin
⁡
F
(
v
i
),   Min
⁡
E
(
v
i
) denote the earliest execution finish time and minimum task energy consumption on all processors of heterogeneous systems. Thus, the novel metric R
E of task v
i on processor p
k at frequency f
k
,
l is(24)
RE
v
i
,
f
k
,
l
=
θ
×
EFT
v
i
,
f
k
,
l
-
Min
⁡
F
v
i
EFT
v
i
,
f
k
,
l
+
1
-
θ
×
EN
v
i
,
f
k
,
l
-
Min
⁡
E
v
i
EN
v
i
,
f
k
,
l
,where θ is the weight of task earliest execution finish time. If the task execution time is more important than energy consumption, we can give higher value to θ; otherwise, θ value is lower. Moreover, the scheduling objective of this problem is minimum in both schedule length and energy consumption. Thus, in each task assignment step, we try to get the minimum R
E
(
v
i
,
f
k
,
l
) and assign task v
i to the corresponding processor frequency.


## 5.3. Slack Reclamation

Tasks of parallel application may have some slack time for their execution due primarily to communication events, for example, “multidimensional” intertask communication (or intertask data dependencies), and these processor slacks are an obvious source of energy wastage. Slack reclamation was studied to reduce energy consumption using the slack left by some completed task instances. The idea behind the slack reclamation for the reducing of energy consumption is to exploit the slack time to slow down the execution speeds of the remaining tasks [12, 20]. In this paper, we adopt this technique to reduce energy consumption after making the scheduling decision. The slack time of task v
i is defined by(25)
Slack
v
i
=
Min
⁡
v
j
∈
succ
v
i
⁡
Sch
v
j
,
s
T
-
Sch
v
i
,
f
T
if
v
i
,
v
j
on  same  processor
Sch
v
j
,
s
T
-
d
i
,
j
-
Sch
v
i
,
f
T
otherwise
,where Sch
(
v
i
,
s
T
) is the task v
i earliest start time in scheduling processor-frequency pairs and Sch
(
v
i
,
f
T
) is the earliest finish time.If task slack timeSlack
(
v
i
)
>
0, we can scale down the execution frequency to save energy consumption. Thus, the optimal frequency f
k
,
l is satisfied with(26)
w
i
,
k
,
l
+
RO
v
i
,
f
k
,
l
<
Sch
v
i
,
f
T
+
Slack
v
i
,
EN
v
i
,
f
k
,
l
<
EN
v
i
,
f
k
,
orig
,where f
k
,
orig is the original scheduling processor-frequency pairs. At last step, we reassign task v
i to the optimal frequency f
k
,
l.


## 6. Experimental Results and Discussion

In this section, we compare the performance, energy consumption, and system reliability using our REAS algorithm with three existing scheduling algorithms: DLS [6], RDLS [27], and ECS [20]. The experiments are performed on the synthetic randomly generated precedence-constrained parallel application graphs as described below. The performance metrics chosen for the comparison are the schedule length (2) and (22), systems energy consumption EN
(
P
) (7), and application reliability P
[
G
] (16).To test the performance of these algorithms, we have developed a discrete event simulation environment of heterogeneous systems with8 DVFS-enabled processors using C++. This simulator includes 2 Intel® Core™ Duo, 2 Intel Xeon, 2 AMD Athlon, 1 TI DSP, and 1 Tesla GPU, mostly based on Intel processor. The systems are interconnected by Infiniband, which is a switched fabric communications link primarily used in high-performance computing. For the Infiniband configuration, the switch considered is Mellanox InfiniScaleTM III SDR and NIC is Mellanox ConnectXTM IB Dual Copper Card [21]. Other parameters of the model are set as follows. The failure rates of processors are assumed to be uniformly distributed between 1
×
1
0
-
4 and 1
×
1
0
-
5 failures/hr [8, 9, 28]; the transmission rates of links are assumed to be 1000 Mbits/sec.


### 6.1. Randomly Generated Application Graphs

These experiments use three commonly DAG characteristics to generate parallel application graphs [5, 8, 9, 29]:(i)
DAG Size (
v
). It is the number of tasks in the application DAG.
(ii)
Communication-Computation Ratio (CCR). It is the ratio of communication time to computation time. A small CCR value means the application is computation-intensive; a large CCR value indicates that the application is communication-intensive [5, 8–10, 29].
(iii)
Out-Degree. It is out-degree of a task node.In experiments setting, DAG are generated based on the above parameters with the number of tasks50 and 100. Task weights are generated randomly from uniform distribution [1
×
1
0
9
,
9
×
1
0
11] execution cycles to be around 4.5
×
1
0
10; thus the average task execution cycles are 4.5
×
1
0
10. We also generated edge weights with a uniform distribution based on a mean CCR. Different objective parallel applications can be produced as giving various CCR values [5, 8–10, 29]. In these experiments, we varied CCR in a reasonable range of 0.1 to 10.


### 6.2. Various Weightθ of REAS Algorithm

In the first experiments, we evaluate the performance of weightθ to REAS algorithm. Figure 2 shows the simulation results of scheduling 50 and 100 tasks with CCR = 1 by varying weight θ from 0 to 1, in steps of 0.2. We observe from Figure 2 that the schedule length and energy consumption decrease and the application reliability almost at the same level as the REAS algorithm weight θ increases. It is reasonable that the REAS algorithm with high θ is mostly based on task execution time and makes its schedule length shorter and consumes less energy. However, as the weight θ over 0.4, the performance of REAS is not much distinguishable. Thus, in the below experiments, we let θ
=
0.5.Figure 2
The experimental results of REAS algorithm with various weightsθ. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)


### 6.3. Random Task Performance Results

For the set of randomly generated parallel applications, the results are shown in Figures3 and 4, where each data point is the average of the data obtained in 1,000 experiments. In this set of experiments, we assume the weight θ
=
0.5 of metric R
E (see (24)) in REAS algorithm. In other word, the REAS algorithm has the same weight on task execution time and energy consumption. In the next section, we will examine the performance by various weights θ.Figure 3
The experimental results. (a)50-task schedule length. (b) 50-task energy consumption. (c) 50-task application reliability. (d) 100-task schedule length. (e) 100-task energy consumption. (f) 100-task application reliability.
(a)
(b)
(c)
(d)
(e)
(f)Figure 4
The experimental results of100 tasks for 4 Intel Xeon and 4 AMD Athlon. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)We observe from Figure3(a) that REAS is over RDLS and ECS with respect to schedule length, and the schedule length increases as the CCR increases. The average schedule length of the REAS algorithm is shorter than that of the RDLS and ECS by 2.6
% and 1.9
%, respectively. This improvement becomes more obvious as CCR increases, for CCR = 5 and REAS over RDLS and ECS by 7.5
% and 2.6
%, respectively. However, the REAS is inferior to DLS in terms of schedule length. Figure 3(b) reveals that REAS saves more average energy consumption than RDLS by 15.3
%, ECS by 3.7
%, and DLS by 16
%, respectively. Figure 3(c) shows that REAS outperforms RDLS, ECS, and DLS by 0.3
%, 2
%, and 0.7
% in terms of the average application reliability.This is mainly due to the fact that REAS algorithm schedules tasks according to the novel objectiveR
E, which can get effective tradeoff among task execution time, energy consumption, and task execution reliability. However, DLS algorithm only focuses on optimizing the task execution time and its actual execution time including the task scheduling time and reliability overhead. Thus, the scheduling solution generated by DLS can get optimal schedule length. However, it consumes more energy and has lower reliability. RDLS algorithm schedules tasks considering their execution reliability and ignoring task energy consumption. ECS algorithm is a solution for optimizing both schedule length and energy consumption, but this solution needs more task execution reliability overhead. Thus, REAS algorithm outperforms RDLS, ECS, and DLS in terms of the schedule length, energy consumption, and reliability. Other interesting experimental phenomena are that RDLS and DLS are better than ECS in terms of reliability. This is mainly due to the fact that tasks of solutions RDLS and DLS are always executing on the normal frequency of processor, which has the high reliability in all processor frequency.The improvements of scheduling performance also could be concluded from Figures3(d), 3(e), and 3(f) for 100 tasks. These results also show REAS over RDLS and ECS by 4.9
% and 3.5
% in terms of the average schedule length. And, REAS is also over RDLS, ECS, and DLS by 8.93
%, 4.53
%, and 8.24
% in terms of the average energy consumption and by 1.86
%, 6.28
%, and 2.1
% in terms of the average application reliability, respectively.We also simulate heterogeneous systems with4 Intel Xeon and 4 AMD Athlon; the other configurations are the same as before. Figure 4 shows the results of 100 randomly generated tasks on this heterogeneous computing platform. The results show REAS over RDLS, ECS, and DLS in terms of average schedule length and energy consumption. However, REAS is inferior to RDLS in terms of the application reliability.


### 6.4. Application Graphs of Real-World Problem

Using real applications to test the performance of algorithms is very common [5, 8–10, 29]. In this section, we also simulate a real-world digital signal processing (DSP) problem, and the detail can be seen in [5, 8–10, 29]. From Figure 5, we can conclude that REAS is also better than RDLS, ECS, and DLS.Figure 5
The experimental results of real-world DSP problem. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)


## 6.1. Randomly Generated Application Graphs

These experiments use three commonly DAG characteristics to generate parallel application graphs [5, 8, 9, 29]:(i)
DAG Size (
v
). It is the number of tasks in the application DAG.
(ii)
Communication-Computation Ratio (CCR). It is the ratio of communication time to computation time. A small CCR value means the application is computation-intensive; a large CCR value indicates that the application is communication-intensive [5, 8–10, 29].
(iii)
Out-Degree. It is out-degree of a task node.In experiments setting, DAG are generated based on the above parameters with the number of tasks50 and 100. Task weights are generated randomly from uniform distribution [1
×
1
0
9
,
9
×
1
0
11] execution cycles to be around 4.5
×
1
0
10; thus the average task execution cycles are 4.5
×
1
0
10. We also generated edge weights with a uniform distribution based on a mean CCR. Different objective parallel applications can be produced as giving various CCR values [5, 8–10, 29]. In these experiments, we varied CCR in a reasonable range of 0.1 to 10.


## 6.2. Various Weightθ of REAS Algorithm

In the first experiments, we evaluate the performance of weightθ to REAS algorithm. Figure 2 shows the simulation results of scheduling 50 and 100 tasks with CCR = 1 by varying weight θ from 0 to 1, in steps of 0.2. We observe from Figure 2 that the schedule length and energy consumption decrease and the application reliability almost at the same level as the REAS algorithm weight θ increases. It is reasonable that the REAS algorithm with high θ is mostly based on task execution time and makes its schedule length shorter and consumes less energy. However, as the weight θ over 0.4, the performance of REAS is not much distinguishable. Thus, in the below experiments, we let θ
=
0.5.Figure 2
The experimental results of REAS algorithm with various weightsθ. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)


## 6.3. Random Task Performance Results

For the set of randomly generated parallel applications, the results are shown in Figures3 and 4, where each data point is the average of the data obtained in 1,000 experiments. In this set of experiments, we assume the weight θ
=
0.5 of metric R
E (see (24)) in REAS algorithm. In other word, the REAS algorithm has the same weight on task execution time and energy consumption. In the next section, we will examine the performance by various weights θ.Figure 3
The experimental results. (a)50-task schedule length. (b) 50-task energy consumption. (c) 50-task application reliability. (d) 100-task schedule length. (e) 100-task energy consumption. (f) 100-task application reliability.
(a)
(b)
(c)
(d)
(e)
(f)Figure 4
The experimental results of100 tasks for 4 Intel Xeon and 4 AMD Athlon. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)We observe from Figure3(a) that REAS is over RDLS and ECS with respect to schedule length, and the schedule length increases as the CCR increases. The average schedule length of the REAS algorithm is shorter than that of the RDLS and ECS by 2.6
% and 1.9
%, respectively. This improvement becomes more obvious as CCR increases, for CCR = 5 and REAS over RDLS and ECS by 7.5
% and 2.6
%, respectively. However, the REAS is inferior to DLS in terms of schedule length. Figure 3(b) reveals that REAS saves more average energy consumption than RDLS by 15.3
%, ECS by 3.7
%, and DLS by 16
%, respectively. Figure 3(c) shows that REAS outperforms RDLS, ECS, and DLS by 0.3
%, 2
%, and 0.7
% in terms of the average application reliability.This is mainly due to the fact that REAS algorithm schedules tasks according to the novel objectiveR
E, which can get effective tradeoff among task execution time, energy consumption, and task execution reliability. However, DLS algorithm only focuses on optimizing the task execution time and its actual execution time including the task scheduling time and reliability overhead. Thus, the scheduling solution generated by DLS can get optimal schedule length. However, it consumes more energy and has lower reliability. RDLS algorithm schedules tasks considering their execution reliability and ignoring task energy consumption. ECS algorithm is a solution for optimizing both schedule length and energy consumption, but this solution needs more task execution reliability overhead. Thus, REAS algorithm outperforms RDLS, ECS, and DLS in terms of the schedule length, energy consumption, and reliability. Other interesting experimental phenomena are that RDLS and DLS are better than ECS in terms of reliability. This is mainly due to the fact that tasks of solutions RDLS and DLS are always executing on the normal frequency of processor, which has the high reliability in all processor frequency.The improvements of scheduling performance also could be concluded from Figures3(d), 3(e), and 3(f) for 100 tasks. These results also show REAS over RDLS and ECS by 4.9
% and 3.5
% in terms of the average schedule length. And, REAS is also over RDLS, ECS, and DLS by 8.93
%, 4.53
%, and 8.24
% in terms of the average energy consumption and by 1.86
%, 6.28
%, and 2.1
% in terms of the average application reliability, respectively.We also simulate heterogeneous systems with4 Intel Xeon and 4 AMD Athlon; the other configurations are the same as before. Figure 4 shows the results of 100 randomly generated tasks on this heterogeneous computing platform. The results show REAS over RDLS, ECS, and DLS in terms of average schedule length and energy consumption. However, REAS is inferior to RDLS in terms of the application reliability.


## 6.4. Application Graphs of Real-World Problem

Using real applications to test the performance of algorithms is very common [5, 8–10, 29]. In this section, we also simulate a real-world digital signal processing (DSP) problem, and the detail can be seen in [5, 8–10, 29]. From Figure 5, we can conclude that REAS is also better than RDLS, ECS, and DLS.Figure 5
The experimental results of real-world DSP problem. (a) Schedule length. (b) Energy consumption. (c) Application reliability.
(a)
(b)
(c)


## 7. Conclusions and Future Work

In the past few years, with the rapid development of heterogeneous systems, the high price of energy, system performance, reliability, and various environmental issues have forced the high-performance computing sector to reconsider some of its old practices with an aim to create more sustainable system. In this paper, we attempt the simultaneous management of system performance, reliability, and energy consumption. To achieve this goal, we first built a reliability and energy aware task scheduling architecture, which mainly includes heterogeneous systems, parallel application DAG model, and energy consumption model. Then, we proposed a relationship between execution reliability and processor’s voltage/frequency and deduced its parameters approximation value by least squares curve fitting method. Thirdly, we established parallel application execution reliability model and formulated this reliability and energy aware scheduling problem as a linear programming. Finally, to provide an optimum solution for this problem, we proposed a heuristic Reliability-Energy Aware Scheduling (REAS) algorithm based on a novel scheduling objective RE, which is synthetic considering the task execution time, energy consumption, and reliability.The performance of REAS algorithm is evaluated with an extensive set of simulations and compared to three of the best existing scheduling algorithms for heterogeneous systems: the RDLS, ECS, and DLS algorithms. The comparison is also performed on the synthetic randomly generated precedence-constrained parallel application DAG. The simulation experiment results clearly confirm the superior performance of REAS algorithm over the other three, particularly in energy saving.This work is one of the first attempts to consider the simultaneous management of system performance, reliability, and energy consumption on high-performance computing systems. Future studies in this domain are twofold. Firstly, it will be interesting to extend our model to multidimensional computing resources, such as interconnections, memory access, and I/O activities. Secondly, in this paper, the failures occurring on resources of systems are assumed to follow Poisson process. Other reliability models can also be used in further studies.



---

*Source: 9823213-2016-03-17.xml*