Energy-efficient scheduling for multiprocessors

An energy-efficient scheduling algorithm is proposed for parallel tasks in a multiprocessor system. The proposed algorithm utilises the dynamic voltage scaling (DVS) method for low energy consumption and executes tasks in parallel to compensate for the execution delay induced by the DVS method     

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

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

Maximizing the Lifetime of Embedded Systems Powered by Fuel Cell-Battery Hybrids

Fuel cell (FC) is a viable alternative power source for portable applications; it has higher energy density than traditional Li-ion battery and thus can achieve longer lifetime for the same weight or volume. However, because of its limited power density, it can hardly track fast fluctuations in the load current of digital systems. A hybrid power source, which consists of a FC and a Li-ion battery, has the advantages of long lifetime and good load following capabilities. In this paper, we consider the problem of extending the lifetime of a fuel-cell-based hybrid source that is used to provide power to an embedded system which supports dynamic voltage scaling (DVS). We propose an energy-based optimization framework that considers the characteristics of both the energy consumer (the embedded system) and the energy provider (the hybrid power source). We use this framework to develop algorithms that determine the output power level of the FC and the scaling factor of the DVS processor during task scheduling. Simulations on task traces based on a real-application (Path Finder) and a randomized version demonstrate significant superiority of our algorithms with respect to a conventional DVS algorithm which only considers energy minimization of the embedded system.      

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.     

A multiprocessor-oriented power-conscious scheduling algorithm for periodic tasks

With the rapid development of advanced technology in VLSI circuit designs, many processors could provide dynamic voltage scaling (DVS) to save power consumption when the supply voltage is allowed to be lower. In this paper, we propose a multiprocessor-oriented power-conscious scheduling algorithm for the real-time periodic tasks with task migration constrained scheme. We classify periodic tasks into fixed tasks and migration tasks, and limit the number of migration tasks and the number of destination processors which execute migration tasks. The proposed algorithm is made up of two steps. Firstly, choosing a processor to sort all of the periodic tasks in a non-increasing order according to task utilization, afterwards, allocating them to other processors. Secondly, scheduling the migration tasks with a virtual execution windows policy, and then scheduling the fixed tasks with EDF algorithm. The experiment results show that compared with arbitrary task migration policy and no task migration allowed policy, the power consumption in multiprocessor real-time periodic tasks scheduling is lowered significantly with the proposed algorithm.     

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     

众核任务映射算法研究现状与发展趋势

在众核系统中,并行任务在执行前需要被映射到处理器,这一过程被称为任务映射,任务映射算法对芯片性能影响巨大,所以近年来众核任务映射算法成为研究热点。针对不同的系统架构(如二维和三维众核系统)和优化目标(如通信开销、功耗、温度等)对现有任务映射算法进行综述,并展望了任务映射算法的未来发展趋势。     

针对电压可调处理器的低功耗设计策略

在便携式系统的低功耗设计中，动态电源管理（Dynamic Power Management，DPM）和动态电压调节（Dynamic Voltage Scaling，DVS）已经成为比较通用的技术，并且很多实验数据表明DVS省电性能比DPM更为优越。本文针对电压可调的处理器，在理论证明的基础上提出了一种能够跟踪工作负载需求变化，在保证给定任务组中所有任务性能的同时实现系统能耗最优化的电压调节策略EOVSP（Energy Optimal Voltage Scaling Policy）。实验结果也表明，该策略在满足系统性能要求的前提下具有比一般DPM策略更好的省电性能。     

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     

几种实时嵌入式系统DVS策略的分类比较

动态电压调节是一种有效的运用于实时嵌入式系统中的低功耗技术。实时嵌入式系统DVS技术不仅要实现系统功耗的降低,同时也要兼顾系统的实时性,满足任务的截止时间限。该文针对近几年实时嵌入式系统中DVS策略,首先介绍实时系统中DVS策略模型,对主流策略进行分类比较,并且对相应策略进行仿真,DVS策略可以取得10%～40%的能耗节省。     

An optimal analytical solution for maximizing expected battery lifetime using the calculus of variations

The exponential growth in the semiconductor industry and hence the increase in chip complexity, has led to more power usage and power density in modern processors. On the other hand, most of today's embedded systems are battery-powered, so the power consumption is one of the most critical criteria in these systems. Dynamic Voltage and Frequency Scaling (DVFS) is known as one of the most effective energy-saving methods. In this paper, we propose the optimal DVFS profile to minimize the energy consumption of a battery-based system with uncertain task execution time under deadline constraints using the Calculus of Variations (CoV). The contribution of this work is to analytically calculate the lower bound of expected battery charge consumption for a given task with uncertain execution time. Most of the research in dynamic voltage and frequency scaling tends to discretize time and value factors. This is presumably because of the context of embedded systems which is mainly based on digital design and algorithms. However, important factors in power and energy, such as supply voltage, supply current, and operational frequency, are continuous functions of time. The CoV is a branch of mathematics, where system parameters are considered as continuous functions of time. So, for dealing with this kind of problems, which system parameters are continuous functions of time, we can use the CoV as a powerful way to solve continuous optimization problems. In this paper, we obtain the exact analytical solution for maximizing battery lifetime, which is applicable to any convex power model.     

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.

