多核系统中基于Global EDF 的在线节能实时调度算法

随着多核系统能耗问题日益突出,在满足时间约束条件下降低系统能耗成为多核实时节能调度研究中亟待解决的问题之一.现有研究成果基于事先已知实时任务属性的假设,而实际应用中,只有当任务到达之后才能够获得其属性.为此,针对一般任务模型,不基于任何先验知识提出一种多核系统中基于Global EDF在线节能硬实时任务调度算法,通过引入速度调节因子,利用松弛时间,结合动态功耗管理和动态电压/频率调节技术,降低多核系统中任务的执行速度,达到实时约束与能耗节余之间的合理折衷.所提出的算法仅在上下文切换和任务完成时进行动态电压/频率调节,计算复杂度小,易于在实时操作系统中实现.实验结果表明,该算法适用于不同类型的片上动态电压/频率调节技术,节能效果始终优于Global EDF算法,最多可节能15％～20％,最少可节能5％～10％.     

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.     

Power-aware scheduling for AND/OR graphs in real-time systems

Power aware computing has become popular, recently and many techniques have been proposed to manage processor energy consumption for traditional real-time applications. In this paper, we are concerned mainly with the AND/OR model of real-time applications that have different execution paths consisting of different tasks. The contribution of this paper is twofold. First, we propose a greedy slack stealing algorithm to deal with applications represented by AND/OR graphs and prove its correctness in terms of meeting the timing constraints. Then, using statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and, thus, the overhead) while ensuring that the application meets its timing constraints. Some practical issues are also considered, such as shared memory access contention and idle energy consumption. The performance of the algorithms is analyzed with respect to processor energy savings. The results surprisingly show that the greedy slack stealing scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system or when there are only a few (four to six) voltage/speed levels.     

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.     

Race-to-halt energy saving strategies

Energy consumption is one of the major issues for modern embedded systems. Early, power saving approaches mainly focused on dynamic power dissipation, while neglecting the static (leakage) energy consumption. However, technology improvements resulted in a case where static power dissipation increasingly dominates. Addressing this issue, hardware vendors have equipped modern processors with several sleep states. We propose a set of leakage-aware energy management approaches that reduce the energy consumption of embedded real-time systems while respecting the real-time constraints. Our algorithms are based on the race-to-halt strategy that tends to run the system at top speed with an aim to create long idle intervals, which are used to deploy a sleep state. The effectiveness of our algorithms is illustrated with an extensive set of simulations that show an improvement of up to 8% reduction in energy consumption over existing work at high utilization. The complexity of our algorithms is smaller when compared to state-of-the-art algorithms. We also eliminate assumptions made in the related work that restrict the practical application of the respective algorithms. Moreover, a novel study about the relation between the use of sleep intervals and the number of pre-emptions is also presented utilizing a large set of simulation results, where our algorithms reduce the experienced number of pre-emptions in all cases. Our results show that sleep states in general can save up to 30% of the overall number of pre-emptions when compared to the sleep-agnostic earliest-deadline-first algorithm.     

无线传感器网络异步任务集双效节能延迟调度算法研究

深亚微米技术的发展,使得漏电功耗在CMOS电路总功耗中所占比重日益增大,传统的传感器节点CPU节能研究主要针对动态功耗,其能耗估计和优化方法已凸显局限.针对此问题,提出动态电压调节(DVS)和动态功耗管理(DPM)相结合的双效节能延迟调度算法.从相对截止期小于等于周期的异步实时任务调度出发,结合DVS技术,综合考虑动态功耗和漏电功耗的影响,在满足任务实时性的前提下,选取每个任务的CPU执行速度,以降低总能耗,并通过任务的延迟调度对CPU空闲时段加以合并,采用DPM方法使CPU在空闲时段有选择性的进入低功耗状态,从而进一步降低漏电能耗.仿真实验验证了该算法的有效性.     

Energy efficient scheduling for real-time embedded systems with QoS guarantee

While the dynamic voltage scaling (DVS) techniques are efficient in reducing the dynamic energy consumption for the processor, varying voltage alone becomes less effective for the overall energy reduction as the static power is growing rapidly. On the other hand, Quality of Service (QoS) is also a primary concern in the development of today’s pervasive computing systems. In this paper, we propose a dynamic approach to minimize the overall energy consumption for soft real-time systems while ensuring the QoS-guarantee. The QoS requirements are deterministically quantified with the window-constraints, which require that at least m out of each non-overlapped window of k consecutive jobs of a task meet their deadlines. Necessary and sufficient conditions for checking the feasibility of task sets with arbitrary service times and periods are developed to ensure that the window-constraints can be guaranteed in the worst case. And efficient scheduling techniques based on pattern variation and dynamic slack reclaiming extensions are proposed to combine the task procrastination and dynamic slowdown to minimize the energy consumption. In contrast to the previous leakage-aware dynamic reclaiming work which never scales the job speed below the critical speed, we will show that it can be more energy efficient to reclaim the slack with speed lower than the critical speed when necessary. Through extensive simulations, our experiment results demonstrate that the proposed techniques significantly outperformed the previous research in both overall and idle energy reduction.     

