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.     

开销敏感的多处理器最优节能实时调度算法

嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.     

Energy-aware scheduling and simulation methodologies for parallel security processors with multiple voltage domains

Dynamic voltage scaling (DVS) and power gating (PG) have become mainstream technologies for low-power optimization in recent years. One issue that remains to be solved is integrating these techniques in correlated domains operating with multiple voltages. This article addresses the problem of power-aware task scheduling on a scalable cryptographic processor that is designed as a heterogeneous and distributed system-on-a-chip, with the aim of effectively integrating DVS, PG, and the scheduling of resources in multiple voltage domains (MVD) to achieve low energy consumption. Our approach uses an analytic model as the basis for estimating the performance and energy requirements between different domains and addressing the scheduling issues for correlated resources in systems. We also present the results of performance and energy simulations from transaction-level models of our security processors in a variety of system configurations. The prototype experiments show that our proposed methods yield significant energy reductions. The proposed techniques will be useful for implementing DVS and PG in domains with multiple correlated resources.     

EPTS:一种实时动态电压调整的抢占阈值调度器

低功耗目前已成为嵌入式实时系统设计中非常重要的性能需求。动态电压调度DVS机制通过动态调整处理器电压进而有效降低系统功耗,正在逐渐得到广泛应用。抢占阈值调度策略实现双优先级系统,每个任务具有两个优先级,任务优先级被用于任务之间竞争处理器,而抢占阈值作为任务开始运行后实际使用的优先级,从而减少现场切换次数,降低系统功耗,同时也提高整个任务集合的可调度性。本文提出一种在线节能调度算法EPTS,拓展抢占阈值调度模型,在任务执行过程中动态调节处理器电压,力求在保证任务集合可调度性的前提下尽可能减少系统功耗,提高系统性能。而后在AMDAthlon4处理器和RT-Linux平台上实现了EPTS调度器,实验证明对于实际任务集合能够有效节能,提高了处理器的利用率,改善了RT-Linux的实时性能。     

Hybridization of Metaheuristics Based Energy Efficient Scheduling Algorithm for Multi-Core Systems

The developments of multi-core systems (MCS) have considerably improved the existing technologies in the field of computer architecture. The MCS comprises several processors that are heterogeneous for resource capacities, working environments, topologies, and so on. The existing multi-core technology unlocks additional research opportunities for energy minimization by the use of effective task scheduling. At the same time, the task scheduling process is yet to be explored in the multi-core systems. This paper presents a new hybrid genetic algorithm (GA) with a krill herd (KH) based energy-efficient scheduling technique for multi-core systems (GAKH-SMCS). The goal of the GAKH-SMCS technique is to derive scheduling tasks in such a way to achieve faster completion time and minimum energy dissipation. The GAKH-SMCS model involves a multi-objective fitness function using four parameters such as makespan, processor utilization, speedup, and energy consumption to schedule tasks proficiently. The performance of the GAKH-SMCS model has been validated against two datasets namely random dataset and benchmark dataset. The experimental outcome ensured the effectiveness of the GAKH-SMCS model interms of makespan, processor utilization, speedup, and energy consumption. The overall simulation results depicted that the presented GAKH-SMCS model achieves energy efficiency by optimal task scheduling process in MCS.     

异构多核下兼顾应用公平性和能耗的调度方法研究

异构多核处理器通常由高性能的大核和低能耗的小核组成,在其上进行合理的线程调度可以有效地提高资源利用率,节省能耗。之前论文提出的大小核上的公平性调度并没有考虑核上有不同频率/电压状态的情况,而现在支持DVFS调节的处理器越来越普遍,因此很有必要将线程间公平度的计算进行扩展和改进。提出在每个核有若干种不同的DVFS状态时异构多核处理器上线程公平度的计算方法,对已有的性能预测模型进行改进,采用自适应算法调整模型中的系数,并在此基础上提出了一种调度策略,维持各线程之间的公平度和处理器功率满足提前设定的阈值,同时选取能效最优化的配置,实现减小应用运行能耗的目的。实验结果表明,与所提出的调度策略相比,采用static、DVFS-only、swap-only三种调度方法时,在总的运行时间几乎相同的情况下,平均要多产生20%以上能耗,对于有些应用甚至达到了50%。     

