Survey on energy efficient scheduling techniques on cloud computing

Abstract

With ever-growing technical advances, performance of complex scientific and engineering applications has arrived at petaflops and exaflops range. However, massive power drawn from the large scale computing infrastructure has caused commensurate rise in electricity consumption, escalating data center ownership costs besides leaving carbon footprints. Judicious scheduling of complex applications with an objective to reduce overall makespan and reduced energy consumption has become one of the biggest confront in the realm of computing architectures. This paper presents a survey on energy efficient scheduling algorithms based on dynamic voltage and frequency scaling (DVFS) and dynamic power management (DPM) techniques. The parameters considered are mainly the makespan, processor energy (dynamic and static) consumption, and network energy (communication) consumption, wherever appropriate during task scheduling.

Keywords

Power consumption duplication based scheduling list based scheduling clustering based scheduling dynamic power management dynamic voltage and frequency scaling

1. Introduction

For sustainable computing, growing energy consumption tends to be the major obstacles for the proliferation of high performance computing. Over the last decade, performance improvement of computing systems from gigaflops to petaflops [17] resulted in substantial energy consumption rise. In the current computing paradigm, speedup of petaflops is drawing enormous power consumption, and is inevitably obscuring the expansion of future exascale machines. Contemporary exascale machines consume incredible power consumption of the order of 100 MW leading to unsustainable energy utility costs. There are many survey papers in the domain of power aware scheduling, but as the technology, tools, and associated features are developing rapidly, there is a sufficient research space to uncover certain aspects, which is the focus of work in this paper. The performance and power consumption scenario of the worldwide powerful machines can be realized from the latest Top500 list, wherein Japan’s Fugaku is number one supercomputer with power and performance of 28.3 megawatt and 415.5 petaflops respectively [49]. The data centers are predicted to draw more than 1000TWh energy in the next decade, surpassing power dissipation of Japan and Germany. Ultimately, power dissipation has reached at an alarming stage that leads to increase operational cost, poor system reliability, additional cooling costs, and limited battery life besides ecological hazards. In view of the issues, challenges, and constraints in computing paradigms, competent energy efficient scheduling techniques that can sustain the makespan and reduce overall energy consumption need to be investigated. This article intends to help the research fraternity for better insights on energy aware techniques, as well as to develop more competent power aware systems of tomorrow.

As the task scheduling of an application program is crucial, it needs to be managed effectively to utilize the full potency of parallel computing platforms. In the past few decades, researchers are working hard on scheduling problem mainly to get minimal makespan. However, in the light of sustainability, it is pertinent to carefully schedule tasks on an interconnected system of multiprocessor (homogeneous or heterogeneous) machines such that total energy consumption is kept low while meeting quality of service. As injudicious scheduling heuristics may lead to redundant energy consumption, much focus is being paid to optimize the energy consumption nowadays. Sometimes, these objectives are aberrant with each other, and are difficult to attain.

Major part of this paper is divided into two parts, i) Survey of DVFS-based energy aware scheduling on uniprocessor and multiprocessor computing systems, particularly in the context of different task scheduling heuristics, ii) Then, owing to the fabrication of compact and fast transistor sizes for complementary metal oxide semiconductor (CMOS) design, static power dissipation is increasing at an exponential rate. The growing trend of chip scaling to nano-scale causes static power dissipation to come near to the level of dynamic power, and thereby needs careful concerns too. To address this issue, DPM-based energy efficient techniques and associated algorithms are identified and discussed in the second part of the paper.

The remainder of this paper is organized as follows. Section 2 provides a glimpse on task scheduling heuristics, and power consumption in CMOS logic circuit, and an overview of the power management techniques. Next Section presents survey on energy efficient scheduling algorithms based on DVFS and DPM techniques. Finally, Section 4 discusses the concluding remarks. The main contributions of the proposed paper are as:

1)
Paper presents the static scheduling heuristics to reveal them further on energy aware frontage.
2)
Energy efficient scheduling algorithms are surveyed based on DVFS and DPM-based techniques.
3)
Survey on DVFS-based technique is presented covering, i) different computing platforms (uniprocessor and multiprocessor), ii) homogeneity/heterogeneity of multiprocessor systems, iii) type of application tasks (independent and dependent) to be scheduled, iv) and type of heuristics (list-based, clustering-based, and duplication-based) for scheduling tasks of a parallel application.
4)
Survey on DPM-based technique is presented covering, i) different power states of a processor, ii) power aware scheduling considering simple and complex power states of processor.
5)
Consideration of optimization parameters that includes makespan/schedule length, dynamic energy, static energy, and communication energy consumption of an application program.

2. Background

2.1 Preliminary on task scheduling heuristics

Scheduling aims at reducing the application’s overall execution time by carefully allocating and assigning tasks to the available processors. The overall time to execute a parallel application is termed as makespan/schedule length. Mapping tasks of an application on a given set of processors can be based on static scheduling or dynamic scheduling [14]. This paper focuses on static scheduling heuristics, wherein execution time of tasks, amount of data-flow, and data dependencies are known at compile-time. Scheduling on multiprocessor system is a well-known nondeterministic NP-complete problem [12] with optimal schedules available under approximation and heuristic-based techniques. Heuristic-based techniques are taken up in this paper, which are further classified as list, clustering, and duplication, each with its own performance and complexity. Over several facets of technology shift and computing paradigms, taxonomy of scheduling techniques into the fundamental categories is shown in Fig. 1.

Figure 1.

A brief task scheduling taxonomy.

List-based heuristics use certain priority scheme to assign task priority, and then allocate task to a processor that gives earliest start time. Traditionally, these heuristics were designed for homogeneous multiprocessor systems with and without interprocess communication costs (IPC), and later on, in view of heterogeneity of processors as well. However, these heuristics are not able to well exploit the parallelism of communication intensive graphs due to lack of addressing IPC costs. In pursuit to fulfill the computing power of wider complexity and big simulations, state-of-the-art industrial and scientific society demands heterogeneous computing systems. In this regard, distributed computing resources [13] provide a way to tackle scheduling problems of increased complexity. Some algorithms that fall under list-based heuristic include Highest Level First with Estimated Times (HLFET), Smallest Co-Level First with Estimated Times (SCFET), Critical Path/Most Immediate Successors First (CP/MISF), Heaviest Node First (HNF), Earliest Task First (ETF), Mapping Heuristic (MH), Modified Critical Path (MCP), Fast Critical Path (FCP), Heterogeneous Earliest Finish Time (HEFT), Performance Effective Task Scheduling (PETS), Longest Dynamic Critical Path (LDCP), Lookahead, Constrained Earliest Finish Time (CEFT), Predict Earliest Finish Time (PEFT) etc.

