Adaptive Weight-Based Energy-Efficient Scheduling Algorithm for heterogeneous
computing systems
Cheng Xu, Pan Shu, Tao Li, Yan Liu
College of Information Science and Engineering
Hunan University
Changsha, China
supermanpanshu@gmail.com
Abstract—Energy-saving scheduling algorithm for parallel
applications on heterogeneous computing systems has become
an important research subject. Considering that the existing
energy-efficient scheduling algorithms have strong locality and
cannot flexibly adapt to the application performance
(makespan /schedule length) requirements, the authors
designed a weighted objective function, based on which an
adaptive weight-based energy-efficient scheduling algorithm
has been proposed with dynamic voltage scaling (DVS). It can
effectively balance performance and power consumption by
controlling the weight. The algorithm consists of two parts: (1)
automatically calculate the optimum weight, thus consume less
energy while guaranteeing makespan requirement; (2) use
objective function to get the approximately optimal task
allocation on the DVS-enabled processors through the idea of
list scheduling algorithm. Compared to the other three existing
task scheduling algorithms, the experimental results show that
the new algorithm can much effectively balance schedule
lengths and energy consumption.
Keywords-heterogeneous computing system; dynamic voltage
scaling (DVS); energy-efficient scheduling; green computing
I. INTRODUCTION
Over the years, heterogeneous computing systems have
been widely used for compute-intensive and data-intensive
applications. Notably, the energy consumption of
heterogeneous computing systems is huge. According to the
current study [1], the power consumption by computing
centers accounted for about 0.5% of the world's total
electricity consumption. The study also indicates that
electricity consumption is expected to double by 2020.
Clearly, there are environment issues with the generation of
electricity [2]. Therefore, green energy has become one of
the important factors that must be considered in high-
performance computing.
Due to the importance of energy consumption, various
techniques have been investigated and developed [3]. DVS
(dynamic voltage scaling) among these has been proven to
be a very promising technique with its demonstrated
capability for energy savings (e.g., [4], [5], and [6]). DVS
enables processors to dynamically adjust voltage supply
levels aiming to reduce power consumption; however, this
reduction is achieved at the expense of sacrificing clock
frequencies.
Traditionally, the primary performance goal of
heterogeneous computer systems has focused on reducing
the execution time of applications. List scheduling algorithm
[7] is a well-known algorithm for this performance goal, and
has been studied separately with DVS. For reducing
makespan the conventional list scheduling ignores that high-
frequency and high voltage lead to high energy consumption.
Although some algorithms by proposing a novel target
function combined list scheduling algorithm and DVS to
reduce the energy consumption [8], but these objective
functions of scheduling algorithms does not consider the
impact of a task completion time on the total energy
consumption, so they are localized strongly. In addition, they
also cannot be automatically adjusted according to the
application performance requirement.
By analyzing the relationship of task completion time
and energy consumption, we found that the energy
consumption can be saved by executing task in lower voltage
which will lead to extend the task completion time, however,
because it can increase idle time, if left unchecked, the total
energy consumption will increase instead. Thus this paper
proposes a weighted objective function and comes up with
an adaptive weight-Based energy-efficient scheduling
algorithm (AWES). It combines list scheduling algorithm
and DVS. AWES is essentially different from the existing
scheduling algorithms. Firstly, with the relationship between
task completion time and total energy consumption a novel
target function with weight is proposed; secondly the optimal
weight can be automatically calculated based on the
performance requirements; finally, we can reduce energy
consumption on the premise that makespan requirements can
be met.
II. RELATED WORK
Due to the NP-hard nature of the task scheduling problem
[9], heuristics are the most popular scheduling model
adopted by many researchers. And for low complexity and
high effect, the HEFT which is a well-known list-scheduling
heuristic is widely used [7]. However, it ignores the energy
problem. To solve this problem, LEE in [8] presented ECS
and ECS+idle scheduling algorithm. The performance of
these algorithms is very compelling in terms of both
application completion time and energy consumption. But
there are still lots of space for improvement.
International Conference on Computer Science and Service System (CSSS 2014)
© 2014. The authors - Published by Atlantis Press