基于多核处理器的节能任务调度方法

由于关系到系统的安全性及散热代价等方面,能耗问题已经成为嵌入式系统研究的重点。对于多核处理器上具有依赖关系的周期性硬实时任务,设计了一种基于动态电压调节的节能任务调度方法。该方法首先用RDAG算法将任务独立化,然后以功耗最低为原则,采用遗传算法确定任务映射。基于Intel PXA270功耗模型,采用了几个随机任务集进行仿真实验,结果表明该方法比现有的方法节省了20%～30%的能耗。     

Energy Efficient Real-Time Task Scheduling for Embedded Systems with Hybrid Main Memory

Available energy becomes a critical design issue for the increasingly complex real-time embedded systems. Phase Change Memory (PCM), with high density and low idle power, has recently been extensively studied as a promising alternative of DRAM. Hybrid PCM-DRAM main memory architecture has been proposed to leverage the low power of PCM and high speed of DRAM. In this paper, we propose energy-aware real-time task scheduling strategies for hybrid PCM-DRAM based embedded systems. Given the execution time variation when a task is loaded into PCM or DRAM, we re-design the static table-driven scheduling for a set of fixed tasks, as well as the Rate-Monotonic (RM) and Earliest Deadline First (EDF) scheduling policies for periodic task sets. Furthermore, since the actual execution time can be much shorter than the worst-case execution time in the actual execution, we propose online schedulers which migrates the tasks between PCM and DRAM to optimize the energy consumption by utilizing the slack time resulted from the completed tasks. All the proposed algorithms minimize the number of task migrations from PCM to DRAM by ensuring that aperiodic tasks are not migrated while each periodic task instance can be migrated at most once. Experimental results show our proposed scheduling algorithms satisfy the real-time constraints and significantly reduce the energy consumption.     

Simultaneous Dynamic Voltage Scaling of Processors and Communication Links in Real-Time Distributed Embedded Systems

Dynamic voltage scaling has been widely acknowledged as a powerful technique for trading off power consumption and delay for processors. Recently, variable-frequency (and variable-voltage) parallel and serial links have also been proposed, which can save link power consumption by exploiting variations in the bandwidth requirement. This provides a new dimension for power optimization in a distributed embedded system connected by a voltage-scalable interconnection network. At the same time, it imposes new challenges for variable-voltage scheduling as well as flow control. First, the variable-voltage scheduling algorithm should be able to trade off the power consumption and delay jointly for both processors and links. Second, for the variable-frequency network, the scheduling algorithm should not only consider the real-time constraints, but should also be consistent with the underlying flow control techniques. In this paper, we address joint dynamic voltage scaling for variable-voltage processors and communication links in such systems. We propose a scheduling algorithm for real-time applications that captures both data flow and control flow information. It performs efficient routing of communication events through multihops, as well as efficient slack allocation among heterogeneous processors and communication links to maximize energy savings, while meeting all real-time constraints. Our experimental study shows that on an average, joint voltage scaling on processors and links can achieve 32% less power compared with voltage scaling on processors alone     

Real-time multimedia processing in video sensor networks

Video sensor networks (VSNs) has become the recent research focus due to the rich information it provides to address various data-hungry applications. However, VSN implementations face stringent constraints of limited communication bandwidth, processing capability, and power supply. In-network processing has been proposed as efficient means to address these problems. The key component of in-network processing, task mapping and scheduling problem, is investigated in this paper. Although task mapping and scheduling in wired networks of processors has been extensively studied, their application to VSNs remains largely unexplored. Existing algorithms cannot be directly implemented in VSNs due to limited resource availability and shared wireless communication medium. In this work, an application-independent task mapping and scheduling solution in multi-hop VSNs is presented that provides real-time guarantees to process video feeds. The processed data is smaller in volume which further releases the burden on the end-to-end communication. Using a novel multi-hop channel model and a communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously with a dynamic critical-path scheduling algorithm. Dynamic voltage scaling (DVS) mechanism is implemented to further optimize energy consumption. According to the simulation results, the proposed solution outperforms existing mechanisms in terms of guaranteeing application deadlines with minimum energy consumption.     

一种新的嵌入式Linux实时调度算法

针对现有实时调度算法在实时性能上的不足,提出了一种新的实时任务分类调度算法,根据实时任务的到达情况进行分类,划分为周期任务和非周期任务,并对不同类型的实时任务使用不同的改进的实时调度算法.通过实验,证明此算法与现有实时调度算法相比,综合实时性能有了很大程度的提高.     

