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.     

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     

Variable voltage task scheduling algorithms for minimizing energy/power

In this paper, we propose variable voltage task scheduling algorithms that minimize energy or minimize peak power for the case when the task arrival times, deadline times, execution times, periods, and switching activities are given. We consider aperiodic (earliest due date, earliest deadline first), as well as periodic (rate monotonic, earliest deadline first) scheduling algorithms. We use the Lagrange multiplier method to theoretically determine the relation between the task voltages such that the energy or peak power is minimum, and then develop an iterative algorithm that satisfies the relation. The asymptotic complexity of the existing scheduling algorithms change very mildly with the application of the proposed algorithms. We show experimentally (random experiments as well as real-life cases), that the voltage assignment obtained by the proposed low-complexity algorithm is very close to that of the optimal energy (0.1% error) and optimal peak power (1% error) assignment.     

Instruction Scheduling for Low Power

Reducing energy consumption has become an important issue in designing hardware and software systems in recent years. Although low power hardware components are critical for reducing energy consumption, the switching activity, which is the main source of dynamic power dissipation in electronic systems, is largely determined by the software running on these systems.In this paper, we present and evaluate several instruction scheduling algorithms that reorder a given sequence of instructions taking into account the energy considerations. We first compare a performance-oriented scheduling technique with three energy-oriented instruction scheduling algorithms from both performance (execution cycles of the resulting schedules) and energy consumption points of view. Then, we propose three scheduling algorithms that consider energy and performance at the same time. Our experimentation with these scheduling techniques shows that the best scheduling from the performance perspective is not necessarily the best scheduling from the energy perspective. Further, scheduling techniques that consider both energy and performance simultaneously are found to be desirable, that is, these techniques are quite successful in reducing energy consumption and their performance (in terms of execution cycles) is comparable to that of a pure performance-oriented scheduling. We also illuminate the inherent approximations and difficulties in building energy models for enabling energy-aware instruction scheduling and explore alternative options using cycle-accurate energy simulator. The simulation results show that the energy-oriented scheduling reduces energy consumption by up to 30% compared to the performance-oriented scheduling.     

一个面向嵌入式系统实时性能优化的抢占模型

通过对采用RM调度策略的实时嵌入式系统抢占行为的分析，建立了一个周期性实时任务集的抢占模型，从数学上定量地刻画了因抢占而导致的额外开销与系统中各实时任务属性的关系，以及与整个实时任务集的可调度性的关系。依据该模型并借鉴生物学领域的寄生思想，提出了一个基于进化规划的性能优化方法，通过调整任务启动时间，以减少抢占次数或改变抢占关系，降低系统额外开销，提高系统实时性能；最后通过实验验证了建立在抢占模犁基础上的嵌入式系统件能优化方法的有效件。     

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.

Run-time Task Overlapping on Multiprocessor Platforms

Today’s embedded applications often consist of multiple concurrent tasks. These tasks are decomposed into sub-tasks which are in turn assigned and scheduled on multiple different processors to achieve the Pareto-optimal performance/energy combinations. Previous work introduced systematical approaches to make performance-energy trade-offs explorations for each individual task and used the exploration results at run-time to fulfill system-level constraints. However, they did not exploit the fact that the concurrent tasks can be executed in an overlapped fashion. In this paper, we propose a simple yet powerful on-line technique that performs task overlapping by run-time subtask re-scheduling. By doing so, a multiprocessor system with concurrent tasks can achieve better performance without extra energy consumption. We have applied our algorithm to a set of randomly-generated task graphs, obtaining encouraging improvements over non-overlapped task, and also having less overall energy consumption than a previous DVS method for real-time tasks. Then, we have demonstrated the algorithm on real-life video- and image-processing applications implemented on a dual-processor TI TMS320C6202 board: We have achieved a reduction of 22–29% in the application execution time, while the impact of run-time scheduling overhead proved to be negligible (1.55%).     

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

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

RM算法的运行时开销研究与算法改进

RM算法是经典的固定优先级实时调度算法.而在嵌入式实时系统中,系统的工作负荷往往是由很多频率快、执行时间较短的任务组成.因此,直接使用RM算法进行任务调度会由于实时操作系统中任务的上下文切换开销而导致嵌入式系统资源利用率的降低.分析了基于RM算法调度的任务之间的抢占关系,并建立了以任务属性为参数的上下文切换开销模型.在该模型的基础上,通过优化任务的释放时间来降低RM算法导致的系统运行时任务切换开销.最后的实验结果验证了该策略的有效性.     

基于价值优化的相控阵雷达任务调度算法

针对相控阵雷达时间资源分配问题,该文提出一种基于价值优化的任务调度算法。首先建立任务调度属性参数,对跟踪任务队列进行可行性分析和筛选操作,确定跟踪任务调度属性。其次,根据任务最大价值及其变化斜率,建立关于实际执行时刻的动态任务价值函数,并基于此构建任务调度的价值优化模型,对跟踪任务执行时刻进行分配,以更好满足及时性原则。最后,利用执行跟踪任务间的空闲时间片对搜索任务进行调度。仿真结果表明,该文算法有效减小了时间偏移量,提升了实现价值率。     

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

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

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

A distributed mobile DSP system consists of a group of mobile devices with different computing powers. These devices are connected by a wireless network. Parallel processing in the distributed mobile DSP system can provide high computing performance. Due to the fact that most of the mobile devices are battery based, the lifetime of mobile DSP system depends on both the battery behavior and the energy consumption characteristics of tasks. In this paper, we present a systematic system model for task scheduling in mobile DSP system equipped with Dynamic Voltage Scaling (DVS) processors and energy harvesting techniques. We propose the three-phase algorithms to obtain task schedules with shorter total execution time while satisfying the system lifetime constraints. The simulations with randomly generated Directed Acyclic Graphs (DAG) show that our proposed algorithms generate the optimal schedules that can satisfy lifetime constraints.     

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.     