Distributed dynamic pricing based on demand-supply balance and voltage phase difference in power grid

This paper discusses a distributed decision procedure for determining the electricity price for a real-time electricity market in an energy management system. The price decision algorithm proposed in this paper derives the optimal electricity price while considering the constraints of a linearized AC power grid model. The algorithm is based on the power demand-supply balance and voltage phase differences in a power grid. In order to determine the optimal price that maximizes the social welfare distributively and to improve the convergence speed of the algorithm, the proposed algorithm updates the price through the alternating decision making of market participants. In this paper, we show the convergence of the price derived from our proposed algorithm. Furthermore, numerical simulation results show that the proposed dynamic pricing methodology is effective and that there is an improvement in the convergence speed, as compared with the conventional method.     

Power and performance analysis of multimedia applications running on low-power devices by cache modeling

High processing speed is required to support computation intensive applications. Cache memory is used to improve processing speed by reducing the speed gap between the fast processing core and slow main memory. However, the problem of adopting cache into computing systems is twofold: cache is power hungry (that challenges energy constraints) and cache introduces execution time unpredictability (that challenges supporting real-time multimedia applications). Recently published articles suggest that using cache locking improves predictability. However, increased cache activities due to aggressive cache locking make the system consume more energy and become less efficient. In this paper, we investigate the impact of cache parameters and cache locking on power consumption and performance for real-time multimedia applications running on low-power devices. In this work, we consider Intel Pentium-like single-processor and Xeon-like multicore architectures, both with two-level cache memory hierarchy, using three popular multimedia applications: MPEG-4 (the global video coding standard), H.264/AVC (the network friendly video coding standard), and recently introduced H.265/HEVC (for improved video quality and data compression ratio). Experimental results show that cache locking mechanism added to an optimized cache memory structure is very promising to increase the performance/power ratio of low-power systems running multimedia applications. According to the simulation results, performance can be improved by decreasing cache miss rate down to 36 % and the total power consumption can be saved up to 33 %. It is also observed that H.265/HEVC has significant performance advantage over H.264/AVC (and MPEG-4) for smaller caches.     

多处理器环境中基于节能及容错的实时动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest task first based algorithm).通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.     

Low-Power Design for Real-Time Systems

Real-time Systems often are located in the special environments where the power consumption is a big concern. Upon presence of timing constraints, the low power design on the real-time systems has significant impact on the performance as well as the schedulability of the systems. The system developers are facing the challenges for reducing the power consumption and meeting the timing constraints in the real-time systems.This paper represents one of few attempts to address the issue of the low power design on real-time systems. We present two power reduction methods: one is at the software compilation level and the other at the operating system level. Given a real-time program, an inter-instruction power reduction technique is proposed to transform the program to another one with lower power consumption. In addition, a scheduling algorithm for real-time operating systems is proposed to reschedule real-time programs when the execution time of the programs is changed. Therefore, the proposed scheduling algorithm works together with the proposed power reduction technique to make sure all programs meet their deadlines and to improve the system schedulability. We also evaluate the performance of the proposed inter-instruction reduction method by comparing it with the cold scheduling algorithm and show that the proposed method outperforms the cold scheduling algorithm and reduces more energy power.     

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

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

Reducing power consumption of non-preemptive real-time systems

With introduction of dynamic voltage scaling techniques, promising results have been obtained for minimizing overall power consumptions of the real-time systems by exploiting the hardware characteristics of latest processors. Traditionally, preemptive systems have been investigated in depth and interesting results are established accordingly. The non-preemptive counterpart, though equally important, has received very little attention. Due to its simple implementation and lesser number of context switching, non-preemptive systems offer even more opportunities to be exploited for reducing power consumption of the system. In this paper, we establish mathematical foundations for determining the system speed appropriate to non-preemptive nature of tasks such that the timing constraints remain intact and overall power consumption is reduced. We compare our results with closely related techniques, and our analysis shows that the reduction in power consumptions is significant with proposed technique.     

Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems

