Temperature-Aware Task Allocation and Scheduling for Embedded Multiprocessor Systems-on-Chip (MPSoC) Design

Temperature affects not only the performance but also the power, reliability, and cost of the embedded system. This paper proposes a temperature-aware task allocation and scheduling algorithm for MPSoC embedded systems. Thermal-aware heuristics are developed, and a temperature-aware floorplanning tool is used to reduce the peak temperature and achieve a thermally even distribution while meeting real time constraints. The paper investigates both power-aware and thermal-aware approaches to the task allocation and scheduling. The experimental results show that the thermal-aware approach outperforms the power-aware schemes in terms of maximal and average temperature reductions. To the best of our knowledge, this is the first MPSoC task allocation and scheduling algorithm that takes temperature into consideration.

---

     

Task scheduling on multicore embedded systems under power and thermal constraints

The trend nowadays is to utilise multiple processors to overcome the limited additional power that can be extracted from a single core. This adds to the challenge of task scheduling on such architectures. Task scheduling should consider the power consumption of concurrently running tasks to avoid going over the maximum power limit. However, often scheduling with power awareness does not guarantee thermal safety. Thermal safety is intended to keep the temperatures of all system components under the maximum allowable temperature at all times. High temperatures can reduce the reliability and the overall functionality of the system. This implies that thermal-aware task scheduling is essential to reduce the system hotspots. In this article, we propose effective solutions to power and thermal-aware scheduling based on an integer linear formulation and genetic algorithms. Results on benchmarks proved the effectiveness and usefulness of our provided techniques.     

Efficient Worst-Case Temperature Evaluation for Thermal-Aware Assignment of Real-Time Applications on MPSoCs

The reliability of multiprocessor system-on-chips (MPSoCs) is nowadays threatened by high chip temperatures leading to long-term reliability concerns and short-term functional errors. High chip temperatures might not only cause potential deadline violations, but also increase cooling costs and leakage power. Pro-active thermal-aware allocation and scheduling techniques that avoid thermal emergencies are promising techniques to reduce the peak temperature of an MPSoC. However, calculating the peak temperature of hundreds of design alternatives during design space exploration is time-consuming, in particular for unknown input patterns and data. In this paper, we address this challenge and present a fast analytic method to calculate a non-trivial upper bound on the maximum temperature of a multi-core real-time system with non-deterministic workload. The considered thermal model is able to address various thermal effects like heat exchange between neighboring cores and temperature-dependent leakage power. Afterwards, we integrate the proposed thermal analysis method into a design-space exploration framework to optimize the task to processing component assignment. Finally, we apply the proposed method in various case studies to explore thermal hot spots and to optimize the task to processing component assignment.     

Thermal Management of On-Chip Caches Through Power Density Minimization

Various architectural power reduction techniques have been proposed for on-chip caches in the last decade. In this paper, we first show that these power reduction techniques can be suboptimal when thermal effects are considered. Then, we propose a thermal-aware cache power-down technique that minimizes the power density of the active parts by turning off alternating rows of memory cells instead of entire banks. The decrease in the power density lowers the temperature, which then exponentially reduces the leakage. Thus, leakage power of the active parts is reduced in addition to the power eliminated from the parts that are turned off. Simulations based on SPEC2000, NetBench, and MediaBench applications in a 70-nm technology show that the proposed thermal-aware architecture can reduce the total energy consumption by 53% compared to a conventional cache, and 14% compared to a cache architecture with thermal-unaware power reduction scheme. Second, we show a block permutation scheme that can be used during the design of the caches to maximize the distance between blocks with consecutive addresses. Because of spatial locality, blocks with consecutive addresses are likely to be accessed within a short time interval. By maximizing the distance between such blocks, we minimize the power density of the hot spots in the cache, and hence reduce the peak temperature. This, in return, results in an average leakage power reduction of 8.7% compared to a conventional cache without affecting the dynamic power and the latency. Overall, both of our architectures add no extra run-time penalty compared to the thermal-unaware power reduction schemes, yet they result in a significant reduction in the total energy consumption of a cache     

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

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

