Hard real-time tasks' scheduling considering voltage scaling, precedence and exclusion relations

Several scheduling approaches have been developed to address DVS in time-critical systems, however, overheads, precedence and exclusion relations have been neglected. This paper presents a pre-runtime scheduling method for hard real-time systems considering DVS, overheads as well as inter-task relations. The proposed method adopts a formal model based on time Petri nets in order to find a feasible schedule that satisfies timing and energy constraints.     

基于Markov模型的动态电压调节策略

基于Markov模型,针对具有离散工作电压模式的处理器提出了一种动态电压调节策略MKBVSP（Markov based voltage scaling policy）。MKBVSP能够根据工作负载的需求变化实现处理器工作模式的动态切换,达到系统性能与能耗之间的平衡。实验结果表明,MKBVSP策略能够在更大程度上降低系统平均能耗,最大比率可达58%。     

Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling

Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to exploit multiple voltage and frequency levels and to prolong their battery life. However, pure DVS techniques do not perform well for systems with dynamic workloads where the job execution times vary significantly. In this paper, we present a novel approach combining feedback control with DVS schemes targeting hard real-time systems with dynamic workloads. Our method relies strictly on operating system support by integrating a DVS scheduler and a feedback controller within the earliest-deadline-first (EDF) scheduling algorithm. Each task is divided into two portions. The objective within the first portion is to exploit frequency scaling for the average execution time. Static and dynamic slack is accumulated for each task with slack-passing and preemption handling schemes. The objective within the second portion is to meet the hard real-time deadline requirements up to the worst-case execution time following a last-chance approach. Feedback control techniques make the system capable of selecting the right frequency and voltage settings for the first portion, as well as guaranteeing hard real-time requirements for the overall task. A feedback control model is given to describe our feedback DVS scheduler, which is used to analyze the system's stability. Simulation experiments demonstrate the ability of our algorithm to save up to 29% more energy than previous work for task sets with different dynamic workload characteristics. This work was supported in part by NSF grants CCR-0208581, CCR-0310860 and CCR-0312695. Preliminary versions of parts of this work appeared in the ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02) (Dudani et al., 2002), in the Workshop on Compilers and Operating Systems for Low Power 2002 (Zhu and Mueller, 2002) and in the IEEE Real-Time Embedded Technology and Applications Symposium 2004 (Zhu and Mueller, 2004a).     

针对离散电压处理器的动态电压调节策略

嵌入式系统设计者在以往设计过程中,通常只考虑到系统的稳定性、实时性等,但现在却面临着一个新的挑战降低系统的功耗.基于LP线性规划模型,针对具有离散工作电压模式的处理器提出了一种动态电压调节策略LPBVSP(LP based voltage scaling policy).LPBVSP能够根据工作负载的需求变化实现处理器...     

A DVS-assisted hard real-time I/O device scheduling algorithm

The I/O subsystem has become a major source of energy consumption in a hard real-time monitoring and control system. To reduce its energy consumption without missing deadlines, a dynamic power management (DPM) policy must carefully consider the power parameters of a device, such as its break-even time and wake-up latency, when switching off idle devices. This problem becomes extremely complicated when dynamic voltage scaling (DVS) is applied to change the execution time of a task. In this paper, we present COLORS, a composite low-power scheduling framework that includes DVS in a DPM policy to maximize the energy reduction on the I/O subsystem. COLORS dynamically predicts the earliest-access time of a device and switches off idle devices. It makes use of both static and dynamic slack time to extend the execution time of a task by DVS, in order to create additional switch-off opportunities. Task workloads, processor profiles, and device characteristics all impact the performance of a low-power real-time algorithm. We also identify a key metric that primarily determines its performance. The experimental results show that, compared with previous work, COLORS achieves additional energy reduction up to 20%, due to the efficient utilization of slack time.

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

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

Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters

