Energy-aware clustering scheduling of parallel applications on heterogeneous computing systems

Abstract

Energy saving in multiprocessor system is emerging as a primary issue in recent years. Mostly the work available has stressed on reducing makespan of application and little attention has been paid to energy management. In this paper, a novel dynamic power management based clustering task scheduling algorithm is proposed for heterogeneous computing platforms. The prime objective of this paper is to reduce the dynamic and static power consumption of the processors. This paper couples clustering scheduling heuristics with dynamic power management technique to reduce energy consumption. The simulation based results of the proposed energy-aware clustering task scheduling algorithm with dynamic power management are analysed and compare with well-known list based heterogeneous earliest finish time (HEFT) and list based energy-aware precedence-constrained tasks algorithm (PASTA) algorithm. The result carried out for an extensive set of random and real world graphs demonstrate the potency of the proposed algorithm.

Keywords

Energy management clustering task scheduling heterogeneous computing systems directed acyclic graphs static power consumption dynamic power management

1. Introduction

Multiprocessor platform is composed of two or more central processing units (CPUs) that execute tasks of parallel application with high performance and low computation cost. The significant turnover in list of most powerful supercomputers by Top500 from previous lists imparted the necessity of such high computation system these days [1]. However, this architecture has its own challenges such as load balancing, resource utilization, intercommunication of processor, and process synchronization. These challenges can be dealt with help of judicious scheduling algorithms. In recent years, power management of such systems has also become a concern issue for research fraternity. This revolution is result of the rapid increase of number of users of computer, laptops, and mobile phones day by day. On the motherboard of portable devices, processors are found to be the most energy consuming component following the memory units and other components [2]. Adequate energy saving in these computing infrastructures benefit many monetary and environmental aspects such as less electricity consumption, heat dissipation, maintenance cost, greenhouse emission, and more reliability. Several power management techniques are suggested at circuits, architectures, system software, and applications level [3].

Dynamic and static energy are two main sources of energy dissipation in processors. Dynamic energy dissipation occurs due the switching of the transistor at run time. Static energy dissipation occurs due to the continuous flow of current in gates and also when a transistor switches [4]. With the advancement of the technology, chip miniaturization, improved idle states, fast memory cache, and increase in number of transistors, the static energy dissipation has dominated dynamic power dissipation [5]. Hence, it’s important to focus both static as well as dynamic energy consumption while scheduling.

In this paper, a new energy-aware scheduling algorithm is proposed for directed acyclic graph (DAG) for heterogeneous computing platforms that judiciously builds the energy-aware clusters to reduce dynamic energy consumption. Further, the dynamic power management (DPM) techniques are made use of by exploiting three low power states for the available idle slots to reduce static energy consumption. The main contributions of the proposed energy-aware clustering task scheduling algorithm with dynamic power management (CDPM) are as:

(iii) (i)
As clustering scheduling heuristics are helpful in reducing makespan, we focus on reducing energy consumption for such heuristics.
(ii)
We focus on reducing static energy consumption by exploiting DPM with clustering heuristics besides reducing dynamic energy consumption.
(iii)
The different low power states of a processor are considered while utilizing DPM technique along with context switching overheads.
(iv)
The target machine model undertaken is heterogeneous computing system.

The rest of the paper is organized as follows: In Section 2, related work is presented from literature. Section 3 discusses task model, a machine model and an energy consumption model that are adopted in this paper. Next Section 4 presents proposed task scheduling strategy. Simulation platform and results for random and regular graph suites are stated in Section 5. Finally, Section 6 presents the conclusions.
2. Literature review

DAG scheduling is to map tasks onto machines and order their execution such that task precedence requirements are satisfied with minimum makespan. In general, the scheduling can be performed in two ways: online scheduling and offline scheduling. Former is performed at run time where the behavior of the task may or may not be known. In the latter, scheduling is performed at compile time, knowing the behavior of upcoming tasks thus creates better schedules with lesser scheduling overhead than the former one. Task scheduling problem is NP-complete [7, 13] and many heuristics based scheduling algorithms list, cluster, and duplication are given in literature [23, 24]. The idea of list based algorithms is to assign rank to the tasks and then map them to the processors. Cluster based algorithms involve grouping of tasks in clusters such that intercommunication among processors is minimized. Duplication based algorithms duplicate the predecessor of a task on many processor to get shorter makespan, thereby eliminating unnecessary communication delay among processors.

Dynamic voltage and frequency scaling (DVFS) and dynamic power management (DPM) are two basic techniques used for energy management. DVFS enables the processor to run at different speeds by scaling the voltage and frequency level. The energy consumed by the processor is directly proportional to the speed of the processor. Hence, more the processor run at low speed less will be the energy consumed [3]. The challenge in this technique is to calculate the adequate voltage at which a task is to execute. If for a certain slack time, a task is executed at lower voltage it may finishes late and can increase makespan [2]. Recently, incorporation of DVFS technique on existing list based [6, 7, 8] and duplication based [9, 10] scheduling heuristics have been targeted for heterogeneous platforms. Some clustering based heuristics also have been suggested to incorporate with DVFS but they focused homogenous platforms [11, 12]. In actual, DVFS technique requires special hardware build with complementary metal-oxide-semiconductor (CMOS) technology that incurs extra cost and scaling the voltage and frequency level has negative impact on reliability of processor [13].

Another DPM technique dynamically reconfigures an electronic system to reduce the number of active components and reduces static energy consumption. For example, in laptops a timeout policy turns off some components after a fixed inactivity to save the energy. However, state transition from active to idle, accompany some time units to turn off. To retain the active state from an idle state some energy and time penalty is involved and is called context switching overhead in this paper. The challenge lying here is that a processor cannot be turned off for all the idle periods because this penalty will have to be considered for every idle to active transition of the processor. For instance, Ma et al. focused clustering and duplication heuristics to schedule tasks on homogenous platforms and used time threshold for idle periods to deploy DPM technique [14].