The IPC problem of list-based heuristics is alleviated by clustering-based scheduling as proposed in late eighties and early nineties. Here, the heavily communicating tasks are grouped in cluster, and then mapped on processors. Scheduling algorithms under this heuristic are Edge Zeroing (EZ), Dominant Sequence Cluster (DSC), Clustering and Scheduling System – II (CASS II), Clustering for Heterogeneous Processors (CHP), Triplet, Wrap Cluster Merging (WCM), and Global Load Balancing (GLB), Cluster Pair Priority Scheduling (CPPS), Computation Communication Load Clustering (CCLC), Dynamic Computation Communication Load (DCCL), Randomized Dynamic Computation Communication (RDCC), Bounded Dominant Sequence Clustering (BDSC) etc.

Another static scheduling heuristic is duplication-based scheduling that intends to duplicate predecessor tasks on multiple processors to evade the costly IPC, and thereby gives much reduced makespan over list-based. Some examples from this category are: Task Duplication based Scheduling (TDS), Modified Task Duplication based Scheduling (MTDS), Duplication Scheduling Heuristic (DSH), Bottom-Up Top-Down Duplication Heuristic (BTDH), Critical Path and Fast Duplication (CPFD), Selective Duplication (SD), Heterogeneous Limited Duplication (HLD) etc.

2.2 Task scheduling model

A parallel application is in the form of a directed acyclic graph (DAG). A DAG is decomposed into multiple tasks, and has precedence constraints among the parent and child tasks. For the correct execution of an application program, the tasks must execute as per the precedence constraints relation. A DAG is denoted by a graph $G(V,E,T,C)$ . Here, $V$ is the set of tasks ${\{}v_{i}|v_{i}$ is an ordered tasks, $i=1,2,3,\ldots,v{\}}$ such that $v_{j}$ can start execution only after $v_{i}$ finishes. An edge set $E={\{}e_{ij}|e_{ij}$ is an edge from task $v_{i}$ to $v_{j}{\}}$ . The variable T represents the cost of executing task $v_{i}$ on the $k^{\text{th}}$ processor, and $C={\{}c_{ij}|c_{ij}$ is communication time to transfer message from task $v_{i}$ to $v_{j}$ . An entry and exit task in a DAG is a task without any parent and child respectively.

2.3 CMOS power consumption

Major sources of power dissipation in CMOS logic circuit [50] are dynamic and static power. Dynamic power dissipation occurs due to the circuit activity as transistors switch states in the logic circuit, and has two main components: i) switched capacitance, and ii) short-circuit current. Switched capacitance, one of the most dominating components, occurs due to charging and discharging of load capacitances during high to low or low to high transitions at the outputs of the circuit, and is defined as:

$\displaystyle p^{\textit{dyn}}\sim\alpha C_{\textit{load}}V^{2}f$ (1)

where $\alpha$ and $C_{\textit{load}}$ is the switching activity factor and load capacitance of logic gate, $V$ is the supply voltage, and $f$ is the clock frequency of circuit and $p^{\textit{dyn}}$ is the processor’s dynamic power consumption. Short-circuit current contributes a small fraction of total power consumption, and dissipates when n-type and p-type transistors are conducting simultaneously.

Static power dissipates due to leakage currents, and is independent of transistor switching states. Due to attenuation of CMOS technology to sub micron level and thousands of transistors integration on a chip, static power consumption is increasing more than dynamic power [9]. Leakage current can be of different types – reverse-biased-junction leakage, gate-induced-drain leakage, subthreshold leakage, gate-oxide-tunnelling, gate-current leakage, and punch-through leakage. Out of these, subthreshold leakage and gate-oxide-tunnelling leakage consumes significant total leakage current.

The static power consumption $p^{\textit{sta}}$ is defined as:

$\displaystyle p^{\textit{sta}}=V.I_{\textit{leakage}}$ (2)

where $I_{\textit{leakage}}$ is the leakage current flowing through transistors even when they are turned-off. Equations (1) and (2) indicate that dynamic power consumption is cubically dependent on the product of voltage and frequency, and static power consumption is linearly dependent on voltage. Therefore, reduction in dynamic power consumption, by means of dynamic control of processor’s voltage and frequency can play a vital role in the design of energy efficient systems.

2.4 Power management techniques

2.4.1 Dynamic voltage and frequency scaling (DVFS)

This technique was introduced in digital circuits in mid-nineties to control processor voltage and frequency based on the system workloads. Conventionally, energy-aware techniques are used to find trade-offs between performance and energy reduction. Selection of lower frequency and voltage pair results in power reduction of processor, but performance may be deteriorated. Thereby, power savings and performance sustain are highly volatile. Several commercial processors (AMD PowerNow and Intel SpeedStep) are driven by this scheme. Many contemporary processors are equipped with built-in support of DVFS to reduce power consumption by means of dynamic control of operating voltage and frequency. As a processor executes several tasks concurrently with inter-task dependencies, idle-times/slacks of varying sizes are typically incurred. In DVFS mechanism, idle-times are exploited with one of the appropriate discrete voltage and frequency to reduce dynamic power consumption of processor. However, lowering down voltage and frequency may increase task execution time, which in turn may elongate the overall makespan. Therefore, exploiting DVFS scheme is beneficial, if reduction in energy consumption does not deteriorate the makespan of an application program.

2.4.2 Dynamic power management (DPM)