Network real-time scheduling algorithm based on multi-feature dynamic priority

Real-time task scheduling system structure and task model were proposed aiming at the network real-time scheduling problem.The task degree of urgency was defined by considering the deadline of task,execution time and interval time between works.The task degree of tightness was proposed based on service-level assurance,according to functional importance of different tasks in the real-time task scheduling system.The thrashing limit for avoiding task switching frequently was acquired through dynamic regulation to task priorities by degree of urgency and degree of tightness,which guaranteed the success rate of tasks execution and utilization ratio of client execution.Test simulation results suggest that the multi-feature dynamic priority scheduling strategy improves the success rate of task scheduling and shorten the average response time,which suggests it has obvious superiority compared with BE and EDF scheduling 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     

Resource scheduling in mobile edge computing using improved ant colony algorithm for space information network

With the development of space information network (SIN), new network applications are emerging. Satellites are not only used for storage and transmission but also gradually used for calculation and analysis, so the demand for resources is increasing. But satellite resources are still limited. Mobile edge computing (MEC) is considered an effective technique to reduce the pressure on satellite resources. To solve the problem of task execution delay caused by limited satellite resources, we designed Space Mobile Edge Computing Network (SMECN) architecture. According to this architecture, we propose a resource scheduling method. First, we decompose the user tasks in SMECN, so that the tasks can be assigned to different servers. An improved ant colony resource scheduling algorithm for SMECN is proposed. The heuristic factors and pheromones of the ant colony algorithm are improved through time and resource constraints, and the roulette algorithm is applied to route selection to avoid falling into the local optimum. We propose a dynamic scheduling algorithm to improve the contract network protocol to cope with the dynamic changes of the SIN and dynamically adjust the task execution to improve the service capability of the SIN. The simulation results show that when the number of tasks reaches 200, the algorithm proposed in this paper takes 17.52% less execution time than the Min-Min algorithm, uses 9.58% less resources than the PSO algorithm, and achieves a resource allocation rate of 91.65%. Finally, introducing dynamic scheduling algorithms can effectively reduce task execution time and improve task availability.     

Cost Minimization with HPDFG and Data Mining for Heterogeneous DSP

Cost minimization and execution-time reduction have become the most important issues in today’s real-time embedded system. Meanwhile, for the DSP (Digital Signal Processing) applications running on embedded system, loops inside them are the most critical part for performance optimization. To optimize the loop iteration patterns, we need to schedule the loop execution order. Due to the uncertainties within the execution time of tasks, we model varied execution times of tasks as random variables and propose a novel data graph model, called HPDFG (Heterogeneous Probabilistic Data-Flow Graph) to model DSP applications on embedded systems. A novel algorithm, LSHAPE, is proposed to minimize the cost and satisfy the timing constraints. First of all, we use the data mining methods to estimate the probabilistic distribution of the execution time variables. Second, we rotate the loops in the application to explore different possible execution patterns. Finally, we combine the list-scheduling and the dynamic programming to generate a near-optimal task allocation and a core-mode assignment. Experimental results demonstrate the effectiveness of our algorithm. Our approach can handle loops efficiently.     

Meta‐heuristic algorithms for channel scheduling problem in wireless sensor networks

The channel scheduling problem is to decide how to commit channels for transmitting data between nodes in wireless networks. This problem is one of the most important problems in wireless sensor networks. In this problem, we aim to obtain a near‐optimal solution with the minimal energy consumption within a reasonable time. As the number of nodes increases in the network, however, the amount of calculation for finding the solution would be too high. It can be difficult to obtain an optimal solution in a reasonable execution time because this problem is NP‐hard. Therefore, most of the recent studies for such problems seem to focus on heuristic algorithms. In this paper, we propose efficient channel scheduling algorithms to obtain a near‐optimal solution on the basis of three meta‐heuristic algorithms; the genetic algorithm, the Tabu search, and the simulated annealing. In order to make a search more efficient, we propose some neighborhood generating methods for the proposed algorithms. We evaluate the performance of the proposed algorithms through some experiments in terms of energy consumption and algorithm execution time. The experimental results show that the proposed algorithms are efficient for solving the channel scheduling problem in wireless sensor networks. Copyright © 2011 John Wiley & Sons, Ltd.     

Q-learning-based task offloading strategy for satellite edge computing

In this paper, we study the task offloading optimization problem in satellite edge computing environments to reduce the whole communication latency and energy consumption so as to enhance the offloading success rate. A three-tier machine learning framework consisting of collaborative edge devices, edge data centers, and cloud data centers has been proposed to ensure an efficient task execution. To accomplish this goal, we also propose a Q-learning-based reinforcement learning offloading strategy in which both the time-sensitive constraints and data requirements of the computation-intensive tasks are taken into account. It enables various types of tasks to select the most suitable satellite nodes for the computing deployment. Simulation results show that our algorithm outperforms other baseline algorithms in terms of latency, energy consumption, and successful execution efficiency.     

云计算环境下能量感知的任务调度算法

云计算环境下传统独立任务调度算法容易导致较高资源能耗或较大任务时间跨度.针对该问题,文中提出了两种能量感知的任务调度算法,并利用遗传算法并行化搜索合理调度方案.两种算法在搜索过程中,分别通过能耗时间归一和能耗时间双适应度方法定义适应度函数并进行个体选择.仿真结果表明,与单独考虑时间或能耗相比,这两种算法能够更有效地缩短任务执行时间跨度,降低资源能耗.