CAD tool for hardware software co-synthesis of heterogeneous multiple processor embedded architectures

Hardware software co-synthesis process intends to determine an optimal architecture for an embedded application specified by a task graph or a specification language. In this paper, we present a co-synthesis approach targeting MPSoCs and distributed memory multiprocessor architectures for high performance embedded applications. Our co-synthesis approach produces pipelined multiprocessor architectures consisting of heterogeneous processing elements connected by a point-to-point communication structure. The co-synthesis process consists of four distinct phases; processing element selection for addition to the system, pipelined task allocation, scheduling and a regular interconnection topology mapping. Initially, an irregular topology is generated that is mapped to a regular architecture. Our co-synthesis methodology performs system partitioning and produces an irregular topology multiprocessor system. It also generates an optimal (or sub-optimal) regular topology architecture after considering some of the well-known regular topologies like mesh, hypercube, tree, etc. The co-synthesis method is demonstrated by exploring embedded architectures for MPEG encoder and artificially generated application task graphs representing complex embedded systems.     

The limit of dynamic voltage scaling and insomniac dynamic voltage scaling

Dynamic voltage scaling (DVS) is a popular approach for energy reduction of integrated circuits. Current processors that use DVS typically have an operating voltage range from full to half of the maximum V/sub dd/. However, there is no fundamental reason why designs cannot operate over a much larger voltage range: from full V/sub dd/ to subthreshold voltages. This possibility raises the question of whether a larger voltage range improves the energy efficiency of DVS. First, from a theoretical point of view, we show that, for subthreshold supply voltages, leakage energy becomes dominant, making "just-in-time computation" energy-inefficient at extremely low voltages. Hence, we introduce the existence of a so-called "energy-optimal voltage" which is the voltage at which the application is executed with the highest possible energy efficiency and below which voltage scaling reduces energy efficiency. We derive an analytical model for the energy-optimal voltage and study its trends with technology scaling and different application loads. Second, we compare several different low-power approaches including MTCMOS, standard DVS, and the proposed Insomniac (extended DVS into subthreshold operation). A study of real applications on commercial processors shows that Insomniac provides the best energy efficiency. From these results, we conclude that extending the voltage range below V/sub dd//2 will improve the energy efficiency for many processor designs.     

Low-Power Impulse UWB Architectures and Circuits

Ultra-wide-band (UWB) communication has a variety of applications ranging from wireless USB to radio-frequency (RF) identification tags. For many of these applications, energy is critical due to the fact that the radios are situated on battery-operated or even batteryless devices. Two custom low-power impulse UWB systems are presented in this paper that address high- and low-data-rate applications. Both systems utilize energy-efficient architectures and circuits. The high-rate system leverages parallelism to enable the use of energy-efficient architectures and aggressive voltage scaling down to 0.4 V while maintaining a rate of 100 Mb/s. The low-rate system has an all digital transmitter architecture, 0.65 and 0.5 V radio-frequency (RF) and analog circuits in the receiver, and no RF local oscillators, allowing the chipset to power on in 2 ns for highly duty-cycled operation.      

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.     

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     

操作系统级低功耗动态电压缩放算法分析

低功耗的设计已经成为嵌入式系统设计中一个非常重要的方面，而动态电压调度（Dynamic Voltage Scaling DVS）又被认为是降低功耗的一种有效手段。本文对各类针对系统的动态电压缩放算法做了较系统的总结，给出了算法的模型，重点描述了操作系统级的两类动态电压缩放算法——基于间隔和基于任务的动态电压调度算法，概述了针对编译级的任务内动态电压调度算法。文章对三类算法作了分析与比较，由此给出了结论与观点，对以后动态电压缩放算法的研究做了预测。     

Real-Time Dynamic Voltage Loop Scheduling for Multi-Core Embedded Systems

In this brief, we propose a novel real-time loop-scheduling technique to minimize energy consumption via dynamic voltage scaling (DVS) for applications with loops considering transition overhead. One algorithm, dynamic voltage loop scheduling (DVLS), is designed integrating with DVS. In DVLS, we repeatedly regroup a loop based on rotation scheduling and decrease the energy by DVS as much as possible within a timing constraint. We conduct the experiments on a set of digital signal processing benchmarks. The experimental results show that DVLS achieves big energy saving compared with the traditional time-performance-oriented scheduling algorithm