In above works, the scheduling algorithms that were originally designed to reduce makespan are incorporated with DVFS and DPM techniques further to make them energy efficient. On other hand, Mei et al. focused to design duplication based energy-aware algorithms that duplicates the task on basis of both time and energy parameters [15]. Kaur et al. also proposed duplication controlled energy efficient scheduling and further deploy DPM technique to reduce static energy consumption [16, 18]. Some researchers have proposed to reduce the number of processor required to finish the tasks which is a good strategy to reduce the total energy consumption [17, 19]. Many researchers have proposed multi-objective scheduling algorithms including energy as one of the objectives [20, 21, 22]. However, these techniques are not suitable for precedence constrained parallel applications.

From the above works, majority the researchers have targeted list and duplication based energy-aware algorithm and cluster based heuristics are less focused. Further, the suggested works have taken homogeneous platform as target machine model. As heterogeneous systems are suitable to execute computation extensive applications, we have considered such platform in this paper. In addition, researchers in past years have focused more to reduce dynamic energy consumption. With chip miniaturization static energy consumption is surpassing dynamic energy consumption and DVFS is becoming less efficient, hence need to be addressed. Therefore, DPM technique with several low power states is considered to reduce static energy consumption besides dynamic energy consumption. Keeping in view the above stated issues, a cluster heuristic based with DPM method is proposed that reduce dynamic as well as static power consumption for heterogeneous computing system (HCS).

3. Models

This section presents the formal description and the unifying notation for processor, task and energy consumption models. Table 1 enlists the notations used in the proposed CDPM algorithm.

Table 1
Notations used in the proposed CDPM algorithm

$V,E,P,C_{n}$	Set of tasks, edges in DAG, set of processors, set of clusters generated
$v_{i},p_{j},idle_{k}$	Task $i$ where $v_{i}\in V$ , processor $j$ where $p_{k}\in P$ and idle time of processor $k$
$\textit{WPD}_{k},\textit{IPD}_{k}$	Working and idle power dissipation of processor $k$
$E_{\textit{total}},E_{\textit{dynamic}},E_{\textit{static}}$	Total, dynamic and static energy consumption
${\textit{BET}}_{s},EC_{s},Pen_{s}$	Break event time, energy consumption, energy penalty at low-power state
$b_{\textit{level}}(v_{i}),w_{i}$	Bottom up level of $v_{i}$ , mean computation of task $v_{i}$
$succ(v_{i}),pred(v_{i})$	Set of successor and predecessor of $v_{i}$
$avail[k],\textit{AFT}(v_{i})$	Available time of processor $k,$ actual finish time of task $v_{i}$
$est(v_{i},p_{j}),ect(v_{i},p_{j})$	Earliest start time and earliest completion time of $v_{i}$ on $p_{j}$
$fp(v_{i}),fpred(v_{i})$	Favourite processor and favourite predecessor of
$fp_{\textit{energy}}(v_{i}),fpred_{\textit{energy}}(v_{i})$	Favourite processor and favourite predecessor of $v_{i}$ in terms of energy
$v_{\textit{score}}(v_{i}),c_{\textit{score}}(p_{k}),e_{\textit{score}}(p_{k})$	Task score of $v_{i}$ , computation, and energy score of $p_{j}$
$E_{\textit{score}}(C_{n},p_{k})$	Energy score of cluster $n$ on energy processor $k$
$E_{\textit{static}}^{\textit{DPM}}$	Static energy consumption with DPM
$t_{\textit{idle}}(v_{i},p_{k})$	Time for which processor $p_{k}$ remain idle after executing task $v_{i}$

3.1 Machine model

The target system has fully connected processors and the communication between the processors is done via message transfer. Let $P=\{p_{k}|p_{k}$ is processor, where $k$ is $1,2,\ldots,k\}$ is processor set. Each processor can perform communication and computation simultaneously where task preemption is not allowed. The system considered is heterogeneous that is each task has different computation time on each processor ${p}_{k}$ .

3.2 Task model

A parallel application is decomposed into subtasks and dependencies among subtasks can be represented in the form of a directed acyclic graph (DAG). To execute the application correctly, the order of execution of tasks should be according to the precedence constraints. A DAG denoted by $G=(V,E,T,C)$ is quadruple. Here, $V=\{v_{i}|v_{i}$ is an ordered task, $i=1,2,3,\ldots,v\}$ is vertex set. $E=\{e_{ij}|e_{ij}$ is edge from $v_{i}$ to $v_{j}\}$ is edge set. $T=\{t(v_{i},p_{k})|t(v_{i},p_{k})$ is computation time of $v_{i}$ , on processor $p_{k}\}$ and $C=\{{c}_{ij}|{c}_{ij}$ is communication time from task $v_{i}$ to $v_{j}$ where, $v_{i}$ is predecessor of $v_{j}\}$ . The $(v_{i})$ denote set of successors of task $v_{i}$ and $(v_{i})$ set of predecessors of task $v_{i}$ . An entry task $v_{\textit{entry}}$ has no predecessors while exit task $v_{\textit{exit}}$ has no successors.

3.3 Energy model

The complementary metal-oxide-semiconductor (CMOS) based processor has two components responsible for its power dissipation (i) dynamic and (ii) idle power dissipation. For $k^{\rm th}$ processor dynamic energy consumed to execute the task $v_{i}$ on $p_{k}$ , denoted as $E_{\textit{dynamic}}(v_{i},p_{k})$ and given by:

$\displaystyle E_{\textit{dynamic}}(v_{i},p_{k})=\textit{WPD}_{k}\times t\left(% v_{i},p_{k}\right)$ (1)

where working power dissipation $(\textit{WPD})$ is due to loading and unloading of the capacitors, gate switching, clock frequency and supplied voltage [3]. Thus total dynamic energy consumed to execute all tasks $V$ on processor $P$ denoted by $E_{\textit{dynamic}}$ is given by:

$\displaystyle E_{\textit{dynamic}}=\sum\limits_{i=1}^{|V|}\sum\limits_{k=1}^{|% P|}E_{\textit{dynamic}}\left(v_{i},p_{k}\right)$ (2)

