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

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

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.     

用于多核嵌入式环境的硬实时任务感功调度算法

充分考虑当前CMOS多核嵌入式处理器片上仅提供全局动态电压缩放(DVS)支持以及亚纳米时代后CMOS处理器泄露功耗不可忽视的现状,提出一种新的多核嵌入式环境中的硬实时任务感功调度算法GRR&CS。算法通过基于贪心法的静态任务划分,基于全局资源回收利用和任务迁移的动态负载均衡,以及动态核缩放三个步骤实现整体能耗的降低,并同时保证实时任务的可调度性约束。实验表明,提出的算法相比较现有算法多节省14.8%~41.2%的能耗。     

抢占阈值调度的功耗优化

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

WSN软实时系统的DVS控制优化算法

为降低无线传感器网络（WSN）软实时系统中的能量消耗,建立能量消耗数学模型,引入离散事件系统框架中的优化控制问题使目标函数最小化,采用线性规划方法求解,得到一种可扩展的低复杂度算法,并对该算法进行优化。数值结果表明,应用优化算法对WSN节点进行动态电压调节,能在满足时限要求的基础上更大程度地节省节点能量。     

基于软实时多处理器系统的动态低功耗算法

结合DVS技术和(m,k)-firm模型，提出一个保证完成率、适用于软实时多电压多处理器系统中有依赖关系任务集的动态低功耗算法VAP_DY。该算法权衡应用的性能需求、执行时间的不确定性和系统对合理执行失败的容忍来动态调整每个处理器运行时的供电电压,以降低多处理器系统的总功耗。分析和实验结果表明，VAP_DY能够在保证时间和完成率约束的条件下有效降低系统功耗。     

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.     

Slack allocation algorithm for parallel machines

Energy consumption is a critical issue in parallel and distributed embedded systems. We present a novel algorithm for energy efficient scheduling of Directed Acyclic Graph (DAG) based applications on Dynamic Voltage Scaling (DVS) enabled systems. Experimental results show that our algorithm provides near optimal solutions for energy minimization with considerably smaller computational time and memory requirements compared to an existing algorithm that provides near optimal solutions.     

基于能量消耗模型的WSN动态电压调节算法

为了降低WSN中弱硬实时系统的能量消耗,应用离散事件系统（DES）框架中的优化原理,建立数学模型,得到了能量消耗的目标函数,为了最小化目标函数,利用线性规划方法进行求解,得到一种可扩展的低复杂度算法来进行动态电压调节（DVS）。并对算法进行了模型实例计算,结果表明,优化的DVS算法能在满足弱硬实时系统时限要求的基础上更大程度节省节点能量。     

可重构系统功耗相关的硬件任务调度算法

面向可重构系统,提出了一种功耗相关的硬件任务调度算法（Energy—Efficient HardwareTask Schedu—ling,EEHTS）。动态电压调整（DynamicVoltage Scaling,DVS）技术通过在软件任务运行时动态改变CPU的运行电压而降低系统功耗。类似地,EEHTS算法在硬件任务调度时动态改变FPGA的工作频率,达到降低功耗的目的。模拟实验结果表明,EEHTS算法在不影响硬件任务截止期要求的前提下,可以有效降低系统功耗。     

Energy- and reliability-aware task scheduling onto heterogeneous MPSoC architectures

Scheduling periodic tasks onto a multiprocessor architecture under several constraints such as performance, cost, energy, and reliability is a major challenge in embedded systems. In this paper, we present an Integer Linear Programming (ILP) based framework that maps a given task set onto an Heterogeneous Multiprocessor System-on-Chip (HMPSoC) architecture. Our framework can be used with several objective functions; minimizing energy consumption, minimizing cost (i.e., the number of heterogeneous processors), and maximizing reliability of the system under performance constraints. We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to maximize reliability. We illustrate the effectiveness of our approach through several experiments, each with a different number of tasks to be scheduled. We also propose two heuristics based on Earliest Deadline First (EDF) algorithm for minimizing energy under performance and cost constraints. Our experiments on generated task sets show that ILP-based method reduces the energy consumption up to 62% percent against a method that does not apply DVS. Heuristic methods obtain promising results when compared to optimal results generated by our ILP-based method.     

一种基于同构多核处理器的动态节能调度算法

在节能计算系统中节能调度是一个重要的研究方向。目前针对节能调度的研究中,多从动态电压频率调节（DVFS）的角度进行。但是随着芯片制造工艺的改进,处理器核心电压越来越低,所能调节的电压范围越来越小,通过DVFS技术实现节能遇到了理论上的瓶颈。提出了一种基于同构多核处理器的动态节能调度算法。在系统负载较轻的情况下,通过将系统任务分配到较少的处理核心上而使其他处理核心处于休眠状态来达到动态节能的效果。实验表明该算法具有较好的节能效果。     

硬实时混合任务在线节能调度技术分析

对混合实时任务节能调度技术进行了分析,深入探讨了目前优秀的硬实时系统在线节能调度算法(OLDVS),指出其存在不足的原因 ,即松弛时间丢失和松弛时间转移。为了提高其节能效果,给出了多种改进思路,为进一步研究工作做出有益的探索。     

一个基于资源操作的强实时动态调压算法

动态调压算法能够降低系统功耗，可用来降低CPU发热量、延长电池供电系统的工作时间．然而，现有动态调压算法均不允许进程进行资源操作（申请或释放资源），这在实际应用中是难以满足的．因此，现有算法不便于实际应用,本文提出了一种新的强实时动态调压算法．该算法允许进程进行资源操作，并且功耗低于现有算法；该算法还能避免死锁．该算法易于应用到实际系统中．     

无线传感器网络中的动态电压调节算法

无线传感器节点一般由电池供电,且电池不易更换,所以传感器网络最关注的问题是如何高效地利用有限的能量.动态电压调节技术允许软件在运行时动态的改变处理器的频率和电压,以减少它的能量消耗.分析了现有的一些动态电压调节算法,根据无线传感器网络多跳路由和拓扑易变化的特点,提出了一种针对中继节点的动态电压调节算法,并在NS2平台上对算法进行了仿真.通过对仿真结果的分析,表明改进的算法能够很好地减少系统能量消耗,延长无线传感器网络的使用寿命.     

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

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

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

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

Performance evaluation and energy consumption of a real-time heterogeneous grid system using DVS and DPM

Energy consumption of large scale systems has been severely studied due to economic and ecological reasons. This paper studies energy gains that come from the application of two popular energy saving techniques, Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM), in a real-time 2-level heterogeneous grid system. While these techniques generally work in a competitive way, we show that under certain circumstances they can work together and achieve greater savings when they are both applied at the processor level. A simulation model is used to evaluate the performance of the system. Experimental results show encouraging energy savings up to 46% and minimum performance degradation when both energy saving techniques are applied.     

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

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

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

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