Achieving scalability in real-time systems

Running real-time applications with a variable-speed processor can result in scheduling anomalies and permanent overloads. A proposed computational model varies task response times continuously with processor speed, enabling the system to predictably scale its performance during voltage changes. Mutually exclusive resources and nonpreemptive code can generate scheduling anomalies in a processor with dynamic voltage scaling, causing tasks to increase their response times when the processor runs at higher speeds. Even worse, decreasing the speed can cause a permanent overload that degrades system performance in an uncontrolled fashion. Such problems can be efficiently handled through a set of kernel mechanisms, including cyclic asynchronous buffers and elastic scheduling that let system designers scale the performance of real-time applications as a function of processor speed. As successfully done in the SHaRK kernel, both CABs and elastic scheduling can be easily implemented on top of any real-time operating system, as a middleware layer, and they should be included in current standards to develop embedded systems with real-time and energy requirements.     

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.     

基于DVS技术的性能感知反馈调度算法

传统DVS算法在能量管理方面没有考虑实际系统性能的需求,这在一定意义上限制了其节能效果．针对这一问题,提出一种基于DVS技术的性能感知反馈调度算法．在反馈调度器中,分别采用DVS技术和模糊控制技术设计CPU电压调节模块和控制任务周期调节模块,实现对系统CPU速率和控制任务采样周期的动态调节．通过与基于固定采样周期的DVS反馈调度算法进行对比,结果表明该算法在保证系统控制性能的同时进一步降低了系统能耗．     

抢占阈值调度的功耗优化

DVS(Dynamic Voltage Scaling)技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加.延迟调度(Procrastination Scheduling)算法是近年提出用于减少静态功耗的有效方法,它通过推迟任务的正常执行来尽可能长时间地让处理器处于睡眠或关闭状态,从而避免过多的静态功耗泄露.文中针对可变电压处理器上运用抢占阈值调度策略的周期性任务集合,将节能调度和延迟调度结合起来,提出一种两阶段节能调度算法,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个任务的延迟时间,从而动态判定处理器开启/关闭时刻.实例研究和仿真实验表明,作者的方法能够进一步降低抢占阈值任务调度算法的功耗.     

Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

Dynamic Voltage Scaling for Digital Control System Implementation

For real-time computer-controlled systems, control performances of tasks as well as energy consumption of overall system must be optimized. A control task does not have a fixed period but a range of periods in which the control performance varies. Hence, when more than one control tasks are scheduled on a single processor, an optimization problem appears. Furthermore, when an energy saving technique such as dynamic voltage scaling is used, its properties affect the control performance.Using a performance index that involves control performance and energy consumption, a static solution is proposed to obtain the optimal processor speed and a set of periods for given control tasks in O(k). Also a dynamic solution is proposed to utilize system services of real-time operating systems to overcome unavoidable deficiencies of the static solution and to further reduce the energy consumption of the overall system. The performances of proposed solutions are revealed via simulation studies.Hyung Sun Lee received his B.S. and M.S. degrees in electronics engineering from Korea Advanced Institute of Science and Technology (KAIST) in 2000 and 2002, respectively. He is currently a Ph.D. student in the Department of Electrical Engineering and Computer Science (EECS) at KAIST. His research interests include real-time control and power-aware real-time embedded systems.Byung Kook Kim received his B.S. degree in Electronics Engineering from Seoul National University in 1975, and his M.S. and Ph.D. degrees from KAIST in 1977 and 1981, respectively. Dr. Kim was a manager and founder of the Calibration Laboratory, Woojin Instrument Co. Ltd, in 1981. He performed his postdoctoral research at the University of Michigan, Ann Arbor, Michigan, from 1982 to 1983. He returned to Woojin Instruments as a chief researcher of the R&D Department from 1984 to 1986. He joined the faculty of the Department of Electrical Engineering at KAIST in 1986, where he is currently a professor. His research interests include real-time systems, parallel and distributed systems, fault-tolerant computing, mobile robot sensing and navigation, and manipulator control.     