On other hand, idle energy consumed on processor $p_{k}$ , denoted as $E_{\textit{static}}(idle_{k},p_{k})$ is given by:

$\displaystyle E_{static}(idle_{k},p_{k})=\textit{IPD}_{k}\times idle_{k}$ (3)

where idle power dissipation $(\textit{IPD}_{k})$ of processor $p_{k}$ occurs due to leakage current flowing through transistors even though the transistors are not in use or turned off for idle time $idle_{k}$ [3]. Therefore, the total idle energy consumed on all processors $P$ denoted by $E_{\textit{static}}$ is given by:

$\displaystyle E_{\textit{static}}=\sum\limits_{k=1}^{|P|}{E_{\textit{static}}(% p_{k},idle_{k})}$ (4)

Thus total power dissipation $(E_{\textit{total}})$ is defined as sum of total dynamic $(E_{\textit{dynamic}})$ and total idle $(E_{\textit{static}})$ power dissipation as:

$\displaystyle E_{\textit{total}}=E_{\textit{dynamic}}+E_{\textit{staic}}$ (5)

4. Proposed algorithm

In this paper, an energy-aware clustering task scheduling algorithm with dynamic power management (CDPM) is developed. The framework of proposed CDPM algorithm is depicted in Fig. 1, and it comprises in three phases: (i) tasks clustering phase; (ii) cluster merging phase; (iii) cluster mapping and DPM phase. The three phases are illustrated in the subsequent section using the DAG as shown in Fig. 2.

Figure 1.

Framework for energy-aware clustering scheduling of directed acyclic graph (DAG) applications on heterogeneous computing system (HCS).

4.1 Task clustering phase

This phase generates the initial set of clusters to reduce the communication cost. First, the tasks of parallel application are ranked on the basis of bottom level ${b}_{\textit{level}}(v_{i})$ , which is the length of a longest path from a task $v_{i}$ to exit task $v_{\textit{exit}}$ given as:

$\displaystyle b_{\textit{level}}\left(v_{i}\right)=w_{i}+\mathop{\max}\limits_% {\forall v_{j}\in\textit{succ}(v_{i})}{\left\{b_{\textit{level}}\left(v_{j}% \right)+\overline{c_{ij}}\right\}}$ (6)

where $w_{i}=(\overline{t\left(v_{i},p_{k}\right)})$ is the mean computation of task $v_{i}$ and $\overline{c_{ij}}$ is mean communication cost of edges. Rank is assigned to tasks on decreasing order of $b_{\textit{level}}(v_{i})$ as shown in Table 2.

Table 2

Computation cost on three processors with $b_{\textit{level}}$ and rank of each task

Task( $v_{i}$ )	$t(v_{i},P_{k})$			$b_{\textit{level}}$	Rank
	$p_{1}$	$p_{2}$	$p_{3}$
$v_{1}$	14	16	9	108	10
$v_{2}$	13	19	18	77	7
$v_{3}$	11	13	19	79.99	8
$v_{4}$	13	8	17	80	9
$v_{5}$	12	13	10	69	6
$v_{6}$	13	16	9	63.33	5
$v_{7}$	7	15	11	42.66	3
$v_{8}$	5	11	14	35.66	2
$v_{9}$	18	12	20	44.33	4
$v_{10}$	21	7	16	14.66	1

Then, the earliest start time $est\left(v_{i},p_{k}\right)$ of a task $v_{i}$ on processor is calculated and given as:

$\displaystyle est\left(v_{\textit{entry}},p_{k}\right)=0$ $\displaystyle est\left(v_{i},p_{k}\right)=\max\left\{avail\left[k\right],% \mathop{\max}\limits_{v_{t}\in\textit{pred}(v_{i})}{(\textit{AFT}(v_{t})+c_{ti% }})\right\}$ (7)

where $avail\left[k\right]$ is the earliest time at which processor $p_{k}$ is ready for execution. After a task $v_{i}$ is scheduled on processor ${p}_{k}$ , the earliest completion time $ect\left(v_{i},p_{k}\right)$ is computed as:

$\displaystyle ect\left(v_{i},p_{k}\right)=t\left(v_{i},p_{k}\right)+est\left(v% _{i},p_{k}\right)$ (8)

Next, two parameters: favourite processor and favourite predecessor which are used to generate the initial clusters are calculated. The favourite processor $fp(v_{i})$ of a task $v_{i}$ is the processor that gives minimum completion time is given as:

$\displaystyle fp(v_{i})=\mathop{\min}\limits_{p_{k}\in p}\left\{ect\left(v_{i}% ,p_{k}\right)\right\}$ (9)

The favourite predecessor $fpred\left(v_{i}\right)$ of task $v_{i}$ is that predecessor which gives maximum value of earliest completion time as below:

$\displaystyle fpred\left(v_{i}\right)=\mathop{\max}\limits_{v_{t}\in\textit{% pred}(v_{i})}\left\{ect\left(v_{i},p_{k}\right)\right\}$ (10)

Table 3 shows the calculated values of $ect\left(v_{i},p_{k}\right),fp\left(v_{i}\right)$ and $fpred\left(v_{i}\right)$ . To generate the initial clusters, tasks are iterated in ascending order of rank. For instance say, if task $v_{i}$ is favourite predecessor of any task say $v_{s}$ then the cluster assign to task $v_{i}$ is same as the cluster assign to task $v_{s}$ . For example, the task $v_{9}$ is favourite predecessor of task ${v}_{10}$ . Thereby, task $v_{9}$ is assigned to the cluster same as assign to task $v_{10}$ which is $C_{2}$ . On other hand, if $v_{i}$ is not a favourite predecessor of any task then assign $v_{i}$ to cluster as per its favourite processor. For example, task $v_{10}$ is not favourite predecessor of any task. Thereby, this task is assigned to the cluster as per its favourite processor which is $p_{2}$ . After iterating all the tasks, group the tasks in set of clusters which are assigned to same cluster. So, the three cluster generated in this manner are $C_{1}=\left(v_{3},v_{5},v_{7}\right),C_{2}=\left(v_{1},v_{2},v_{4},v_{9},v_{10% }\right)$ and $C_{3}=\left(v_{6},v_{8}\right)$ . Then the formed clusters are sorted on the basis of increasing order of their size for the next phase. Hence, sorted clusters become $[C_{2},C_{1},C_{3}]$ .