Developing energy-efficient clusters not only can reduce power electricity cost but also can improve system reliability. Existing scheduling strategies developed for energy-efficient clusters conserve energy at the cost of performance. The performance problem becomes especially apparent when cluster computing systems are heavily loaded. To address this issue, we propose in this paper a novel scheduling strategy–adaptive energy-efficient scheduling or AEES–for aperiodic and independent real-time tasks on heterogeneous clusters with dynamic voltage scaling. The AEES scheme aims to adaptively adjust voltages according to the workload conditions of a cluster, thereby making the best trade-offs between energy conservation and schedulability. When the cluster is heavily loaded, AEES considers voltage levels of both new tasks and running tasks to meet tasks’ deadlines. Under light load, AEES aggressively reduces the voltage levels to conserve energy while maintaining higher guarantee ratios. We conducted extensive experiments to compare AEES with an existing algorithm–MEG, as well as two baseline algorithms–MELV, MEHV. Experimental results show that AEES significantly improves the scheduling quality of MELV, MEHV and MEG.     

基于小波的DVS在无线传感器网络中的应用*

为了最大限度节约能源的使用,使无线传感器网络使用寿命延长,针对无线传感器网络的节点在运行状态提出了基于小波的动态电压调度(DVS)算法.该方法首先通过使用小波、Kalman和AR三种算法相结合对下一任务量进行预测,并根据预测结果判断处理器(使用SA-1100处理器)进入何种操作频率等级(处理器的工作电压与操作频率一一对应),使较小任务量进入较小操作频率等级的状态,从而减少了节点在周期内的能量消耗.仿真实验结果表明,该方法是有效的.     

Energy efficient scheduling of real-time tasks on multi-core processors with voltage islands

This paper studies energy efficient scheduling of periodic real-time tasks on multi-core processors with voltage islands, in which cores are partitioned into multiple blocks (termed voltage islands) and each block has its own power source to supply voltage. Cores in the same block always operate at the same voltage level, but can be adjusted by using Dynamic Voltage and Frequency Scaling (DVFS). We propose a Voltage Island Largest Capacity First (VILCF) algorithm for energy efficient scheduling of periodic real-time tasks on multi-core processors. It achieves better energy efficiency by fully utilizing the remaining capacity of an island before turning on more islands or increasing the voltage level of the current active islands. We provide detailed theoretical analysis of the approximation ratio of the proposed VILCF algorithm in terms of energy efficiency. In addition, our experimental results show that VILCF significantly outperforms the existing algorithms when there are multiple cores in a voltage island.     

一种基于EDF算法的多处理器实时调度算法

多处理器系统实时调度理论是目前实时系统研究的热点问题。EDF调度算法是目前流行的实时调度算法,有很多优点,但在多处理器系统应用中存在问题。论文研究了EDF调度算法在多处理器系统中的调度理论,在此基础上,提出了一种基于EDF算法的优先级驱动实时调度算法,算法充分利用了EDF调度算法的优点,较大程度地克服了EDF算法在多处理器系统中的调度缺点,并提供了较好的实时调度性能。     

Reducing energy consumption of parallel sparse matrix applications through integrated link/CPU voltage scaling

Reducing power consumption is quickly becoming a first-class optimization metric for many high-performance parallel computing platforms. One of the techniques employed by many prior proposals along this direction is voltage scaling and past research used it on different components such as networks, CPUs, and memories. In contrast to most of the existent efforts on voltage scaling that target a single component (CPU, network or memory components), this paper proposes and experimentally evaluates a voltage/frequency scaling algorithm that considers CPU and communication links in a mesh network at the same time. More specifically, it scales voltages/frequencies of CPUs in the nodes and the communication links among them in a coordinated fashion (instead of one after another) such that energy savings are maximized without impacting execution time. Our experiments with several tree-based sparse matrix computations reveal that the proposed integrated voltage scaling approach is very effective in practice and brings 13% and 17% energy savings over the pure CPU and pure communication link voltage scaling schemes, respectively. The results also show that our savings are consistent with the different network sizes and different sets of voltage/frequency levels.

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.     

Slack computation for DVS algorithms in fixed-priority real-time systems using fluid slack analysis

This work presents a scheduling algorithm to reduce the energy of hard real-time tasks with fixed priorities assigned in a rate-monotonic policy. Sets of independent tasks running periodically on a processor with dynamic voltage scaling (DVS) are considered as well. The proposed online approach can cooperate with many slack-time analysis methods based on low-power work demand analysis (lpWDA) without increasing the computational complexity of DVS algorithms. The proposed approach introduces a novel technique called low-power fluid slack analysis (lpFSA) that extends the analysis interval produced by its cooperative methods and computes the available slack in the extended interval. The lpFSA regards the additional slack as fluid and computes its length, such that it can be moved to the current job. Therefore, the proposed approach provides the cooperative methods with additional slack. Experimental results show that the proposed approach combined with lpWDA-based algorithms achieves more energy reductions than do the initial algorithms alone.     