System level fixed priority energy management algorithm for embedded real time application

Dynamic power management (DPM) and dynamic voltage scaling (DVS) are crucial techniques to reduce the energy consumption in embedded real-time systems. Many previous studies have focused on the energy consumption of the processor or I/O devices. In this paper, we focus on the problem of energy management integrating DVS and DPM techniques for periodic embedded real-time applications with rate monotonic (RM) policy and present a system level fixed priority energy-efficient scheduling (SLFPEES) algorithm. The SLFPEES algorithm consists of I/O device scheduling and job scheduling. I/O device scheduling is based on the dynamic power management with rate monotonic (DPM-RM) policy which puts devices into the sleep state when the idle interval is larger than devices break even time. Job scheduling is based on the RM policy and uses stack resource protocol (SRP) to guarantee exclusive access to the shared resources. For energy efficiency, the SLFPEES algorithm schedules the task with a lower speed and a higher speed. The experimental result shows that the SLFPEES algorithm can yield significantly energy savings with respect to the existing techniques.     

Applying pinwheel scheduling and compiler profiling for power-aware real-time scheduling

Energy consumption is a critical design issue in embedded systems, especially in battery-operated systems. Maintaining high performance while extending the battery life is an interesting challenge for system designers. Dynamic voltage scaling and dynamic frequency scaling allow us to adjust supply voltage and processor frequency to adapt to the workload demand for better energy management. Because of the high complexity involved, most solutions depend on heuristics for online power-aware real-time scheduling or offline time-consuming scheduling. In this paper, we discuss how we can apply pinwheel model to power-aware real-time scheduling so that task information, including start times, finish times, preemption times, etc, can be efficiently derived using pinwheel model. System predictability is thus increased and under better control on power-awareness. However, job execution time may be only a small portion of its worst case execution time and can only be determined at runtime. We implement a profiling tool to insert codes for collecting runtime information of real-time tasks. Worst case execution time is updated online for scheduler to perform better rescheduling according to actual execution. Simulations have shown that at most 50% energy can be saved by the proposed scheduling algorithm. Moreover, at most additional 33% energy can be saved when the profiling technique is applied. This paper is an extended version of the paper Power-Aware Real-Time Scheduling using Pinwheel Model and Profiling Technique that appeared in the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.     

基于多核处理器的K线程低能耗的任务调度优化算法

针对具有独立DVFS的多核处理器系统,提出了一种K线程低能耗模型的并行任务调度优化算法(Tasks Optimization based on Energy-Effectiveness Model,TO-EEM)。与传统的并行任务节能调度相比,该算法的主要目标是不仅通过降低处理器频率来减少处理器瞬时功耗,而且结合并行任务间的同步互斥所造成的线程阻塞情况,合理分配线程资源来减少线程同步时间,优化并行性能;保证任务在一定的并行加速比性能前提下,提高资源利用率,减少能耗,达到程序能耗和性能之间的折衷。文中进行了大量模拟实验,结果证明提出的任务优化模型算法节能效果明显,能有效降低处理器的功耗,并始终保持线性加速比。     

An energy‐aware scheduling algorithm for divisible loads in a bus network

The schedule of divisible loads is one of the most typical problems in the research and application of parallel and distributed systems. For these large‐scale systems, the energy consumption problem has drawn great attention in recent years because of falling hardware costs and the growing concern of energy costs. In computing‐intensive systems, energy is primarily consumed by CPUs, and dynamic voltage‐frequency scaling technology is capable of adjusting CPUs' speed as well as saving energy. In this paper, we focus on computing‐intensive applications and study the energy‐aware scheduling problem for divisible loads in a bus network. The energy‐speed model is introduced to characterize the problem based on dynamic voltage scaling, and the energy‐aware scheduling problem is analyzed in the application layer above the operating system. The problem can be formulated mathematically as a nonlinear programming problem, and the solution is achieved using the Lagrange multiplier method under Kuhn–Tucker conditions. Based on the analytical results, an energy‐aware scheduling scheme called ENERG for divisible loads is presented. Finally, the energy‐aware scheme is compared with two other schemes to show the effectiveness and efficiency of the energy savings of our algorithm. Additionally, the experimental results illustrate the influence of network transmission delay on energy consumption. Copyright © 2015 John Wiley & Sons, Ltd.     