Table 3

Values of different parameters for cluster generation

Task( $v_{i}$ )	$ect(v_{i},P_{k})$			$fp(v_{i})$	fpred( $v_{i}$ )	$C_{n}$
	$p_{1}$	$p_{2}$	$p_{3}$
$v_{1}$	14	16	9	$p_{3}$	–	$C_{2}$
$v_{2}$	40	46	46	$p_{1}$	$v_{1}$	$C_{2}$
$v_{3}$	32	39	28	$p_{3}$	$v_{1}$	$C_{1}$
$v_{4}$	31	26	26	$p_{2}$	$v_{1}$	$C_{2}$
$v_{5}$	52	39	38	$p_{3}$	$v_{1}$	$C_{1}$
$v_{6}$	53	42	47	$p_{2}$	$v_{1}$	$C_{3}$
$v_{7}$	58	83	49	$p_{3}$	$v_{3}$	$C_{1}$
$v_{8}$	62	79	73	$p_{1}$	$v_{6}$	$C_{3}$
$v_{9}$	69	68	76	$p_{2}$	$v_{2}$	$C_{2}$
$v_{10}$	102	80	97	$p_{2}$	$v_{9}$	$C_{2}$

Figure 2.

A sample application represented as a task graph [23].

4.2 Cluster merging phase

This phase attempts to reduce dynamic energy by reducing the number of processors and number of initial clusters to be used in scheduling. Number of processors to be reduced is based on the maximum parallelism of the task graph using the method described in precedence-constrained tasks algorithm (PASTA) [17] and comes out to be 5 for given DAG.

In proposed CDPM algorithm, processor reduction is performed to reduce number of clusters generated in phase 1. For this, two parameters namely computation score $c_{\textit{score}}\left(p_{k}\right)$ and energy score $e_{\textit{score}}\left(p_{k}\right)$ are devised that find the set of processors that balances the trade-off of energy consumption and makespan.

$\displaystyle c_{\textit{score}}\left(p_{k}\right)=\frac{\sum\nolimits_{v_{i}% \epsilon V}{t\left(v_{i},p_{k}\right)}}{\left|V\right|}$ (11) $\displaystyle e_{\textit{score}}\left(p_{k}\right)=c_{\textit{score}}\left(p_{% k}\right)\times\textit{WPD}_{k}$ (12)

Next, processors are arranged in ascending order of $e_{\textit{score}}\left(p_{k}\right)$ that come to be $[p_{2},p_{1},p_{3}]$ . In case, if number of processors is more than the maximum parallelism then subset equal to maximum parallelism from the head of sorted set of processors is selected. Here in our example, the number of processors is 3 that is less than the maximum parallelism. So, all the three processor $[p_{2},p_{1},p_{3}]$ are selected on which the clusters will be allocated in next phase.

Table 4

Calculated values of $c_{\textit{score}}$ and $e_{\textit{score}}$ the three processors

Processor	$c_{\textit{score}}\left(p_{k}\right)$	$e_{\textit{score}}\left(p_{k}\right)$
$p_{1}$	12.7	330.2
$p_{2}$	13	182
$p_{3}$	14.3	1573

The number of initial cluster obtained in phase 1 and number of processor selected in this phase could be different. In case, the number of initial clusters obtained and the reduced number of processors is less or equal then cluster merging is not required. On other hand, when number of initial clusters is greater than the reduced number of processors, then the extra clusters occurring at the end of the sorted set of initial cluster are required to be merged. Further, the two modified parameters $fp_{\textit{energy}}\left(v_{i}\right)$ and $fpred_{\textit{energy}}\left(v_{i}\right)$ which keep an eye on the energy consumption along with makespan while merging the tasks of the extra cluster are introduced. Another parameter required to define above two parameters is task score $v_{\textit{score}}\left(v_{i},p_{k}\right)$ and given as:

$\displaystyle v_{\textit{score}}\left(v_{i},p_{k}\right)=\begin{cases}ect\left% (v_{i},p_{k}\right)\times\textit{WPD}_{k}\times t_{ik},&{\rm if}∼{}v_{i}\in CP% \\ ect\left(v_{i},p_{k}\right),&{\rm else}\\ \end{cases}$ (13)

where critical path $(CP)$ of a DAG is a longest path in the DAG. Further, two parameters: favourite processor $fp_{\textit{energy}}\left(v_{i}\right)$ and favourite predecessor $fpred_{\textit{energy}}\left(v_{i}\right)$ of $v_{i}$ in terms of energy are incorporated and given as:

$\displaystyle fp_{\textit{energy}}(v_{i})=\mathop{\min}\limits_{p_{k}\in p}% \left\{v_{score}\left(v_{i},p_{k}\right)\right\}$ (14) $\displaystyle fpred_{\textit{energy}}\left(v_{i}\right)=\mathop{\max}\limits_{% v_{t}\in\textit{pred}(v_{i})}\left\{\mathop{\min}\limits_{p_{k}\in p}{v_{% \textit{score}}\left(v_{t},p_{k}\right)}\right\}$ (15)

Now, for all task $v_{i}$ from extra cluster, if it is favourite predecessor in terms of energy of any task say $v_{s}$ then assign the cluster to task $v_{i}$ same as the cluster assign to task ${v}_{s}$ . On other hand, if not then assign the cluster as per its favourite processor in terms of energy to task ${v}_{s}$ . The computed values of $v_{\textit{score}}\left(v_{i},p_{k}\right)$ $fp_{\textit{energy}}\left(v_{i}\right)$ and $fpred_{\textit{energy}}\left(v_{i}\right)$ parameters are shown in Table 5, which are used to merge the extra clusters. In our example, the size of sorted processors is equal to the number of initial cluster, so no cluster merging is required.

Table 5

Values of different parameters for cluster combination