Significant amount of power dissipates when processor is in active and idle mode. As peak performance is desired during certain time intervals, processor must not stay in active mode for the entire scheduling periods so as to generate the energy efficient schedules. A CPU/processor supports shutdown and slowdown power-saving modes to reduce power consumption under ambience of certain validation constraints such as context switch overheads. Processor in shutdown mode is considered as highest power saving mode but with more switching overheads. In this paper, slowdown mode is further categorized into standby and dormant modes. Depending on workload of an application program, appropriate power-saving modes could be utilized to reduce much power consumption instead of letting the processor to remain in idle mode [3, 33]. The strategy behind the DPM policy is the judicious selection of available idle slots against one of the feasible power-saving modes. However, switching a processor from a specific power-saving mode to an active mode comes along with certain context switch overheads in terms of transition delay and energy penalty. Consequently, applying DPM is meaningful provided energy consumption reduction for a given power-saving mode succeeds over energy penalty overheads.

3. Energy efficient scheduling techniques

This paper presents survey on energy efficient task scheduling, in particular to the identification and classification of power/energy aware techniques, types of the computing paradigm, types of an application program, and types of the scheduling heuristics deployed on an application program, as shown in Figs 2 and 3. To begin, energy aware techniques are classified into two prominent categories namely DVFS and DPM. The DVFS-based scheduling is further classified covering many facets such as type of computing platform (homogeneous uniprocessor or homogeneous and heterogeneous multiprocessor system), type of an application (independent or dependent/precedence constrained tasks), type of scheduling heuristics (list-based, duplication-based, clustering-based) deployed on an underlying computing platform, as shown in Fig. 2. Further, DPM-based techniques in relation to different power states of a processor are presented in Fig. 3.

Figure 2.

DVFS-based energy efficient scheduling techniques.

Figure 3.

Taxonomy of DPM-based energy efficient scheduling.

3.1 DVFS scheduling on uniprocessor systems

Earlier works in this sphere were largely focused on real-time scheduling of independent tasks, especially on uniprocessor homogeneous computing platforms. In real-time scheduling, tasks deadline are given and their WCET (Worst-Case Execution Times) are typically known before-hand. Many algorithms developed in this domain have leveraged the performance slack available in real time. Aydin et al. [1] found that using WCET to guarantee the temporal constraints of the workload may not properly utilize the unused computations as WCET and actual execution times of real-time applications can differ. The scheduling algorithms for independent and dependent tasks as proposed by Zhu et al. [54] try to overcome the limitations of prior techniques [1, 21, 53]. In the mid nineties, CMOS technology was not smart enough; the algorithms were evaluated on execution traces and certain simulation models. In papers [29, 44], favorable set of frequency and voltage is computed to reduce energy-delay product of a circuit. The aim was to scale down the operating voltage till the desired clock frequency is reached. By the year 2000, semiconductor technology seemed mature with the inclusion of DVFS-enabled commodity processors.

DVFS-based algorithms can be classified as on-line and off-line. The former one relies on past behavior/history of the system to forecast future workloads to decide voltage-frequency scaling along with possible scaled value. Interval-based DVFS is one of the on-line schemes that divide the time into fixed length intervals so that voltage scaling is activated only at the start of each interval. Weiser et al. [51] suggested an on-line scheme for energy efficient scheduling of non real-time tasks. Later on, Govil et al. [16] extended the work with a sophisticated prediction policy to discover the processor busy interval time, and then smoothing speed to balance power consumption and delay. The main issues with interval-based DVFS are irregular prediction of future workloads and certain performance degradations. To address this issue, Sinha and Chandrakasan [47] suggested adaptive filtering to smooth out noises in the past workload patterns. On contrary, an off-line DVFS algorithm fixes voltage scaling in advance. Task-based DVFS is an off-line scheme that controls voltage and frequency per task basis instead of fixed time intervals, making it more practical and suitable for real-time tasks having varying timing requirements. Based on this approach, Yao et al. [53] proposed an optimal, off-line polynomial time scheduling algorithm for real-time independent tasks on a variable speed uniprocessor system to compute optimal minimum energy schedule. In [21], authors suggested an integer linear programming by which voltage selection varies as per the task switching activity. Tasks with more switch activity were exploited with lower voltages and vice-versa. Ultimately, a task may exhibits different voltage and frequency for different cycles. In contrast, Manzak and Chakrabarti [38] assumed a set of continuous voltages and a single voltage-frequency for a task. They presented an off-line scheduling algorithm based on the switching activity of tasks with random arrivals and deadlines.

3.2 DVFS scheduling on multiprocessor systems

In this part of survey, the approach and track on energy efficient techniques on multiprocessor system is discussed for scheduling dependent tasks on homogeneous and heterogeneous systems, and with respect to different scheduling heuristics such as list-based, duplication-based, and clustering-based. It is gathered that most of the available works exploited list-based heuristics over duplication and clustering to reduce dynamic energy consumption.

3.2.1 Energy aware list-based scheduling algorithms

With the inclusion of matured CMOS technology in the year 2000, Gruian and Kuchcinski [15] proposed a list based Low Energy Scheduling (LENES) algorithm for scheduling dependent tasks on homogeneous computing paradigms, as opposed to the prior works mainly done for independent task scheduling. LENES makes use of an energy sensitive priority function to run processor at varying voltages to generate energy efficient static schedules. Its performance for certain random and real graphs was shown to be quite well. An Energy Reduction Algorithm [24] was proposed on a power scalable homogeneous cluster for directed acyclic as well as tree task graphs. The algorithm selects lower and uniform voltage and frequency along the critical path in task graph. Dynamic voltage scaling is applied at an average for two consecutive tasks, provided they exhibit certain slack time. Simulation results on a real platform showed energy reduction with some makespan degradation.

The ignorance of IPC costs in this algorithm was handled by Mori et al. [43] with a Power Aware Scheduling Algorithm (PASA) to schedule dependent tasks on homogeneous cluster. PASA selects an appropriate frequency for the tasks that are not on the critical paths. Based on task selection based mechanism, wherever feasible, power consumption was reduced during heavy and low load computation times. For consecutive tasks with slack times, a task that can reduce maximum amount of power consumption is selected and exploited with DVFS. However, simulation results of PASA were conducted for few random task graphs only.