Energy efficient semi-partitioned scheduling for embedded multiprocessor streaming systems

In this paper, we study the problem of energy minimization when mapping streaming applications with throughput constraints to homogeneous multiprocessor systems in which voltage and frequency scaling is supported with a discrete set of operating voltage/frequency modes. We propose a soft real-time semi-partitioned scheduling algorithm which allows an even distribution of the utilization of tasks among the available processors. In turn, this enables processors to run at a lower frequency, which yields to lower energy consumption. We show on a set of real-life applications that our semi-partitioned scheduling approach achieves significant energy savings compared to a purely partitioned scheduling approach and an existing semi-partitioned one, EDF-os, on average by 36 % (and up to 64 %) when using the lowest frequency which guarantees schedulability and is supported by the system. By using a periodic frequency switching scheme that preserves schedulability, instead of this lowest supported fixed frequency, we obtain an additional energy saving up to 18 %. Although the throughput of applications is unchanged by the proposed semi-partitioned approach, the mentioned energy savings come at the cost of increased memory requirements and latency of applications.     

动态电压调整多处理器实时系统任务调度

动态电压调整DVS（Dynamic Voltage Scaling）是根据处理器电压（速度）降低之后，能量消耗平方级的减少这一原理提出的。文章通过DVS机制在多处理器实时系统中进行任务调度．通过对任务调度中的静态能量管理进行分析，在此基础上提出了一种新的基于DVS的适用于多处理器实时系统中的调度算法。这种新的调度算法是通过对贪婪法调度进行研究，发现其不足．并以此为基础进行改进。结合了动态电压调整的多处理器实时系统任务调度的能量消耗比普通的任务调度能量消耗有了很大的改善。     

基于MrsP协议的任务划分优化算法

多处理器实时系统中,调度和资源共享是核心问题,与之相对应的调度算法和共享资源访问协议将直接影响系统的性能,这就要求调度算法和资源访问协议在保证实时性的基础上尽量发挥硬件平台的计算能力。然而,现有的调度算法多假设任务相互独立,没有考虑任务之间的资源共享,共享资源访问协议也多侧重于规则和最坏响应时间分析。对此,将P-RM算法和MrsP协议相结合,得出了多处理器实时系统的整体可调度性条件。文中根据MrsP协议的特性,提出了一种减小阻塞时间的任务划分算法,通过改进任务利用率的计算方式解决了关键区重复计算的问题,与之前的任务划分算法相比,也解决了关键区重复计算以及任务分类后拆分再分配的问题。实验表明,该算法所需要的处理器数目减少了15%~20%。     

Elastic DVS Management in Processors With Discrete Voltage/Frequency Modes

Applying classical dynamic voltage scaling (DVS) techniques to real-time systems running on processors with discrete voltage/frequency modes causes a waste of computational resources. In fact, whenever the ideal speed level computed by the DVS algorithm is not available in the system, to guarantee the feasibility of the task set, the processor speed must be set to the nearest level greater than the optimal one, thus underutilizing the system. Whenever the task set allows a certain degree of flexibility in specifying timing constraints, rate adaptation techniques can be adopted to balance performance (which is a function of task rates) versus energy consumption (which is a function of the processor speed). In this paper, we propose a new method that combines discrete DVS management with elastic scheduling to fully exploit the available computational resources. Depending on the application requirements, the algorithm can be set to improve performance or reduce energy consumption, so enhancing the flexibility of the system. A reclaiming mechanism is also used to take advantage of early completions. To make the proposed approach usable in real-world applications, the task model is enhanced to consider some of the real CPU characteristics, such as discrete voltage/frequency levels, switching overhead, task execution times nonlinear with the frequency, and tasks with different power consumption. Implementation issues and experimental results for the proposed algorithm are also discussed     

Peak Temperature Minimization via Task Allocation and Splitting for Heterogeneous MPSoC Real-Time Systems