Optimal Semi-Partitioned Scheduling in Soft Real-Time Systems

Semi-partitioned real-time scheduling algorithms extend partitioned ones by allowing a (usually small) subset of tasks to migrate. The first such algorithm to be proposed was directed at soft real-time (SRT) sporadic task systems where bounded deadline tardiness is acceptable. That algorithm, called EDF-fm, has the desirable property that migrations are boundary-limited, i.e., they can only occur at job boundaries. However, it is not optimal because per-task utilization restrictions are required. In this paper, a new optimal semi-partitioned scheduling algorithm for SRT sporadic task systems is proposed that eliminates such restrictions. This algorithm, called EDF-os, preserves the boundary-limited property. In overhead-aware schedulability experiments presented herein, EDF-os proved to be better than all other tested alternatives in terms of schedulability in almost all considered scenarios. It also proved capable of ensuring very low tardiness bounds, which were near zero in most considered scenarios.     

Tasking planning based on task splitting and merging in relay satellite network

To handle the low planning efficiency of the tasks with too long or too short service time,a task planning scheme was proposed based on task splitting and merging for relay satellite systems.First,a task splitting and merging was developed to transfer the task requirements of user to task units which could be planned with high efficiency.Secondly,based on the parallel machine scheduling model,the optimization problem of the task unit planning to maximize the number of completed tasks in the network was built.Further,a heuristic polynomial time scheduling algorithm was proposed.Simulation results show that compared to the traditional scheme,the task planning scheme perform better in terms of completed task number,resource utilization and fairness.     

分层异构信号处理平台调度方法研究

异构多处理器的高效性和可靠性能够满足日趋复杂的信号处理任务需求,因此分层异构系统已成为信号处理平台的发展趋势.为提高平台强实时性并解决高吞吐量的问题,文中对分层异构信号处理平台的软硬件模块及架构进行了研究,并采用有向无环图对组件任务及硬件资源进行建模.将已提出的调度算法按照任务类型、调度目标、调度过程和研究方法进行分类...     

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

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

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.     

一种基于QoS的多任务实时集群系统负载均衡算法

负载均衡算法是多任务实时集群系统的一个关键技术。在分析了常见的轮转式均衡调度算法和任务最少优先法的优缺点基础上,针对实时集群系统处理多类任务的特点,引入了加权负载率的概念来更准确地描述各分布式集群节点的负载状况。提出了通过任务QoS映射为负载权值的思想,并给出了一种改进的任务最少优先算法——加权负载率最小法,描述了以加权负载率表为核心的多任务均衡调度算法。最后,通过仿真验证了该算法明显优于前两种算法。     

3D IC floorplanning: Automating optimization settings and exploring new thermal-aware management techniques

The introduction of 3D chip architectures is an increasingly attractive integration solution due to the potential performance improvement, power consumption reduction and heterogeneous integration. Nevertheless, thermal distribution, evacuation and limitation constitute some of the key issues that can hinder widespread adoption of 3D integration technology. Efficient 3D floorplan algorithms have to be developed to address such complexity. In this paper we first discuss the implementation of such an algorithm and identify parameters that play a role in the solution quality. We then propose the use of a genetic algorithm to discover sets of parameters that guarantee good ?oorplan quality. Then, we present an improved thermal-aware ?oorplanner based on a new formulation of the cost function that minimizes not only peak temperature, but also thermal gradients. The temperature minimization goal is reinforced using a smart heuristic that guides 3D moves in the direction of placing power hungry blocks next to the heat sink. Experimental results show the ability of the method to reduce the temperature peak and gradient signi?cantly, while maintaining area, wirelength and computation time.     

一种新的基于值函数迁移的快速Sarsa算法