Another list-based algorithm was formulated by Wang et al. [52] known as Power Aware List Scheduling (PALS) for dependent tasks on homogeneous clusters. This algorithm finds the slack times of non-critical tasks, extends their execution times, and applies voltage scaling during idle and communication phases. In PALS, a list-based earliest task first (ETF) algorithm was implemented to generate a schedule list, and then voltage scaling is applied for all the non-critical tasks. A green service level agreement (SLA) was also formulated that showed negotiation of performance degradation and energy savings. This algorithm was found to be effective over other well-known algorithms namely Energy Reduction Algorithm, LENES, and ECS [37]. Low Power Heterogeneous Machine (LPHM) [8] algorithm combined traditional list-based HEFT algorithm with voltage scaling for continuous voltage scalable processors. It identifies the available scheduling slots on a processor and exploited dynamic voltage scaling technique to reduce dynamic energy consumption without violation of precedence constraints. The simulation results on a large set of random graphs showed a considerable energy consumption reduction over HEFT.

Kaur et al. [28] extended LPHM algorithm, and suggested list-based LDVS algorithm, wherein dynamic voltage scaling is exploited for idle and communication times in the schedule of HEFT algorithm. The total energy consumption was considered for both computation and communication energy. The simulation results of LDVS on an exhaustive set of random and regular graphs were shown better than related list-based HEFT and duplication-based HLD algorithms.

To balance trade-off between makespan and energy consumption, an Energy Conscious Scheduling (ECS) [37] algorithm was implemented for parallel tasks on heterogeneous distributed computing system. Two parameters namely relative superiority (RS) and makespan-conservative energy reduction (MCER) were included for scheduling of tasks. Further, this approach was extended by ECS $+$ Idle algorithm [36] that considered processor’s idle energy consumption besides active energy of processor. For the purpose, RS and MCER parameters were fine tuned to incorporate processor’s indirect energy consumption. ECS and ECS $+$ Idle algorithms were found to be energy efficient over classical list-based HEFT and duplication based DBUS algorithms.

Baskiyar and Abdel-Kader [7] presented an Energy Aware DAG Scheduling (EADAGS) algorithm for scheduling dependent tasks on heterogeneous system. The idle slots generated by Decisive path scheduling (DPS) algorithm were exploited with discrete voltage levels to achieve energy gains. For heterogeneous computing platforms, an energy-efficient elastic (3E) [55] algorithm was suggested for scheduling aperiodic, independent non-real time tasks. This algorithm can adjust supply voltages and frequencies of a processor depending on the system workload, and thereby makes a nice compromise between expected finish time and energy consumption. A survey of popular list-based DVFS scheduling algorithms on homogeneous and heterogeneous multiprocessor systems is shown in Table 1.

Table 1
List-based scheduling heuristics with DVFS technique

Approach	Algorithm/year	Application type	Target platform	Target energy
List-based scheduling	LENES/2001 [15]	Dependent tasks	Homogeneous computing	Computation
and DVFS	Energy reduction algorithm/	Dependent tasks	Homogeneous cluster	Computation
	2006 [24]
	Power aware scheduling	Dependent tasks	Homogeneous cluster	Computation
	algorithm/2009 [43]
	PALS/2013 [52]	Dependent tasks	Homogeneous cluster	Computation
	LPHM/2006 [7]	Dependent tasks	Heterogeneous computing	Computation
	LDVS/2015 [28]	Dependent tasks	Heterogeneous computing	Computation and
				communication
	ECS/2009 [37]	Dependent tasks	Heterogeneous distributed computing	Computation
	ECS $+$ idle/2011 [36]	Dependent tasks	Heterogeneous distributed computing	Computation
	EADAGS/2010 [7]	Dependent tasks	Heterogeneous computing	Computation
	3E/2013 [55]	Independent tasks	Heterogeneous distributed computing	Computation

3.2.2 Energy aware clustering and duplication-based scheduling algorithms

As duplication and clustering-based scheduling heuristics give more reduced makespan, some energy management techniques are also investigated for these heuristics. Power Aware Task Clustering (PATC) [52] was formulated, in which an edge zeroing (EZ) algorithm was made energy aware via DVFS technique. Traditional EZ reduces makespan by zeroing the edges of high communication costs in a task graph. However, PATC guides edge zeroing process from the perspective of power consumption reduction. Ruan et al. [46] suggested Energy Efficient Scheduling algorithm TDVAS for the parallel applications running on homogeneous clusters by utilizing voltage scaling to baseline Task Duplication Scheduling (TDS) algorithm without makespan increase. An Energy Optimization Scheduling for Task Dependent Graph (EOTD) [42] was formulated for homogeneous computing platforms. Unlike the previous works, EOTD mainly focused on targeting communication and static energy of processing elements. EOTD employed task clustering, dynamic voltage scaling, and binary search based power management. For energy optimization, this algorithm make use of clustering scheduling to reduce transmission time and communication energy, DVFS scheme to reduce dynamic energy, and then DPM on a binary search to reduce static energy consumption.

To balance makespan and energy consumption on homogeneous clusters, Zong et al. [56] presented Energy Aware Duplication (EAD) and Performance-Energy Balanced Duplication (PEBD) algorithms. The main motive of these algorithms was to judiciously replicate the predecessors of a task such that replication/duplication reduces makespan without increasing energy consumption. For this, fixed set of threshold values were selected to control the number of duplications. Only those duplications were allowed that do not increase system energy consumption. However, the suggested algorithm did not exploited DVFS technique. The performance of EAD and PEBD were shown to perform well than existing TDS and MCP algorithms for some regular task graphs. An extension to Zong’s work was carried by Liu at al. [34] with an Adaptive Energy Efficient Scheduling (AES) algorithm. AES combined adaptive threshold approach with dynamic voltage scaling. The performance of algorithm was observed good over TDVAS, EAD, and PEBD algorithms.

Some alternatives of Zong’s algorithm were proposed to reduce communication energy consumption of dependent tasks on homogeneous cluster. Liang et al. [31] implemented an Energy Aware Dynamic Clustering Scheduling algorithm, which made use of clustering and dynamic re-clustering techniques. Preliminary clustering aims to create clusters of tasks into multiple groups prior to application execution. However, due to uncertainty of execution time, dynamic re-clustering can adjust the clustering groups based on a threshold and communication overhead. Another Novel Energy Aware Scheduling Algorithm (NEASA) [30] was suggested based on two-phase frequency scaling algorithm. NEASA adopted the DVFS technique, wherein both static as well as dynamic workload variation slack times were reclaimed, and exploited with different frequencies. NEASA is shown to be energy efficient than TDVAS for compute intensive applications. However, the algorithm was not at an obvious advantage for communication intensive applications.