Task( $v_{i}$ )	$v_{\textit{score}}$			$fp_{\textit{energy}}$	$fpred_{\textit{energy}}$
	$p_{1}$	$p_{2}$	$p_{3}$
$v_{1}$	14	16	9	$p_{3}$	–
$v_{2}$	13520	12236	91080	$p_{2}$	$v_{1}$
$v_{3}$	32	39	28	$p_{3}$	$v_{1}$
$v_{4}$	10478	2912	48620	$p_{2}$	$v_{1}$
$v_{5}$	16224	7098	41800	$p_{2}$	$v_{1}$
$v_{6}$	17914	9408	46530	$p_{2}$	$v_{1}$
$v_{7}$	58	83	49	$p_{3}$	$v_{3}$
$v_{8}$	62	79	73	$p_{1}$	$v_{2}$
$v_{9}$	69	68	76	$p_{2}$	$v_{2}$
$v_{10}$	102	80	97	$p_{2}$	$v_{7}$

4.3 Cluster mapping and DPM

CDPM performs energy-aware clustering on the basis of energy score ${E}_{\textit{score}}$ parameter of final clusters obtained in phase 2 given as:

$\displaystyle E_{\textit{score}}\left(C_{n},p_{k}\right)=\textit{WPD}_{k}% \times\sum\limits_{v_{i}\epsilon C_{n}}{t\left(v_{i},p_{k}\right)}$ (16)

where $E_{\textit{score}}\left(C_{n},p_{k}\right)$ is the energy score of cluster $C_{n}$ on processor $p_{k}$ Next, all the possible permutations in which the clusters can be mapped to the processor with their sum of energy score are calculated as depict in Table 6(b). Now, the best mapping is selected that give minimum sum of energy score. Hence, the clusters are scheduled on the processors that give the minimum cluster-processor energy consumption. Thereby, cluster $C_{2}=\left(v_{1},v_{2},v_{4},v_{9},v_{10}\right)$ is allocated on processor $p_{2}$ , cluster $C_{1}=\left(v_{3},v_{5},v_{7}\right)$ is allocated on processor $p_{1}$ , and cluster $C_{3}=(v_{6},v_{8})$ is allocated on processor ${p}_{3}$ which gives the minimum energy score of 4718.

Table 6

(a) $E_{\textit{score}}\left(C_{n},p_{k}\right)$ of three clusters on three processors; (b) Different permutations of three processors for three clusters along with sum of energy score of each permutation

(a)
$E_{score}\left(C_{n},p_{k}\right)$	$p_{1}$	$p_{2}$	$p_{3}$
$C_{1}$	2054	868	8800
$C_{2}$	780	574	4400
$C_{3}$	468	378	2530

(b)
Permutation	Mapping of cluster			Sum of energy score
	$C_{1}$	$C_{2}$	$C_{3}$
1	$p_{1}$	$p_{3}$	$p_{2}$	6832
2	$p_{3}$	$p_{2}$	$p_{1}$	9842
3	$p_{1}$	$p_{2}$	$p_{3}$	5158
4	$p_{2}$	$p_{1}$	$p_{3}$	4178
5	$p_{2}$	$p_{3}$	$p_{1}$	5736
6	$p_{3}$	$p_{1}$	$p_{2}$	9958

Furthermore, DPM is applied to reduce static energy consumption on processor $p_{k}$ for idle time $(t_{\textit{idle}}(v_{i},p_{k}))$ . In DPM, during an idle time the processor first takes few time units (Break Event Time, $B E T$ ) to transit from active to low power state [3], second it consumes some energy ( $E C$ ) during low power state and third it incurs some energy penalty $(Pen)$ while transiting from low power to active stated as in Fig. 3.

Figure 3.

DPM deployment in the idle state of a processor.

Specifically, a processor cannot transit to low power state if $t_{idle}(v_{i},p_{k})<\textit{BET}$ as in such case the energy penalty and transition delay will be more expensive and degrade performance. Hence, idle power consumption of a processor $E_{\textit{static}}^{\textit{DPM}}(p_{k}t_{\textit{idle}}(v_{i},p_{k}))$ deploying DPM is given as follows:

$\displaystyle E_{\textit{static}}^{\textit{DPM}}(p_{k}t_{\textit{idle}}(v_{i},% p_{k}))=\begin{cases}{EC}_{s}*\left(t_{\textit{idle}}\left(v_{i},p_{k}\right)% \right)+Pen_{s}&{\rm if}∼{}t_{\textit{idle}}\left(v_{i},p_{k}\right)\geqslant% \textit{BET}_{s}\\ \textit{IPD}_{k}\times t_{\textit{idle}}(v_{i},p_{k})&{\rm else}\\ \end{cases}$ (17)

Thus, the idle energy consumed on all processors $P$ denoted by $E_{idle}$ is given by:

$\displaystyle E_{\textit{static}}^{\textit{DPM}}=\sum\limits_{k=1}^{|P|}\sum% \limits_{i=1}^{|V|}{E_{\textit{idle}}(p_{k},t_{\textit{idle}}(v_{i},p_{k}))}$ (18)

5. Performance metrics and graph generation

Typically, the main performance metrics considered are makespan and energy consumption for all simulation results. The energy consumption and makespan of proposed algorithm CDPM against other referenced algorithm are defined as:

$\displaystyle M_{n}=\frac{M_{\textit{ref}}-M_{\textit{CDPM}}}{M_{\textit{ref}}% },E_{n}=\frac{E_{\textit{ref}}-E_{\textit{CDPM}}}{E_{\textit{ref}}}$ (19)

$M_{ref},E_{\textit{ref}}$ and $M_{\textit{CDPM}},E_{\textit{CDPM}}$ represent makespan, energy consumption of reference algorithm and CDPM algorithm respectively. We used a set of benchmark DAGs of homogeneous system and convert them to set of DAGs for heterogeneous system using parameters stated in Table 6. Heterogeneity factor (ß) gives the variance in task’s computations on different processors [23]. Communication to computation ratio (CCR) gives computation-intensive task graphs for low CCR and communication-intensive for high CCR. Another parameter, average CPU power (ACP) is the specification that characterizes the power consumed by the processors when running the application [24]. A set of four types of AMD Opteron processors with different ACP values [24] are considered in this paper and mentioned in Table 7.