知识迁移是当前机器学习领域的一个新的研究热点.其基本思想是通过将经验知识从历史任务到目标任务的迁移,达到提高算法收敛速度和收敛精度的目的.针对当前强化学习领域中经典算法收敛速度慢的问题,提出在学习过程中通过迁移值函数信息,减少算法收敛所需要的样本数量,加快算法的收敛速度.基于强化学习中经典的在策略Sarsa算法的学习框架,结合值函数迁移方法,优化算法初始值函数的设置,提出一种新的基于值函数迁移的快速Sarsa算法--VFT-Sarsa.该算法在执行前期,通过引入自模拟度量方法,在状态空间以及动作空间一致的情况下,对目标任务中的状态与历史任务中的状态之间的距离进行度量,对其中相似并满足一定条件的状态进行值函数迁移,而后再通过学习算法进行学习.将VTF-Sarsa算法用于Random Walk问题,并与经典的Sarsa算法、Q学习算法以及具有较好收敛速度的QV算法进行比较,实验结果表明,该算法在保证收敛精度的基础上,具有更快的收敛速度.     

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

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

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

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

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

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

异构网络化汽车电子系统中多DAG离线任务调度

公平性和通信开销已成为影响调度性能的主要瓶颈,首先在任务优先级排序阶段,提出基于通信开销权值的轮转调度的公平排序标准;在处理器选择阶段,提出在插入法的基础上将任务分配到具有最小选择值的选择标准;综合上述2个阶段,提出以降低调度长度和减少通信开销为目标的多DAG离线公平任务调度(MDOFTS, multiple DAGs off-line and fairness task scheduling)算法。异构网络化汽车电子系统是一个典型的混合关键级嵌入式系统,既要确保实时性又要降低调度长度,提出了以满足安全关键DAG的多DAG离线优先级任务调度(MDOPTS, multiple DAGs off-line and Priority task scheduling)算法。综合MDOFTS和MDOPTS,提出多DAG离线自适应任务调度(MDOATS, multiple DAGs off-line and adaptive task scheduling)算法,在满足实时性的基础上提高调度性能。实例分析和实验结果表明,提出的算法在调度长度、通信开销、不公平性、最差响应时间和实时性上都优于其他算法。     

A Cooperative Management Scheme for Power Efficient Implementations of Real-Time Operating Systems on Soft Processors

A cooperative management scheme for power efficient implementations of real-time operating systems on field-programmable gate-array (FPGA)-based soft processors is presented. Dedicated power management hardware peripherals are tightly coupled to a soft processor by utilizing its configurability. These hardware peripherals manage tasks and interrupts in cooperation with the soft processor, while retaining the real-time responsiveness of the operating system. More specifically, the hardware peripherals perform the following power management functionalities: (1) control the on-chip clock distribution network for driving the soft processor, its hardware peripherals, and the bus interfaces between them; (2) perform task and interrupt management responsibilities of the operating system when the soft processor is turned off; and (3) selectively wake up the soft processor and its hardware components, and put them into proper activation states based on the hardware resource requirements of the tasks under execution. The implementations of two popular real-time operating systems on a state-of-the-art FPGA device are presented. Measurements on an experimental board show that the proposed power management scheme can lead to significant power savings.     

Garbage Collection Scheduling of Aperiodic Tasks

In the previous work of garbage collection （GC） models, scheduling analysis was given based on an assumption that there were no aperiodic mutator tasks. However, it is not true in practical real-time systems. The GC algorithm which can schedule aperiodic tasks is proposed, and the variance of live memory is analyzed. In this algorithm, active tasks are deferred to be processed by GC until the states of tasks become inactive, and the saved sporadic server time can be used to schedule aperiodic tasks. Scheduling the sample task sets demonstrates that this algorithm in this paper can schedule aperiodic tasks and decrease GC work. Thus, the GC algorithm proposed is more flexible and portable.     

树形网格自适应调度模型研究

提出一种基于树形计算网格的自适应调度模型,实现对小粒度独立任务和用户大作业的自适应最优调度.通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间和任务特性的自适应调度算法.实验证明该任务调度模型在负载平衡和容错方面具有良好的性能.