Energy efficient scheduling of parallel tasks on multiprocessor computers

In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed are addressed as combinatorial optimization problems. Two problems are defined, namely, minimizing schedule length with energy consumption constraint and minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor and multicore processor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems and environments where timing constraint is a major requirement. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy-efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. Each subproblem should be solved efficiently, so that heuristic algorithms with overall good performance can be developed. The above decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. A unique feature of our work is to compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally, not to compare the performance of heuristic algorithms among themselves only experimentally. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed, and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption and that our heuristic algorithms are able to produce solutions very close to optimum.     

Performance Analysis of Power-Aware Task Scheduling Algorithms on Multiprocessor Computers with Dynamic Voltage and Speed

Task scheduling on multiprocessor computers with dynamically variable voltage and speed is investigated as combinatorial optimization problems, namely, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems where timing constraint is a major requirement. These problems emphasize the tradeoff between power and performance and are defined such that the power-performance product is optimized by fixing one factor and minimizing the other. It is found that both problems are equivalent to the sum of powers problem and can be decomposed into two subproblems, namely, scheduling tasks and determining power supplies. Such decomposition makes design and analysis of heuristic algorithms tractable. We analyze the performance of list scheduling algorithms and equal-speed algorithms and prove that these algorithms are asymptotically optimal. Our extensive simulation data validate our analytical results and provide deeper insight into the performance of our heuristic algorithms.     

一种面向同构集群系统的并行任务节能调度优化方法

节能调度算法设计是高性能计算领域中的一个研究热点.复制调度算法能够减少后继任务等待延时,缩短任务总体调度时间,但是耗费了更多的能量.为此,作者提出一种启发式处理器合并优化方法 PRO.该方法按照任务最早开始时间和最早结束时间查找处理器时间空隙,将轻负载处理器上的任务重新分配到其它处理器上,从而减少使用的处理器数目,降低系统总体能耗.实验结果表明,和已有的复制任务调度算法TDS、EAD和PEBD相比,优化后的调度算法在不增加调度时间的条件下,能够明显减少使用的处理器数和系统总体能耗,从而更好地实现性能和能耗之间的平衡.     

Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems

As the cost-driven public cloud services emerge, budget constraint is one of the primary design issues in large-scale scientific applications executed on heterogeneous cloud computing systems. Minimizing the schedule length while satisfying the budget constraint of an application is one of the most important quality of service requirements for cloud providers. A directed acyclic graph (DAG) can be used to describe an application consisted of multiple tasks with precedence constrains. Previous DAG scheduling methods tried to presuppose the minimum cost assignment for each task to minimize the schedule length of budget constrained applications on heterogeneous cloud computing systems. However, our analysis revealed that the preassignment of tasks with the minimum cost does not necessarily lead to the minimization of the schedule length. In this study, we propose an efficient algorithm of minimizing the schedule length using the budget level (MSLBL) to select processors for satisfying the budget constraint and minimizing the schedule length of an application. Such problem is decomposed into two sub-problems, namely, satisfying the budget constraint and minimizing the schedule length. The first sub-problem is solved by transferring the budget constraint of the application to that of each task, and the second sub-problem is solved by heuristically scheduling each task with low-time complexity. Experimental results on several real parallel applications validate that the proposed MSLBL algorithm can obtain shorter schedule lengths while satisfying the budget constraint of an application than existing methods in various situations.     

Sleep-aware mode assignment in wireless embedded systems

Minimizing energy consumption is a key issue in designing wireless embedded systems. While a lot of work has been done to manage energy consumption on single processor real-time systems, little work has been done in network-wide energy consumption management for real-time tasks. Existing work on network-wide energy minimization assumes that the underlying network is always connected, which is not consistent with the practice in which wireless nodes often turn off their network interfaces in a sleep schedule to reduce energy consumption. Moreover, existing sleep scheduling techniques are unaware of computation status and often lead to unnecessary wakeup overheads. In this paper, we propose solutions to minimize network-wide energy consumption for real-time tasks with precedence constraints executing on wireless embedded systems. Our solutions jointly consider the radio sleep scheduling of wireless nodes and the execution modes of processors. Based on different wireless network topologies, we propose energy management schemes to minimize energy consumption while guaranteeing the timing constraint and precedence constraint. When the precedence graph is a tree, our solution gives optimal result on energy management. The experiments show that our approach significantly reduces total energy consumption compared with previous works.     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems

The high power consumption of modern processors becomes a major concern because it leads to decreased mission duration (for battery-operated systems), increased heat dissipation, and decreased reliability. While many techniques have been proposed to reduce power consumption for uniprocessor systems, there has been considerably less work on multiprocessor systems. In this paper, based on the concept of slack sharing among processors, we propose two novel power-aware scheduling algorithms for task sets with and without precedence constraints executing on multiprocessor systems. These scheduling techniques reclaim the time unused by a task to reduce the execution speed of future tasks and, thus, reduce the total energy consumption of the system. We also study the effect of discrete voltage/speed levels on the energy savings for multiprocessor systems and propose a new scheme of slack reservation to incorporate voltage/speed adjustment overhead in the scheduling algorithms. Simulation and trace-based results indicate that our algorithms achieve substantial energy savings on systems with variable voltage processors. Moreover, processors with a few discrete voltage/speed levels obtain nearly the same energy savings as processors with continuous voltage/speed, and the effect of voltage/speed adjustment overhead on the energy savings is relatively small.     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。     

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

