ISAECC: An Improved Scheduling Approach for Energy Consumption Constrained
Parallel Applications on Heterogeneous Distributed Systems
Ting Ye
†
, Zhi-Jie Wang
‡,#
, Zhe Quan
†∗
, Song Guo
⊥
, Kenli Li
†
, and Keqin Li
§
†
College of Information Science and Engineering, Hunan University, Changsha, China
‡
School of Data and Computer Science, Sun Yat-sen University, Guangzhou, China
#
Guangdong Key Laboratory of Big Data Analysis and Processing, Guangzhou, China
⊥
Department of Computing, Hong Kong Polytechnic University, Kowloon, Hong Kong
§
Department of Computer Science, State University of New York, United States
ytcaro@hnu.edu.cn, wangzhij5@mail.sysu.edu.cn, quanzhe@gmail.com,
song.guo@polyu.edu.hk, lkl510@263.net, lik@newpaltz.edu
Abstract—Power-aware task scheduling on processors has
been a hot topic. In this paper, we study the problem
of minimizing the schedule length for energy consumption
constrained parallel applications on heterogeneous distributed
systems. Previous work (solving this problem) adopts a policy
that preassigns the minimum energy consumption for each
unassigned task. Nevertheless, our analysis reveals that such a
preassignment policy could be unfair, and it may not achieve
an optimistic schedule length. Motivated by this, we propose
a new task scheduling algorithm that suggests a weight-based
mechanism to preassign energy consumption for unassigned
tasks. We theoretically prove that our preassignment mecha-
nism can guarantee the energy consumption constraint. Also,
we have conducted extensive experiments based on two real
parallel applications. The results consistently demonstrate that,
compared to state-of-the-art algorithms, our approach can
achieve smaller schedule length while satisfying the energy
consumption constraint.
Keywords-Distributed system, energy consumption, parallel
application, task scheduling, preassignment strategy
I. INTRODUCTION
Computers have been developed to achieve higher per-
formance over the past seven decades. While the perfor-
mance has increased dramatically, power consumption in
computer systems has also increased [1, 2]. Such increased
energy consumption causes severe economic, ecological, and
technical problems [2]. Power conservation is critical in
many computation and communication environments and
has attracted much attention [1–6].
Generally, there are two kinds of approaches to reduce
power consumption in computing systems [2]: (i) using the
thermal-aware hardware design; and (ii) using the power-
aware software design. As for the latter, there is a well-
known mechanism called dynamic voltage and frequency
scaling (DVFS), which dynamically tunes the energy-delay
tradeoff [3, 7]. Owning to this mechanism, power-aware
task scheduling on processors with variable voltages and
frequencies has been extensively studied [3, 8–11]. There
are two main considerations in dealing with the energy-delay
tradeoff: (i) in high performance computing systems, tech-
niques and algorithms usually aim to maximize performance
under certain energy consumption constraints; and (ii) in
low-power devices and systems, techniques and algorithms
usually aim to minimize energy consumption while still
meeting certain performance goals. These two lines of works
can be witnessed in [12–15].
Recently, the problem of minimizing schedule length of
an energy consumption constrained application with prece-
dence constrained sequential tasks was studied in [2] by Li.
Later, the author extended this problem to the context of
constrained parallel tasks [16]. These works were interested
in homogeneous systems with shared memory and they
cannot be applied to heterogeneous distributed systems.
Different from the above works, Xiao et al. [17] studied
a variant problem that aims to minimize schedule length of
an energy consumption constrained parallel application on
heterogeneous distributed systems. To solve this problem,
they developed an algorithm called MSLECC. The basic
idea of their method is to preassign the minimum energy
consumption for each unassigned task to satisfy the energy
consumption constraint, and then minimize the schedule
length in a heuristic manner. With this idea, their algorithm
achieves favourable performance. Nevertheless, we observe
that, for the low priority tasks, the preassignment policy
in MSLECC could be not fair, which may lead to less
optimistic results. To address this issue, this paper develops
a new approach that achieves a better performance.
The main contributions of this paper are as follows.
• We design a preassignment strategy that adopts a
weight-based mechanism (Section III-A), and provide
the rigorous proof to show its feasibility (Section III-B).
• We develop a new task scheduling algorithm to mini-
mize the schedule length while considering the energy
consumption constraint (Section III-C).
• We evaluate our approach and the experimental results
show that it can achieve much shorter schedule length
while satisfying the energy consumption constraint
(Section IV).
267
2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS)
978-1-5386-7308-9/18/$31.00 ©2018 IEEE
DOI 10.1109/ICPADS.2018.00044