The aforesaid duplication-based algorithms were applicable on homogeneous clusters with an assumption of an unbounded number of processors. But, most of these algorithms are not pertinent on clustering-based scheduling if number of processors tends to be less than as required to schedule multiple cluster groups. In that case, some dummy processors are utilized to assign the leftover clusters. Moreover, for heterogeneous platforms, owing to different capacities of processors, the suggested solutions may not perform well. Some works on duplication-based heuristics are available on heterogeneous platforms, which are discussed below.

Baskiyar and Abdel-Kader [7] suggested an Energy Aware Graph Scheduling with Duplication (EAGS-D) algorithm, wherein duplication-based heterogeneous N-predecessor duplication (HNPD) algorithm was integrated with DVFS. In EAGS-D, duplication is retained if it helps to lower finish time; else it is discarded so as to reduce computation energy consumption. The proposed technique neglected communication energy consumption of interconnects. In Energy Efficient Task Duplication Schedule (EETDS) algorithm, two-phase strategy was employed to balance makespan and energy consumption tradeoff for heterogeneous cluster. In first phase, grouping was done to create group of tasks that belong to a critical path to reduce communication energy consumption. In second phase, duplication-based strategy was applied to reduce more power dissipation. EETDS was observed better than TDS and NDS algorithms with certain makespan degradation.

An Energy Aware minimized Duplication (EAMD) for heterogeneous computing environment was formulated by Mei and Li [40], which is an extension to baseline HLD algorithm. EAMD attempts to remove the superfluous tasks to reduce the processor’s energy consumption. However, removal of redundant tasks might increase the communication energy consumption of its child tasks that was ignored in EAMD. The idea of exploiting DVFS onto the primary and duplicated tasks is implemented in Energy Aware Duplication Scheduling (EADS) [27] algorithm. EADS analyzed computation and communication energy consumption against list-based HEFT, LPHM and duplication based HLD algorithms. Recently, Kaur et al. [26] proposed an Energy Conscious Scheduling with Controlled Threshold (ECSCT) that integrated controlled threshold-based duplication with dynamic voltage scaling. The simulation results were found significant over list-based (HEFT, LPHM) and duplication-based (HLD, EADS, EAMD) for an exhaustive set of random and real task graphs. Maurya and Tripathi [39] developed an Energy Aware Edge Priority Scheduling (EAEPS) for multiprocessors. This algorithm makes the EPS (Edge Priority Scheduling) algorithm energy efficient by zeroing the edges of higher priorities, and reduces the energy consumption by exploiting DVFS technique. Hu et al. [19] developed an algorithm Energy Aware Scheduling with Service Level Agreement EASLA for cluster systems having DVFS enabled processors. The main idea behind their algorithm is to distribute slacks of set of tasks and scale down voltage/frequencies to achieve energy reduction. The survey of popular duplication and clustering-based algorithms for dependent tasks on multiprocessor system is given in Table 2.

Table 2
Clustering and duplication-based energy aware scheduling

Approach	Algorithm/year	Application type	Target platform	Target energy
Clustering-based energy	PATC/2013 [52]	Dependent tasks	Homogeneous	Computation
aware scheduling	EOTD/2010 [42]	Dependent tasks	Homogeneous	Computation and communication
	Energy aware dynamic	Dependent tasks	Homogeneous	Computation and communication
	clustering 2013 [31]
	EAEPS/2018 [39]	Dependent tasks	Homogeneous cluster	Computation
Duplication-based energy	TDVAS/2007 [46]	Dependent tasks	Homogeneous	Computation
aware scheduling	EAD and PEBD/2011 [56]	Dependent tasks	Homogeneous	Computation and communication
	AES/2014 [34]	Dependent tasks	Homogeneous	Computation and communication
	EETDS/2007 [57]	Dependent tasks	Heterogeneous computing	Computation and communication
	NEASA/2015 [30]	Dependent tasks	Homogeneous	Computation and communication
	EAMD/2012 [40]	Dependent tasks	Heterogeneous computing	Computation
	EAGS-D/2010 [7]	Dependent tasks	Heterogeneous	Computation
	EADS/2016 [27]	Dependent tasks	Heterogeneous computing	Computation and communication
	ECSCT/2017 [26]	Dependent tasks	Heterogeneous computing	Computation and communication
	EASLA/2018 [19]	Dependent tasks	Heterogeneous cluster	Computation

3.3 DPM-based scheduling techniques

Owing to compact and fast transistor sizes in the design of CMOS circuit, it is evident that static power consumption is increasing at a fast track, and much research attention is needed to manage it. The trend towards scaling down of VLSI technology to deep sub micron level causes transistors integrated on a chip to consume substantial static power. Austin et al. [4] predicted leakage current to amount to 50 percent of total power dissipation in 90 nm technologies, thereby contributing to the majority of total energy consumption. A sharp rise in leakage currents in nanometer designs is the prime cause of power dissipation, which is causing a five-fold increase in static power consumption with each technology generation. Accordingly, static power is projected to surpass dynamic power in near future [23]. The main causes of static power consumption is due to the leakage currents flowing through a transistor, and it exists whether a processor is doing some computations or is in idle state. Before delving into survey on DPM-based techniques, an overview of the different power states of a processor are shown in Fig. 3.

For execution of an application program, the processor is considered to be in two possible states i) active-power mode, ii) low-power mode. In the former state, processor is doing normal mode of operation with full support functionality. The processor logic and embedded RAM arrays are clocked and powered on. As in active-power mode, processor is doing computations; it is also referred to be in dynamic state. Conversely, when processor is not doing any computations, because it is waiting for some communication actions to complete, it is said to in an idle state. Off-the-shelf computing systems are nowadays equipped with shutdown policies. Shutdown is a simple and effective method to save maximum amount of energy saving. However, this is in general not applicable at large scale owing to context switch constraints (shutdown and wake-up cost).

Processor supports several low-power modes namely standby, dormant, and shutdown. Such low-power states can be exploited during idle periods to reduce static power dissipation regardless of keeping the processor in idle state. In a standby state, processor clocks are disabled while still keeping the logic powered up. As a result, power drawn to leakage current reduces and a small clock power overhead is incurred to switch the processor from standby to active-power state. In dormant mode, the processor is powered off while leaving the data caches powered on. Shutdown mode is similar to dormant, but it powered off the device and all its possible states.