面向同构多核处理器的节能任务调度方法

对于运行在同构多核处理器上的周期性硬实时任务,设计了一个基于动态电压调节的节能调度方法。该方法首先将计算任务按照周期数降序排序并基于计算任务调度长度最短的原则安排任务映射。然后将各个处理核上具有最小通讯时间的计算任务设置为最后执行的计算任务而其它计算任务顺序保持不变。在初始映射中所有计算任务都被分配最高频率的情况下,每个处理核上的计算任务在执行时间扩展过程中确定最佳的计算任务顺序。基于 Intel PXA270的功耗模型,以几个随机任务集作实验。结果表明提出的方法能够有效地降低多核处理器的能量。     

功耗管理中的动态电压调整综述

综述了十年来动态电压调整的相关文献,对各种策略进行分类介绍;对DVS问题的数学模型进行提炼,抽象出它们解决问题的思路,评价它们的优缺点,并简述典型策略的实现。     

基于辅助队列的硬实时混合任务节能调度算法

节能调度是当今实时系统研究的一个重要领域,其中混合实时任务节能调度技术研究刚刚起步.OLDVS算法是非常简洁的硬实时系统在线节能调度算法,但存在以下不足:不适应任务执行的动态变化,不能有效利用动态松弛时间,过于保守以致节能效果并不理想.据此,提出一种新的基于辅助队列的硬实时混合任务节能调度算法(OLDVS-AQ).通过引入一个额外的数据结构即辅助队列(Assisted Queue,AQ)来计算任务的最大完成时间,能够更有效地利用动态松弛时间进一步降低能耗.证明了该算法的可调度性,仿真实验结果表明,OLDVS-AQ算法始终优于OLDVS算法.平均提高约10%的节能效果.     

Energy-aware task migration for multiprocessor real-time systems

A task migration method is proposed for energy savings in multiprocessor real-time systems. The method is based on the portioned scheduling technique which classifies each task as a fixed task or a migratable task. The basic task migration problem with specific parameters is formulated as a linear programming problem to minimize average power. Then, the method is extended to more general case with a complete migration algorithm. Moreover, a scheduling algorithm is proposed for migratable tasks. Simulation results on two processor models demonstrated significant energy savings over existing methods.     

适合无线传感器网络的自适应动态电压调节算法*

对于能量有限的传感器网络,在计算复杂度较高的应用中,节省CPU的能耗具有重要意义。针对以事件为驱动的无线传感器网络的任务模式,提出一种基于零散任务模型的自适应DVS算法——ADVS。ADVS算法根据CPU的任务量实时调整工作频率和电压,能在很大程度上降低CPU能耗的同时,保证任务的实时性要求。理论分析和实验结果表明,ADVS算法的实际节能效果接近理论分析值的80%左右,可在很大程度上延长节点的生命周期。     

Power-aware scheduling algorithms for sporadic tasks in real-time systems

In this paper, we consider the canonical sporadic task model with the system-wide energy management problem. Our solution uses a generalized power model, in which the static power and the dynamic power are considered. We present a static solution to schedule the sporadic task set, assuming worst-case execution time for each sporadic tasks release, and propose a dynamic solution to reclaim the slacks left by the earlier completion of tasks than their worst-case estimations. The experimental results show that the proposed static algorithm can reduce the energy consumption by 20.63%–89.70% over the EDF* algorithm and the dynamic algorithm consumes 2.06%–24.89% less energy than that of the existing DVS algorithm.     

无线传感器网络动态电压调度算法

针对无线传感器网络的节点在运行状态提出了动态电压调度(DVS)算法。DVS是通过改变处理器的工作电压和工作频率来减少处理器的消耗能量。该方法首先必须对节点各部分发出的信号进行分析和预测,并根据预测后的信号对处理器设定处理速率,最后,设定合适的工作电压和工作频率。