模型指导的多维GPU软件低功耗优化方法

作为众核体系结构的典型代表,GPU(Graphics Processing Units)芯片集成了大量并行处理核心,其功耗开销也在随之增大,逐渐成为计算机系统中功耗开销最大的组成部分之一,而软件低功耗优化技术是降低芯片功耗的有效方法.文中提出了一种模型指导的多维低功耗优化技术,通过结合动态电压/频率调节和动态核心关闭技术,在不影响性能的情况下降低GPU功耗.首先,针对GPU多线程执行模型的特点,建立了访存受限程序的功耗优化模型;然后,基于该模型,分别分析了动态电压/频率调节和动态核心关闭技术对程序执行时间和能量消耗的影响,进而将功耗优化问题归纳为一般整数规划问题;最后,通过对9个典型GPU程序的评测以及与已有方法的对比分析,验证了该文提出的低功耗优化技术可以在不影响性能的情况下有效降低芯片功耗.     

计算机控制中的模糊调度设计

研究了具有模糊截止期的多控制任务的实时调度问题,提出了奉献度的概念和最大奉献优先（LDF）的调度策略．为了减小因任务间频繁切换造成的系统开销。提出了基于抢占阈值的最大奉献优先（TLDF）调度策略．最后,通过仿真比较了LDF和TLDF两种调度策略,实现了具有模糊截止期的控制任务调度,在减少并均衡控制性能损失的同时提高系统计算资源的使用率．     

基于机器学习的异构感知多核调度方法

异构多核处理器已成为现代嵌入式系统的主流解决方案,而好的在线映射或调度方法对其充分发挥高性能和低功耗的优势起着至关重要的作用。针对异构多核处理系统上的应用程序动态映射和调度问题,提出一种基于机器学习、能快速准确评估程序性能和程序行为阶段变化的检测技术来有效确定重映射时机从而最大化系统性能的映射和调度解决方案。该方案一方面通过合理选择处理核和程序运行时的静态和动态特征来有效感知异构处理所带来的计算能力和工作负载运行行为的差异,从而能够构建更加准确的预测模型;另一方面通过引入阶段检测来尽可能减少在线映射计算的次数,从而能够提供更加高效的调度方案。最后,在SPLASH-2数据集上验证了所提出调度方案的有效性。实验结果表明,与Linux默认的完全公平调度（CFS）方法相比,所提出的方法在系统计算性能方面提高了52%,在CPU资源利用率上提高了9.4%。这表明所提方法在系统计算性能和CPU资源利用率方面具备优良的性能,可以有效提升异构多核系统的应用动态映射和调度效果。     

基于机器学习的异构感知多核调度方法

异构多核处理器已成为现代嵌入式系统的主流解决方案，而好的在线映射或调度方法对其充分发挥高性能和低功耗的优势起着至关重要的作用。针对异构多核处理系统上的应用程序动态映射和调度问题，提出一种基于机器学习、能快速准确评估程序性能和程序行为阶段变化的检测技术来有效确定重映射时机从而最大化系统性能的映射和调度解决方案。该方案一方面通过合理选择处理核和程序运行时的静态和动态特征来有效感知异构处理所带来的计算能力和工作负载运行行为的差异，从而能够构建更加准确的预测模型；另一方面通过引入阶段检测来尽可能减少在线映射计算的次数，从而能够提供更加高效的调度方案。最后，在SPLASH-2数据集上验证了所提出调度方案的有效性。实验结果表明，与Linux默认的完全公平调度（CFS）方法相比，所提出的方法在系统计算性能方面提高了52%，在CPU资源利用率上提高了9.4%。这表明所提方法在系统计算性能和CPU资源利用率方面具备优良的性能，可以有效提升异构多核系统的应用动态映射和调度效果。