The second part of survey provides DPM-based scheduling techniques to address static power dissipation. Based on dynamically switching on and off the logic circuit or system components, the static power dissipation can be regulated. As a processor is equipped with several low-power modes (shutdown, standby, and dormant), its power consumption can be reduced by switching to one of these modes during idle periods. These techniques are based on three polices – timeout, predictive and stochastic optimum control [5]. In timeout policy, the component is placed in sleep mode if it remains idle for more than a defined timeout interval. The minimum idle-time that pays off the cost linked with low-power mode is known as breakeven time. In predictive policy, strategy is based on the futuristic component’s usage. This policy makes use of correlation between past history and near future workload patterns to adjudge the expected idle periods in the future course of time. The parameter of interest is to set up a time threshold that decides the transition of component from active to low-power state during unused intervals. The predicted idle periods should be long enough for efficient utilization by sleep mode. The judgment of the predicted idle periods is crucial for exploiting the maximum potency of DPM. Non-judicious calculation of idle period can lead to performance penalty or energy wastage. Predictive-based DPM policy can be further classified as adaptive and non-adaptive. In non-adaptive strategy, time threshold is fixed once and is independent of input patterns. Adaptive strategy uses past history patterns to govern future idle periods and thus changes time threshold as per the varied input patterns.

Leakage Control EDF (LC-EDF) and Leakage Control Dual Priority (LC-DP) algorithms aim to extend the idle time enough to be exploited well by sleep state [35]. However, Jejurikar and Gupta [22] found that procrastination scheduling as used in LC-DP may have the chances of deadlines miss in real time tasks. To cope up, they suggested a better technique with DVFS scheme while accounting for transition delay and energy penalty. A simple power model with only shutdown as a single low-power state is considered in their work. Baptiste [6] developed a dynamic control algorithm for aperiodic real-time events to decide when to switch on and off the devices supporting single sleep mode. For multiple low-power modes, authors presented the operating mode that a processor should enter for aperiodic real-time events and developed an on-line algorithm [2, 20]. For energy optimization, integration of DVFS and DPM as combinational approach is suggested by various researchers [20, 23, 45]. However, the integration of both DVFS and DPM in a framework poses some challenges, with a trade-off factor covering the merits and associated costs [11]. With DVFS, scaling down processor frequency reduces dynamic power consumption. Nevertheless, it also tends to elongate task execution time and less idle-time intervals in the schedule, which limits the provision of transiting processor to low-power sleep mode. On the contrary, operating processor at higher frequencies creates enough idle-times for sleep mode transition but at the price of increased processor energy consumption and more energy penalty.

Swaminathan and Chakrabarty [48] proposed DPM to control processor shutdown and wake-up of real-time events for energy savings. Coupling of voltage scaling and shutdown approach to find trade-off between DVFS, processor shutdown, and number of processors employed is realized by Langen and Juurlink [30]. Chen and Thiele [10] developed leakage-aware DVFS scheduling, wherein tasks are executed with decelerating and accelerating frequencies to initiate sleep state to reduce power consumption. However, it still makes use of simplified power model. The assumption of simplified power model and negligible transition delay has been overcome as adopted in some of the recent works [3, 18, 33]. In [3], breakeven time is computed during different low-power states, and an energy aware slack management algorithm was proposed to reduce static energy consumption of real-time tasks on uniprocessor systems. Legout et al. [33] utilized different low-power states of a processor to conserve static energy for real-time and mixed critical tasks. They relied on the use of different power states of a processor to account for transition delay and energy penalty, which were neglected in most of the prior works.

The above-mentioned algorithms have stressed upon the static energy efficiency of periodic or aperiodic real-time tasks. For precedence constrained tasks and scheduling, Ma et al. [41] discussed integration of task clustering with duplication for homogeneous clusters. They developed an Energy-Efficient Scheduling Algorithm of Data Dependent Tasks (ESTD) for DVFS-unable cluster system. The algorithm employs task clustering and duplication to reduce communication cost and then DPM strategy to reduce static energy consumption. The suggested ESTD algorithm was shown to give better performance than duplication-based EAD and PEBD for some random graphs. Kaur et al. [25] suggested Duplication-Controlled Static Energy-Efficient Scheduling (C-SEED) algorithm that couples adaptive threshold- based duplication with system level dynamic power management technique to reduce static energy consumption.

4. Conclusions

This paper surveys the state-of-the-art DVFS and DPM-based scheduling algorithms largely to address processor’s dynamic and static energy consumption. The former algorithms are surveyed for uniprocessor, and homogenous as well as heterogeneous multiprocessor systems in the context of different scheduling heuristics-list, duplication, and clustering. As analyzed, DVFS-centric scheduling algorithms were primarily focused for scheduling independent tasks on uniprocessor systems, and later on for multiprocessor systems. Much of the works target on dynamic energy consumption by means of managing processor’s active energy but overlooking idle energy consumption. Further, many list-based scheduling algorithms were explored with DVFS scheme to reduce computation energy but did not work towards reducing inter-task communication cost/delay. In addition, static/leakage and network’s communication energy is also neglected in most of the available works. Recently, energy management is carried out for duplication and clustering heuristics mainly to reduce communication energy consumption of network interconnect. As these heuristics have the potential to reduce makespan, they are being investigated on energy efficiency fronts, particularly for heterogeneous computing system. DVFS-centric algorithms are mainly utilized to reduce the processor’s dynamic energy consumption/computation energy.

Additionally, the quantum factors contributing to leakage currents are the main causes of shrinking of silicon feature sizes. Accordingly, static power dissipation is increasing more than dynamic power. DPM-based solutions are gaining importance in managing static power consumption, and are pertinent on the computing paradigms that may not be DVFS-enabled. Most of the DPM-based algorithms are restricted to real-time tasks and that too for homogeneous computing systems. Some works deal with simplified power models without consideration of transition delays and energy penalty while implementing DPM scheme. Only very limited works has facilitated to reduce static energy of dependent tasks in duplication-based schedules for off-the-shelf heterogeneous platforms. The major contribution of the survey is that it provides the trends in energy management techniques and their evolutionary roadmap at a computing platform.

Footnotes