Table 7

Parameters for generating task graphs

Parameter	Value
Number of tasks $(V)$ in a DAG	{10, 20, 30, 50, 100}
Communication to computation ratio (CCR) of DAG	{0.1, 1.0, 10.0}
Range of computation costs on processors ( $\beta$ )	{0.1, 0.25, 0.5, 0.75, 1.0}
Energy heterogeneity factor ( $\alpha$ )	{1, 2, 3, 4}
Number of processors	{3, 5, 7, 9, 10, 15, 20, 25}
Average CPU power (ACP)	{40, 55, 75, 105}
Matrix size (M) for regular graph types	{95, 223} for fast fourier transform

The ACP donates the maximum power that a processor consumes for a task which indeed can increase or decrease according to the application. The uniform distribution used to determine working power dissipation (WPD) of any processor $p_{k}$ per unit time is defined by:

$\displaystyle\textit{WPD}_{k}=\left[\textit{ACP}*\left(1-\mathrm{\alpha}\right% ),\textit{ACP}*\left(1+\mathrm{\alpha}\right)\right];\textit{IPD}_{k}=60-65\%∼% {}of∼{}\textit{WPD}_{k}$ (20)

where ACP is selected randomly from the set of four ACP values from Table 7. The variance in the power consumption is set by the different values of the energy heterogeneity factor ( $\alpha$ ) selected randomly. On other hand, the idle power dissipation of processor (IPD) is calculated by 60–65% of their working power consumption [17]. For simulation the WPD and IPD of the AMD Opteron processors are calculated using Eq. (20). To validate performance with diverse attributes, we consider set of randomly generated applications and real-world application.

5.1 Performance comparison

Proposed CDPM algorithm is compared with other relevant scheduling algorithms – heterogeneous earliest finish time (HEFT) [23], and a power-aware solution to scheduling of precedence-constrained tasks algorithm (PASTA) [17]. HEFT is an insertion-based list scheduling algorithm that gives good performance in terms of makespan, but with no consideration of power consumption. PASTA is a list-based energy-aware algorithm that reduces the number of processors to reduce system energy. However, it ignores static power consumption and the impact of communication cost on makespan. In this paper, clustering is integrated with DPM technique to minimize communication cost and energy consumption respectively. In addition, we have considered three low power states (LPS) standby, dormant, and shutdown instead of a single shutdown state [4]. The low power states, break event time, energy penalty, and energy consumption to deploy DPM technique are given in Table 8b. Figure 4 shows Gantt chart of HEFT, PASTA and proposed CDPM algorithms for the given DAG in Fig. 2.

Figure 4.

(a) HEFT makespan $=$ 80, energy $=$ 6520 joule; (b) PASTA makespan $=$ 113, energy $=$ 5575 joule; (c) CDPM makespan $=$ 94, energy $=$ 4193 joule. Schedule trace and energy consumption of (a) heterogeneous earliest finish time (HEFT) algorithms (b) a power-aware solution to scheduling of precedence-constrained tasks algorithm (PASTA) and (c) Clustering task scheduling with DPM (CDPM).

Table 8

(a) Working and idle power dissipation on three processors; (b) Low power states (LPS) of processor in DPM

(a)
AMD opteron processors	$\textit{WPD}_{k}$ , W	$\textit{IPD}_{k}$ , W
$p_{1}$	26	15.6
$p_{2}$	14	8.4
$p_{3}$	110	66

(b)
LPS	BET	Pen	EC
Standby	1	0.25	0.5
Dormant	5	0.9	0.1
ShutdownZ	10	4.99995	0.0001

PASTA allocates most of its tasks on lowest power consuming processor $p_{2}$ to decrease the dynamic energy consumption, which in turn increases the makespan as shown in Fig. 4b. Proposed CDPM on other hand, generates energy efficient clusters by reducing dynamic and static energy consumption. As in Fig. 4c, task $v_{2}$ scheduled on processor $p_{2}$ has an idle slot $(t_{\textit{idle}}=21)>(BET_{\textit{shutdown}}=10)$ and processor transit to shutdown state with static energy consumption ${E}_{\textit{idle}}\left(p_{2},21\right)=21\times 0.00001+4.99995=5∼{}\mathrm{jouleaprrox}$ . Similarly, DPM can be applied on all idle slots as shown in Table 8(b). Hence, total idle energy consumption is 15 units approx. and dynamic energy consumption for each processor ${p}_{1}=\left(11+12+7\right)\times 26=780∼{}\mathrm{joule},p_{2}=\left(16+19+8% +12+7\right)\times 14=868∼{}\mathrm{joule}$ and $p_{3}=\left(9+14\right)\times 110=253∼{}\mathrm{joule}$ . Hence, total dynamic energy consumption is 4178 and total energy consumption is 4178 $+$ 15 $=$ 4193 joule.

This shows significant amount of static energy consumption saved by applying DPM. In comparison to list based HEFT, proposed CDPM saves 35% energy with increase of 14% makespan, and against energy-aware PASTA, it saves 24% energy with 16% decrease in makespan for under taken DAG.

5.2 Simulation results for random task graphs

Based on parameters in Table 5, the 40 benchmark task graphs for homogeneous system are simulated to give 1365 different DAGs {with three CCRs, five $\beta$ , twelve task graph size $(V)$ , eight number of processors} for heterogeneous system. The simulation results are investigated to analyse the impact of number of tasks, number of processors, CCR, and $\beta$ on energy consumption and makespan.

The first set of experiment compares the total energy consumption and makespan of all algorithms for all tested CCR values (Fig. 5). Average makespan (Fig. 5a) and average total energy consumption (Fig. 5b) of all algorithms tend to increase as CCR increases. At CCR $=$ 0.1 for the computation intensive graphs, CDPM saves energy by judiciously allocating clusters on low energy processors as same as PASTA algorithm. At CCR $=$ 10, CDPM saves energy by cluster merging with low energy score predecessors which is not seen in PASTA. At CCR $=$ 1 where graphs are computation-communication balanced, CDPM balances the energy consumption and makespan. Furthermore, it is also observed that schedules produced by CDPM are close to schedule produced by HEFT, but with significant energy saving than HEFT and PASTA. The energy saving potency of CDPM is more in comparison to HEFT and PASTA regardless of the CCR values. Furthermore, the results are more significant for computation intensive graphs.