With the continued scaling of the CMOS devices, the exponential increase in power density has strikingly elevated the temperature of on-chip systems. Thus, thermal-aware design has become a pressing research issue in computing system, especially for real-time embedded systems with limited cooling techniques. In this paper, the authors formulate the thermal-aware real-time multiprocessor system-on-chip (MPSoC) task allocation and scheduling problem, present a task-to-processor assignment heuristics that improves the thermal profiles of tasks, and propose a task splitting policy that reduces the on-chip peak temperature. The thermal profiles of tasks are improved via task mapping by minimizing task steady state temperatures, and the task splitting technique is applied to reduce the peak temperature by enabling the alternation of hot task execution and slack time. The proposed algorithms explicitly exploits thermal characteristics of both tasks and processors to minimize the peak temperature without incurring significant overheads. Extensive simulations of benchmarking tasks were performed to validate the effectiveness of the proposed algorithms. Experimental results have shown that the task steady state temperature achieved by the proposed algorithm is 3.57 °C lower on average as compared to the benchmarking schemes, and the peak temperature of the proposed algorithm can be up to 11.5 % lower than that of the benchmarking schemes     

一种雷达信号处理多任务调度算法

雷达信号处理(RSP)系统的实时性一直是系统设计者需要重点考虑的内容之一。为提高雷达系统的实时性,本文提出了一种基于多模式雷达的RSP任务模型,并根据DP-Wrap算法和流水处理的思想提出了一种高效的任务调度算法。研究了在本模型下影响系统最小处理时间的因素,给出了系统最小处理时间的精确表达式,并在此基础上进行数值仿真,给出了根据RSP任务选择处理器个数的依据。     

硬实时系统中基于任务同步及节能的动态调度算法

提出基于任务同步及节能的动态实时调度算法HDSA(hybrid dynamic scheduling algorithm),以有效地解决任务同步及节能的难题.HDSA 结合RM及EDF算法,在满足任务实时可调度性及任务同步的限制条件下,采用DVFS节省能耗.HDSA包含静态算法及动态算法两部分.静态算法在静态条件下,求出任务的静态速度.动态调度算法在实际运行中,固定临界区的运行速度,并充分回收、利用任务运行时的空闲执行时间,调节处理器的速度,以有效降低能耗并满足实时可调度性.同时避免高优先权任务被阻塞时,临界区继承高优先权任务的速度时所造成的处理器电压开关的频繁切换,因而能有效地降低实时任务调度的成本.实验测试表明,HDSA在调度性能上明显优于目前所知的有效算法.     

针对弱硬实时系统的DRM调度算法

本文在定义支持多级QoS的弱硬实时系统周期任务模型的基础上,提出基于RM调度策略的弱硬实时调度算法DRM,它具备可调度判定不等式,不限定任务的QoS参数模式,并通过在调度的过程中动态调整任务的优先级来反映其紧迫程度.在系统过载时,DRM调度算法可以采用QoS退化机制,在保证紧要任务以及其所要求的最低QoS执行的同时,适当降低某些任务的服务等级,使得更多的任务可以有效运行,以此来提高系统对负载的适应性.最后,本文通过仿真实验,验证了DRM以及QoS退化机制的有效性.     

Synthesis of Hard Real-Time Application Specific Systems

This paper presents a system level approach for the synthesis of hard real-time multitask application specific systems. The algorithm takes into account task precedence constraints among multiple hard real-time tasks and targets a multiprocessor system consisting of a set of heterogeneous off-the-shelf processors. The optimization goal is to select a minimal cost multi-subset of processors while satisfying all the required timing and precedence constraints. There are three design phases: resource allocation, assignment, and scheduling. Since the resource allocation is a search for a minimal cost multi-subset of processors, we adopted an A* search based technique for the first synthesis phase. A variation of the force-directed optimization technique is used to assign a task to an allocated processor. The final scheduling of a hard-real time task is done by the task level scheduler which is based on Earliest Deadline First (EDF) scheduling policy. Our task level scheduler incorporates force-directed scheduling methodology to address the situations where EDF is not optimal. The experimental results on a variety of examples show that the approach is highly effective and efficient.     

Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded Systems

In this paper, we combine coarse-grained software pipelining with DVS (Dynamic Voltage/Frequency Scaling) for optimizing energy consumption of stream-based multimedia applications on multi-core embedded systems. By exploiting the potential of multi-core architecture and the characteristic of streaming applications, we propose a two-phase approach to solve the energy minimization problem for periodic dependent tasks on multi-core processors with discrete voltage levels. With our approach, in the first phase, we propose a coarse-grained task-level software pipelining algorithm called RDAG to transform the periodic dependent tasks into a set of independent tasks based on the retiming technique (Leiserson and Saxe, Algorithmica 6:5–35, 1991). In the second phase, we propose two DVS scheduling algorithms for energy minimization. For single-core processors, we propose a pseudo-polynomial algorithm based on dynamic programming that can achieve optimal solution. For multi-core processors, we propose a novel scheduling algorithm called SpringS which works like a spring and can effectively reduce energy consumption by iteratively adjusting task scheduling and voltage selection. We conduct experiments with a set of benchmarks from E3S (Dick 2008) and TGFF () based on the power model of the AMD Mobile Athlon4 DVS processor. The experimental results show that our technique can achieve 12.7% energy saving compared with the algorithms in Zhang et al. (2002) on average.