Author’s 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 scheduling on parallel and distributed computing systems, and video forensics systems. She is guiding two Ph.D Scholars. She is available at nirmaljul19@gmail.com.
	Savina Bansal from India earned her Ph.D. from IIT Roorkee, Masters in Computers from TIET Patiala, Bachelors in Engg. from PEC Chandigarh and Bachelors in Science from Punjab University (1984). A former Dean at Maharaja Ranjit Singh Punjab Technical University, Bathinda India, she holds position of Professor at Giani Zail Singh Campus College of Engineering &Technology, Bathinda, since 2005. Her current areas of interest include energy-efficient and fault-tolerant scheduling on parallel and distributed computing systems, wireless sensor networks, image processing and wireless communication systems. She has guided 6-PhDs and currently 3-PhD scholars are working with her. She has more than 100-publications at the International level. She is available at: savina.bansal@gmail.com.
	Rakesh Kumar Bansal from India earned his Ph.D. from Punjabi University Patiala, Masters in Computers and Bachelors in Engg. (1986) both from TIET Patiala. He is a Professor at Giani Zail Singh Campus College of Engineering & Technology Bathinda, India since 2009. His areas of interest include real time fault-tolerant multiprocessor scheduling, distributed computing and wireless sensor networks. He has 60-publications at the International level. He has guided 4-Ph.Ds and 3-Ph.D. scholars are working with him presently. He is available at: drrakeshkbansal@gmail.com.

References

Hakan

Rami

Daniel

and Pedro

, Dynamic and aggressive scheduling techniques for power-aware real-time systems, in: Proceedings 22nd IEEE Real-Time Systems Symposium (RTSS 2001) (Cat. No.01PR1420), London, UK, 3–6 Dec 2001, pp. 95–105.

John

Sandy

and Chaitanya

, Optimal power-down strategies, SIAM Journal on Computing 37(5) (2008), 1499–1516.

Mohammad

and Stefan

, Enhanced Race-To-Halt: A leakage-aware energy management approach for dynamic priority systems, in: Proc. 23rd Euromicro Conference on Real-Time Systems, Porto, Portugal, 5–8 July 2011, pp. 92–101.

Todd

David

Scott

Trevor

Chaitali

and Wayne

, Mobile Supercomputers, IEEE Computer 37(5) (2004), 81–83.

, A.

, G.

,Survey of design techniques for system-level dynamic power management,IEEE Transaction on Very Large Scale Integration Systems,8(3)(2000),299–316.

Philippe

, Scheduling unit tasks to minimize the number of idle periods: A polynomial time algorithm for offline dynamic power management, in: Proc. 17𝑡ℎ Annual ACM-SIAM Symposium on Discrete Algorithm, Miami, Florida, 2006, pp. 364–367.

Sanjeev

and Rabab

A.K.

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

Sanjeev

and Kiran Kumar

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

Anantha

William

and Frank

, Design of high performance microprocessor circuits, Wiley-IEEE Press, 2000.

10.

Jian

and Lothar

, Expected system energy consumption minimization in leakage-aware DVS systems, in: Proc. International Symposium on Low Power Electronics and Design, Bangalore, India, August 2008, pp. 315–320.

11.

Vinay

and Hakan

, On the interplay of dynamic voltage scaling and dynamic power management in real-time embedded applications, in: Proc. 8th ACM International Conference on Embedded Software, Atlanta, GA, USA, 2008, pp. 99–108.

12.

Coffman

E.G.

, Computer and Job-Shop Scheduling Theory, Wiley, New York, 1976.

13.

Ian

and Carl

, The Grid 2: Blueprint for a new computing infrastructure, Morgan Kaufmann Publishers, Inc., San Francisco, CA, USA, 2003.

14.

G. D. D. and Jib-Kwon

, Essential issues in multiprocessor systems, IEEE 18(6) (1985), 9–27.

15.

Flavius

and Krzysztof

, LEneS: Task scheduling for low-energy systems using variable supply voltage processors, in: Proc. Asia and South Pacific Design Automation Conference, Yokohama, Japan, 2001, pp. 449–455.

16.

Kinshuk

Edwin

and Hal

, Comparing algorithm for dynamic speed-setting of a low-power CPU, in: Proc. 1st Annual International Conference on Mobile Computing and Networking, Berkeley, California, USA, 1995, pp. 13–25.

17.

Yiannis

, Resource and Job Management in High Performance Computing, Ph.D Thesis, Joseph Fourier University, 2010.

18.

Kai

Luca

Jian

Lothar

and Giorgio

, Applying real-time interface and calculus for dynamic power management in hard real-time systems, Real-Time Systems 47(2) (2011), 163–193.

19.

Yikun

Chubo

Kenli

Xuedi

and Keqin

, Slack allocation algorithm for energy minimization in cluster systems, Future Generation Computer Systems 74 (2017), 119–131.

20.

Sandy

Sandeep

and Rajesh

, Algorithms for power savings, ACM Transactions on Algorithms 3(4) (2007), 41.1: 41.23.

21.

Tohru

and Hiroto

, Voltage scheduling problem for dynamically variable voltage processors, in: Proc. International Symposium on Low Power Electronics and Design, California, USA, 1998, pp. 197–202.

22.

Ravindra

and Rajesh

, Procrastination scheduling in fixed priority real-time systems, in: Proc. ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, Washington, DC, USA, 2004, pp. 57–66.

23.

Ravindra

Cristiano

and Rajesh

, Leakage aware dynamic voltage scaling for real-time embedded systems, in: Proc. 41st Annual Design Automation Conference, San Diego, USA, 2004, pp. 275–280.

24.

Hideaki

Mitsuhisa

Yoshihiko

and Taisuke

, Empirical study on reducing energy of parallel programs using slack reclamation by DVFS in a power-scalable high performance cluster, in: Proc. 8th IEEE International Conference on Cluster Computing, Barcelona, Spain, 28–28

{}^{\text{th}}

September 2006, pp. 1–10.

25.

Nirmal

Savina

and Rakesh

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

26.

Nirmal

Savina

and Rakesh

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

27.

Nirmal

Savina

and Rakesh

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

28.

Nirmal

Savina

and Rakesh