Figure 5.

(a) Average makespan and (b) total energy consumption for varying CCRs.

The second set of experiment compares the total energy consumption and makespan of the algorithms for all tested task graph sizes (Fig. 6). Average makespan of CDPM lies below PASTA and near to HEFT same as in experiment first (Fig. 6a). Figure 6b shows that energy consumption of CDPM decreases with the increasing number of tasks and outperforms the other two algorithms. For example, average energy saving of CDPM is 3.34%, 6.16%, 4.14%, 32.95%, and 55.43%, for 12, 20, 30, 50, and 100 respectively over PASTA. This is because when task size is small, less number of clusters are formed with little cluster merging. The only possible way to reduce energy consumption is allocating the clusters on low energy processor selected. For large task size graphs, more clusters are generated and more chances of cluster merging. Therefore, for small task size graphs CDPM behaves as that of PASTA but for large task size graphs it saves more energy than PASTA.

Figure 6.

(a) Average makespan and (b) total energy consumption for varying task size.

Figure 7.

(a) Average makespan and (b) total energy consumption for varying heterogeneities.

Figure 8.

(a) Average makespan and (b) total energy consumption for varying number of processors.

The third set of experiment is conducted to compare the performance and energy consumption for varying heterogeneities (Fig. 7). At each heterogeneity parameter $\beta$ , energy saving of CDPM is found to be more effective than HEFT and PASTA. The results show that clustering adapts better with heterogeneity. For instance, at heterogeneity 1, CDPM saves 42.99% and 45.63% energy over PASTA and HEFT respectively. For total energy, at $\beta=$ 0.1, CDPM is better than PASTA and HEFT by 24.29% and 74.40% respectively. From results, CDPM is found to be quite energy efficient over other algorithms regardless of heterogeneity.

The last set of experiment is performed on the varying number of processors (Fig. 8). The CDPM observes highest energy efficiency (Fig. 8b) regardless of number of processors. Like, for number of processor 3, 7, 10, 20, and 25 energy savings of CDPM over PASTA is 21.66%, 42.08%, 41.63%, 2.58%, and 2.22% respectively. From results, the CDPM tends to behave same like PASTA with increasing number of processors. This is because the selection of the reduced processor is same for both, but energy saving clusters generated by proposed CDPM aid more energy saving than PASTA.

5.3 Simulation results of fast fourier transform (FFT)

To evaluate the performance of CDPM, we have used the real world task graphs of Fast Fourier Transform (FFT). The task graph contained $m\times$ log(m) tasks in which $m$ is the number of items in the FFT’s input vector. For FFT, 150 graphs are generated based on CCR values (0.1, 1, 10), number of processor (3, 5, 7, 9, 10), $\beta$ value (0.1, 0.25, 0.5, 0.75, 1) and number of tasks (95 and 223). Figures 9 and 10 demonstrate average makespan and total energy consumption of 150 graphs on varying CCR and number of processor respectively.

Figure 9.

(a) Average makespan and (b) total energy consumption of FFT for varying CCRs.

Figure 10.

(a) Average makespan and (b) total energy consumption of FFT for varying number of processors.

With the increasing number of processors, CDPM can obtain greater percentage of energy saving compared with PASTA and HEFT. For example, when the tasks are scheduled on three processors, the energy saving of CDPM compared with PASTA is 27.51%, and up to 55.79% when the number of processors is 10. Table 8 shows with the increasing CCR, CDPM can reduce more energy consumption compared with PASTA and HEFT algorithm. For example, at CCR $<$ 1 CDPM significantly save 43.04% energy over PASTA and 51.35% over HEFT and their ratio increase to 59.11% and 68.54% at CCR $>$ 1 respectively.

Table 9

Average results of randomly generated applications and FFT

Value	CDPM over PASTA		CDPM over HEFT
	$E_{n}\%$	$M_{n}\%$	$E_{n}\%$	$M_{n}\%$
CCR $=$ 0.1	43.05	37.96	51.33	$-$ 6.53
CCR $=$ 1	41.99	25.73	63.31	$-$ 14.2
CCR $=$ 10	59.11	$-$ 4.52	68.54	$-$ 36.4
$\beta=0.1$	49.04	36.49	55.5	$-$ 13.9
$\beta=0.25$	46.41	37.92	57.21	$-$ 7.45
$\beta=0.5$	45.4	36.97	52.36	$-$ 6.81
$\beta=0.75$	32.32	31.46	47.8	$-$ 2.68
$\beta=1$	45.63	31.79	51.17	$-$ 14.3

6. Conclusion

This paper worked on clustering scheduling approach to reduce static and dynamic energy consumption of precedence constrained tasks on heterogeneous computing platforms. As the clustering heuristics gives reduced makespan of an application program, these are made energy efficient in this paper. The proposed energy-aware clustering task scheduling algorithm with dynamic power management (CDPM) judiciously allocates the clusters on the processors such that dynamic energy consumption reduction is achieved. For this, the proposed algorithm builds clusters on the basis of favourite processor and favourite predecessor selection while keeping an eye on makespan and dynamic energy consumption. Further, DPM technique was exploited to the processor for the available idle periods with one of the feasible low power state (shutdown, dormant, standby) to reduce static energy consumption. The potency of CDPM algorithm is compared with well-known list-based HEFT and energy-aware PASTA algorithms with respect to number of processors, CCRs, heterogeneity, and number of tasks. For an average of random and regular graphs, CDPM gives better energy reduction of 73.5% and 47.5% on communication intensive applications against HEFT and PASTA algorithm respectively. For computation intensive applications, CDPM gives energy reduction with 65% and 20% against HEFT and PASTA algorithm respectively. Simulation results conducted on both random graphs and regular graph revealed that CDPM significantly reduces energy consumption, with results being more superior for communication intensive graphs.