In this paper, we consider the generalized power model in which the focus is the dynamic power and the static power, and we study the problem of the canonical sporadic task scheduling based on the rate-monotonic (RM) scheme. Moreover, we combine with the dynamic voltage scaling (DVS) and dynamic power management (DPM). We present a static low power sporadic tasks scheduling algorithm (SSTLPSA), assuming that each task presents its worst-case work-load to the processor at every instance. In addition, a more energy efficient approach called a dynamic low power sporadic tasks scheduling algorithm (DSTLPSA) is proposed, based on reclaiming the dynamic slack and adjusting the speed of other tasks on-the-fly in order to reduce energy consumption while still meeting the deadlines. The experimental results show that the SSTLPSA algorithm consumes 26.55–38.67% less energy than that of the RM algorithm and the DSTLPSA algorithm reduces the energy consumption up to 18.38–30.51% over the existing DVS algorithm.     

基于DVS机制的低能耗微处理器系统设计方法研究

能耗已经成为微处理器设计的最大挑战之一。微处理器的能耗在便携设备中占有重要的比例。DVS（Dynamic Voltage Scaling）机制可以在设备运行过程中,通过降低处理器的工作电压来降低它的能耗。同时,还需降低处理器的速度。电压调度程序通过分析应用的约束和需求来给定适当的工作电压。文章论述了速度和输入电压可变的微处理器系统设计方法。在处理器低速工作时,降低工作电压可以大幅度降低它的能耗。这将使应用系统能快速地根据负荷的变化调节处理器的性能。     

Optimization power consumption model of reliability-aware GPU clusters

Power controlling on reliability-aware GPU clusters with dynamically variable voltage and speed is investigated as combinatorial optimization problem, namely the problem of minimizing task execution time with energy consumption constraint and the problem of minimizing energy consumption with system reliability constraint. The two problems have applied in general multiprocessor computing and real-time multiprocessing systems where energy consumption and system reliability both are important. These problems which emphasize the trade-off among performance, power and reliability have not been well studied before. In this research, a novel power control model is built based on Model Prediction Control theory. Maximum Entropy Method is used to determine partial ordering relation of control variable and to identify the quality of solutions. Our controller can cap the redundant energy consumption by dynamically transforming energy states of the nodes in GPU cluster. We compare our controller with the control scheme, which does not consider the system reliability. The experimental results demonstrate that the proposed controller is more reliable and valuable.     

Reliability-conscious energy management for fixed-priority real-time embedded systems with weakly hard QoS-constraint

Aggressive scaling in technology size has dramatically increased the power density and degraded the reliability of real-time embedded systems. In this paper, we study the problem of reliability-conscious energy minimization for scheduling fixed-priority real-time embedded systems with weakly hard QoS-constraint. The weakly hard QoS-constraint is modeled with (m, k)-constraint, which requires that at least m out of any k consecutive jobs of a task meet their deadlines. We first propose a technique that can balance the static and dynamic energy consumption for real-time jobs with better speed determination than the classical strategies during their feasible intervals. Then based on it, we propose an adaptive fixed-priority scheduling scheme to reduce the energy consumption for the system while preserving its reliability. Through extensive simulations, our experiment results demonstrate that the proposed techniques can significantly outperform the previous research in energy performance while satisfying the weakly hard QoS-constraint under the reliability requirement.     

能量敏感实时系统能量管理分析

便携系统越来越广泛的应用使得电池使用问题日益突出。对能量敏感实时系统的能量管理进行了分析和探讨,通过对任务执行过程中的电压进行调整以减少实时任务的能量消耗,给出了能量敏感实时系统的静态能量管理和动态能量管理的分析方法,并提出了具有截止时间限制的实时任务减少能量消耗的调度机制。     

基于低阈值单元的高性能低功耗设计方法

在高性能IC设计中对高低两种阈值电压技术进行比较,利用低阈值电压降低动态功耗的手段实现降低总功耗的目标,并分析出了两种阈值电压低功耗设计各自适应的电路类型。首先对40nm工艺中标准单元的内部功耗、时序、尺寸进行分析。接着在相同延时下对高阈值和低阈值两种标准单元所设计的反相器链时序电路的功耗进行对比分析。最后基于Benchmark和AES两种类型电路,分别采用高阈值和低阈值进行综合,对比得出在相同时钟周期下更低功耗的设计所对应的阈值电压设计方式。结果显示,在相同的时钟频率下,对动态功耗占据总功耗比例极大的电路使用低阈值设计得到的功耗更低。同样,在动态功耗比例不是极大的电路中,当低阈值综合的slack为正时,以及当高阈值综合的slack为负、低阈值的slack为0时,用低阈值设计功耗更低;而当高阈值、低阈值综合的slack都为0时,用高阈值设计功耗更低。     

基于硬件剖析的DVS能耗优化

如何在满足系统性能要求的前提下尽可能降低系统能耗已成为嵌入式系统设计所面临的挑战之一。动态电压调节是降低能耗的有效技术，它能通过硬件剖析来识别“热点”，根据指令级并行(ILP)的变化情况动态调节处理器的电压和速度。实验表明该方法可在性能损失较小的情况下，有效节省能耗。