, Towards energy efficient scheduling with DVFS for precedence constrained tasks on heterogeneous cluster system, in: IEEE 2𝑛𝑑 International Conference on Recent Advances in Engineering and Computational Sciences, Chandigarh, India, 21–22 December 2015, pp. 1–6.

29.

Von

K. V.

, P.

, M.

,A voltage reduction technique for battery-operated systems,IEEE Journal of Solid-State Circuits,25(5)(1990),1136–1140.

30.

Aihua

Jun

and Jiazheng

, Energy aware scheduling based on two-phase frequency scaling for parallel tasks in cluster, International Journal of Grid Distribution Computing 8(5) (2015), 205–214.

31.

Aihua

Limin

and Li

, An energy-aware dynamic clustering-based scheduling algorithm for parallel tasks on clusters, International Journal of Advancements in Computing Technology 5(5) (2013), 785–792.

32.

Pepijn

and Ben

, Trade-off between voltage scaling and processor shutdown for low-energy embedded multiprocessors, in: Proc. 7th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, Samos, Greece, 2007, pp. 75–85.

33.

Vincent

Mathieu

and Laurent

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

34.

Wei

Jing

Wei

and GuoSun

, Adaptive energy-efficient scheduling algorithm for parallel tasks on homogeneous clusters, Journal of Network and Computer Applications 41 (2014), 101–113.

35.

Yann

, R. K. P. and K. C. M., Scheduling techniques for reducing leakage power in hard real-time systems, in: Proc. 15th EuromicroConference on Real-Time Systems, Porto, Portugal, 2–4 July 2003, pp. 105–112.

36.

Young

and Albert

, Energy conscious scheduling for distributed computing systems under different operating conditions, IEEE Transactions on Parallel and Distributed Systems 22(8) (2011), 1374–1381.

37.

Young

and Albert

, Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling, in: Proc. 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, Shanghai, China, 18–21 May 2009, pp. 92–99.

38.

Ali

and Chaitali

, Variable voltage task scheduling algorithms for minimizing energy/power, IEEE Transactions on VLSI Systems 11(2) (2003), 270–276.

39.

Anil

and Anil

, An edge priority-based clustering algorithm for multiprocessor environments, Concurrency and Computation: Practice and Experience 31(4) (2018).

40.

Jing

Kenli

and Keqin

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

41.

Yan

Bin

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, Banff, Alberta, Canada, 13–15

{}^{\text{th}}

October 2009, pp. 217–224.

42.

Yan

Bin

and Zou

, Energy-optimization scheduling of task dependent graph on DVS-enabled cluster system, in: Proc of the 5𝑡ℎ Annual Chinagrid Conference, Guangzhou, China, 16–18 Jul 2010, pp. 183–190.

43.

Yuichiro

Koichi

and Toyohide

, A task selection based power-aware scheduling algorithm for applying DVS, in: International Conference on Parallel and Distributed Computing, Applications and Technologies, Higashi Hiroshima, Japan, 8–11 Dec 2009, pp. 518–523.

44.

Lars

Cees

Jens

and Kees

, Low-power operation using self-timed circuits and adaptive scaling of the supply voltage, IEEE Transactions on Very Large Scale Integration System 2(4) (1994), 391–397.

45.

Linwei

and Gang

, Reducing both dynamic and leakage energy consumption for hard real-time systems, in: Proc. International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, Washington DC, USA, 2

{}^{\text{nd}}

September 2004, pp. 140–148.

46.

Xiaojun

Xiao

Ziliang

and Kiranmai

, An energy efficient scheduling algorithm using dynamic voltage scaling for parallel applications on clusters, in: Proc. 16𝑡ℎ International Conference on Computer Communications and Networks, USA, September 2007, pp. 1–6.

47.

Amit

and Anantha

, Dynamic voltage scheduling using adaptive filtering of workload traces, in: Proc. 14th International Conference on VLSI Design, 3

{}^{\text{rd}}

January 2001.

48.

Vishnu

and Krishnendu

, Pruning-based, energy-optimal, deterministic I/O device scheduling for hard real-time systems, ACM Transactions on Embedded Computing Systems 4(1) (2005), 141–167.

49.

TOP 500 supercomputers sites, TOP500 list generated for the year 2020, https://www.top500.org/lists/top500/2020/06/.

50.

Vasanth

and Michael

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

51.

Mark

Brent

Alan

and Scott

, Scheduling for reduced CPU energy, in: Proc. 1st USENIX Conference on Operating Systems Design and Implementation, Monterey, California, 1994.

52.

Lizhe

Samee

Dan

Joanna

Rajiv

Cheng

and Albert

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

53.

Frances

Alan

and Scott

, A scheduling model for reduced CPU energy, in: Proc of 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, US, 23–25 Oct 1995, pp. 374–381.

54.

Dakai

Rami

and Bruce

, Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems, in: Proceedings 22nd IEEE Real-Time Systems Symposium, 2001, pp. 84–94. doi: 10.1109/REAL.2001.990599.

55.

Xiaomin

Rong

Jinguang

and Chuan

, 3E: Energy-efficient elastic scheduling for independent tasks in heterogeneous computing systems, Journals of Systems and Software 86(2) (2013), 302–314.

56.

Ziliang

Adam

Xiaojun

and Xiao

, EAD and PEBD: Two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters, IEEE Transactions on Computers 60(3) (2010), 360–374.

57.

Ziliang

Xiao

Xiaojun

and Kiranmai

, Energy-efficient scheduling for parallel applications running on heterogeneous clusters, in: Proc. 36𝑡ℎ International Conference on Parallel Processing, September 2007.

Survey on energy efficient scheduling techniques on cloud computing

Abstract

Keywords

1. Introduction

2.1 Preliminary on task scheduling heuristics

2.3 CMOS power consumption

2.4.1 Dynamic voltage and frequency scaling (DVFS)

2.4.2 Dynamic power management (DPM)

3. Energy efficient scheduling techniques

3.2 DVFS scheduling on multiprocessor systems

3.2.1 Energy aware list-based scheduling algorithms

Table 1 List-based scheduling heuristics with DVFS technique

Table 2 Clustering and duplication-based energy aware scheduling

4. Conclusions

Footnotes

Author’s Bios

References

Table 1
List-based scheduling heuristics with DVFS technique

Table 2
Clustering and duplication-based energy aware scheduling