Footnotes

Authors’ Bios

Nirmal Kaur earned PhD from IKG-Punjab Technical University, Kapurthala (2017), Masters of Comp. Sc. and Engg. from Punjab Technical University, Kapurthala (2009), and Bachelors of Comp. Sc. and Engg. from Punjabi University, Campus, Patiala (2003), India. Presently, she is an Assistant professor at UIET, Punjab University, Chandigarh, India. Her current areas of interest include energy efficient and fault tolerant scheduling on parallel computing systems, and Digital image watermarking techniques. She is available at

nirmaljul19@gmail.com.

Raman Bhinder pursued her Masters in CSE (2019) from UIET, Punjab University, Chandigarh, India and Bachelors in CSE (2012) from Punjab Technical University, Kapurthala. She is Sr. Software Engineer at Oceana Tech, Zirakpur, India. Her areas of interest include energy aware multiprocessor scheduling, automating engineering processes and developing enterprise applications. She is available at

raman2308@gmail.com.

References

TOP 500 supercomputers sites, TOP500 list generated for the year 2018, https://www.top500.org/lists/(2018)/11/.

Orgerie

A.C.

Assuncao

M.D.D.

and Lefevre

, A survey on techniques for improving the energy efficiency of large-scale distributed systems, ACM Computing Surveys (CSUR) 46(4) (2014), 47.

Venkatachalam

and Franz

, Power reduction techniques for microprocessor systems, ACM Computing Surveys (CSUR) 37(3) (2005), 195–237.

Legout

Jan

, and Pautet

, Scheduling algorithms to reduce the static energy consumption of real-time systems, Real-Time Syst 51(2) (2015), 153–191.

Sueur

and Heiser

, Dynamic voltage and frequency scaling: The laws of diminishing returns, in: Proceedings of the International Conference On Power Aware Computing And Systems, USENIX Association (Oct 3 2010), 1–8.

Baskiyar

and Palli

K.K.

, Low power scheduling of dags to minimize finish times, in: High Performance Computing-HiPC, Springer Berlin Heidelberg (2006), 353–362.

Baskiyar

and Abdel-Kader

, Energy aware DAG scheduling on heterogeneous systems, Cluster Computing 13(4) (2010), 373–383.

Shekar

and Izadi

, Energy aware scheduling for DAG structured applications on heterogeneous and DVS enabled processors, In Green Computing Conference IEEE (2010), 495–502.

Nirmal

Bansal

and Bansal

R.K.

, Energy efficient duplication-based scheduling for precedence constrained tasks on heterogeneous computing cluster, Multiagent and Grid Systems 12(3) (2016), 239–252.

10.

Nirmal

Bansal

and Bansal

R.K.

, Energy conscious scheduling with controlled threshold for precedence-constrained tasks on heterogeneous clusters, Concurrent Engineering 25(3) (2017), 276–286.

11.

Wang

Khan

S.U.

Chen

Kołodziej

Ranjan

C.Z.

and Zomaya

, Energy-aware parallel task scheduling in a cluster, Future Generation Computer Systems 29(7) (2013), 1661–1670.

12.

Liu

Duan

and Du

, An energy efficient clustering-based scheduling algorithm for parallel tasks on homogeneous DVS-enabled clusters, In Computer Supported Cooperative Work in Design (CSCWD), IEEE 16th International Conference on IEEE (2012), 575–582.

13.

Tang

X.Y.

and Tan

W.Z.

, Energy-efficient reliability-aware scheduling algorithm on heterogeneous systems, Scientific Programming (March 2016), Article ID 9823213, 14.

14.

Gong

and Zou

, Energy-efficient scheduling algorithm of task dependent graph on DVS-Unable cluster system, in: Grid Computing, 10th IEEE/ACM International Conference on IEEE (2009), 217–224.

15.

Mei

and Li

, Energy-aware task scheduling in heterogeneous computing environments, Cluster Computing 17(2) (2014), 537–550.

16.

Nirmal

Bansal

and Bansal

R.K.

, Duplication-controlled static energy-efficient scheduling on multiprocessor computing system, Concurrency and Computation: Practice and Experience 29(12) (2017), e4124.

17.

Sharifi

Shahrivari

and Salimi

, PASTA: A power-aware solution to scheduling of precedence-constrained tasks on heterogeneous computing resources, Computing 95(1) (2013), 67–88.

18.

Nirmal

, Energy efficient scheduling techniques for distributed computing systems, Ph. D thesis IKG-Panjab Technical University, Kapurthala (2017).

19.

De Langen

and Juurlink

, Leakage-aware multiprocessor scheduling for low power, In Parallel and Distributed Processing Symposium, IPDPS 20th International IEEE 2006 8-pp.

20.

Nesmachnow

et al, Energy-aware scheduling on multicore heterogeneous grid computing systems, J Grid Computing (11) (2013), 653–680.

21.

Kyle Tarplee

et al., Energy-aware profit maximizing scheduling algorithm for heterogeneous computing systems 2014, 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 595–603.

22.

Kaur

and Chhabra

, Fault-aware advance reservation scheduling in heterogeneous computing systems, International Journal of Applied Engineering Research 13(11) (2018), 9636–9645.

23.

Topcuoglu

Hariri

and Wu

M.Y.

, Performance-effective and low-complexity task scheduling for heterogeneous computing, Parallel and Distributed Systems, IEEE Transactions on 13(3) (2002), 260–274.

24.

Measuring Processor Power TDP vs. ACP https://www.intel.com/content/dam/doc/white-paper/resources-xeon- measuring-processor-power-paper.pdf, 2011.

Energy-aware clustering scheduling of parallel applications on heterogeneous computing systems

Abstract

Keywords

1. Introduction

3. Models

Table 1 Notations used in the proposed CDPM algorithm

3.2 Task model

3.3 Energy model

Footnotes

Authors’ Bios

References

Table 1
Notations used in the proposed CDPM algorithm