Scheduling in and out forests in the presence of communicationdelays

We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum     

多处理器计算环境中基于能量节约的实时动态调度算法

当前处理器由于较高的能量消耗，导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．提出的调度算法针对多处理器计算环境，以执行时间最快的任务优先调度为基础，结合其它有效技术（共享空闲时间回收），使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，提出两种针对同构计算环境的算法：STFBA1（Shortest—Task—First—Based Algorithm）及STFBA2，及两钟针对多任务集的算法HSA1（Hybrid Seheduling Algorithm）及HAS2．在单任务集计算环境下，与目前所知的有效算法相比，算法具有更好的性能（调度长度及能量消耗）．在多任务集计算环境下，基于混合调度策略的算法能够明显改进调度性能．     

异构多核处理器的任务分配及能耗的研究*

异构多核处理器采用不同的任务分配与调度算法,会导致不同的时间消耗与能量消耗,采用合适的任务分配与调度算法能节省较多的能耗。目前普遍认为最有发展前途的任务分配与调度技术是先用启发式方法进行分组,然后再用遗传算法进行调度。在改进任务分组后,又首次提出了用遗传算法解决能耗问题。实验结果表明在实时要求不高的情况下,能以较小的时间代价来节省较多的能耗。     

Reliability-aware scheduling strategy for heterogeneous distributed computing systems

Heterogeneous computing systems are promising computing platforms, since single parallel architecture based systems may not be sufficient to exploit the available parallelism with the running applications. In some cases, heterogeneous distributed computing (HDC) systems can achieve higher performance with lower cost than single-machine supersystems. However, in HDC systems, processors and networks are not failure free and any kind of failure may be critical to the running applications. One way of dealing with such failures is to employ a reliable scheduling algorithm. Unfortunately, most existing scheduling algorithms for precedence constrained tasks in HDC systems do not adequately consider reliability requirements of inter-dependent tasks. In this paper, we design a reliability-driven scheduling architecture that can effectively measure system reliability, based on an optimal reliability communication path search algorithm, and then we introduce reliability priority rank (RRank) to estimate the task’s priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG) we propose a reliability-aware scheduling algorithm for precedence constrained tasks, which can achieve high quality of reliability for applications. The comparison studies, based on both randomly generated graphs and the graphs of some real applications, show that our scheduling algorithm outperforms the existing scheduling algorithms in terms of makespan, scheduling length ratio, and reliability. At the same time, the improvement gained by our algorithm increases as the data communication among tasks increases.     

Analysis of processor allocation in multiprogrammed,distributed-memory parallel processing systems

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy     

An energy-aware scheduling algorithm under maximum power consumption constraints

This research investigates the production scheduling problems under maximum power consumption constraints. Probabilistic models are developed to model dispatching-dependent and stochastic machine energy consumption. A multi-objective scheduling algorithm called the energy-aware scheduling optimization method is proposed in this study to enhance both production and energy efficiency. The explicit consideration of the probabilistic energy consumption constraint and the following factors makes this work distinct from other existing studies in the literature: 1) dispatching-dependent energy consumption of machines, 2) stochastic energy consumption of machines, 3) parallel machines with different production rates and energy consumption pattern, and 4) maximum power consumption constraints. The proposed three-stage algorithm can quickly generate near-optimal solutions and outperforms other algorithms in terms of energy efficiency, makespan, and computation time. While minimizing the total energy consumption in the first and second stages, the proposed algorithm generates a detailed production schedule under the probabilistic constraint of peak energy consumption in the third stage. Numerical results show the superiority of the scheduling solution with regard to quality and computational time in real problems instances from manufacturing industry. While the scheduling solution is optimal in total energy consumption, the makespan is within 0.6 % of the optimal on average.     

一个调度Out-Tree任务图的启发式算法

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。     

优化能耗的可变电压禁忌任务调度算法

能耗是影响异构式并行和分布式系统性能的一个重要因素,动态电压缩放(DVS)技术通过将处理器降低到不同频率来达到有效地节约能耗的目标。通常DVS技术包含任务调度及空闲时间片分配两阶段。当前绝大部分研究均针对时间片分配阶段,而在此考虑的是任务分配与空闲时间片间的关系。为了降低异构分布式系统的能耗,提出了一个利用禁忌(Tabu)策略进行调度的DVS算法。此算法首先调度用有向无环图(DAG)表示的任务集到处理器上,再应用禁忌策略来改进它,通过禁止任务再调度到特定处理器,从而增加时间片,分配阶段可用的空闲时间片达到进一步减少能耗的目标。仿真结果表明,本算法能有效地减少计算机系统的能耗。     

一种满足可靠性和能效的云工作流调度方法

为了同步解决云工作流调度时的失效和高能耗问题,提出一种基于可靠性和能效的工作流调度算法.算法为了在截止时间的QoS约束下最大化系统可靠性并最小化调度能耗,将工作流调度过程划分为四个阶段:计算任务优先级、工作流任务聚簇、截止时间子分配和任务调度.算法在满足执行次序的情况下对任务进行拓扑排序,并以通信代价最小为目标对任务进...     

Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks

A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of nindependent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed ε > 0 , computes in O(n)time a non-preemptive schedule of length at most (1+ε)times the optimum.