New Thermal‐Aware Voltage Island Formation for 3D Many‐Core Processors

The power consumption of 3D many‐core processors can be reduced, and the power delivery of such processors can be improved by introducing voltage island (VI) design using on‐chip voltage regulators. With the dramatic growth in the number of cores that are integrated in a processor, however, it is infeasible to adopt per‐core VI design. We propose a 3D many‐core processor architecture that consists of multiple voltage clusters, where each has a set of cores that share an on‐chip voltage regulator. Based on the architecture, the steady state temperature is analyzed so that the thermal characteristic of each voltage cluster is known. In the voltage scaling and task scheduling stages, the thermal characteristics and communication between cores is considered. The consideration of the thermal characteristics enables the proposed VI formation to reduce the total energy consumption, peak temperature, and temperature gradients in 3D many‐core processors.     

La technologie asynchrone au service de la réduction d’énergie dans les systèmes embarqués

This article presents the benefits of asynchronous systems versus synchronous systems in term of energy reduction in the context of embedded systems and in particular for telecom equipments such as mobile communicating objects. The electrical consumption reduction is obtained at the hardware and software levels. The shutdown technique and the dynamic voltage scaling for asynchronous systems are studied and compared to synchronous systems. Finally, a power management policy is proposed for asynchronous microprocessors processing periodic and sporadic tasks.     

Design of a hard real-time multi-core testbed for energy measurement

This paper presents a systematic methodology for designing a hard real-time multi-core testbed to validate and benchmark various rate monotonic scheduling (RMS)-based task allocation and scheduling schemes in energy consumption. The hard real-time multi-core testbed comprises Intel Core Duo T2500 processor with dynamic voltage scaling (DVS) capability and runs the Linux Fedora 8 operating system supporting soft real-time scheduling. POSIX threads API and Linux FIFO scheduling policy are utilized to facilitate the design and Dhrystone-based tasks are generated to verify the design. A LabView-based DAQ system is designed to measure the energy consumption of CPU and system board of the testbed. A case study of task allocation and scheduling algorithms is also presented that aim to optimize the schedule feasibility and energy consumed by the processor and memory module in the multi-core platform. The experience from the implementation is summarized to serve as potential guidelines for other researchers and practitioners.     

Cross-Layer Collaborative In-Network Processing in Multihop Wireless Sensor Networks

Emerging wireless sensor network (WSN) applications demand considerable computation capacity for in-network processing. To achieve the required processing capacity, cross-layer collaborative in-network processing among sensors emerges as a promising solution: sensors do not only process information at the application layer, but also synchronize their communication activities to exchange partially processed data for parallel processing. However, scheduling computation and communication events is a challenging problem in WSNs due to limited resource availability and shared communication medium. In this work, an application-independent task mapping and scheduling solution in multihop homogeneous WSNs, multihop task mapping and scheduling (MTMS), is presented that provides real-time guarantees. Using our proposed application model, the multihop channel model, and the communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously. The dynamic voltage scaling (DVS) algorithm is presented to further optimize energy consumption. Simulation results show significant performance improvements compared with existing mechanisms in terms of minimizing energy consumption subject to delay constraints     

Application-directed voltage scaling

Clock (and voltage) scheduling is an important technique to reduce the energy consumption of processors that support voltage scaling. It is difficult, however, to achieve good results using only statistics from the operating system level when applications show bursty (unpredictable) behavior. We take the approach that such applications must be made power-aware and specify their average execution time (AET) and the deadline to the scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) algorithm supporting power-aware applications. EPS orders tasks according to how tight their deadlines are and how often tasks overlap. Low-priority tasks are scheduled first, since they can be easily preempted to accommodate for high-priority tasks later. The EPS algorithm does not always yield the optimal schedule, but has a low complexity. We have implemented EPS on a StrongARM-based variable-voltage platform. We conducted experiments with a modified video decoder that estimates the AET of each frame. Measurements show that application-directed voltage scaling reduces processor power consumption with 50% for the bursty video decoder without missing any frame deadlines.