多核多处理器系统的节能实时调度技术研究

发布时间：2018-06-28 02:12

本文选题：实时系统 + 节能调度　；参考：《国防科学技术大学》2012年博士论文

【摘要】：现实世界的实际需求促进了实时系统的产生和发展，随着电子技术和计算机技术的飞速发展，实时系统的应用范围也在不断扩大。这些领域的发展迫切需要提供性能更强大、操作更灵活、效能比更高的微处理器系统，以满足实时应用越来越复杂化、智能化的需求。随着VLSI技术的迅猛发展与应用需求的不断提高，芯片制造商正在推出多核芯片和片上多处理器系统，多核和多处理器平台已经变得更加普遍，受到了嵌入式实时领域越来越多的关注。但是，处理器的高性能会带来高能耗。而能耗是很多嵌入式实时系统首要考虑的因素，特别是无线移动和便携式计算设备。为了满足嵌入式实时应用的进一步发展，节能实时调度技术研究已经成为当前学术和工业界共同关注的前沿领域和热门课题之一，并且随着“绿色计算”需求的提出，变得越来越重要。本文针对多核/多处理器实时系统中的能耗问题，由多处理器系统到多核处理器系统，由偶发任务模型到一般任务模型，由理想DVFS处理器模型到实际DVFS处理器多维限制模型，从以下四个方面展开研究： 1.本文提出一种多处理器系统中偶发任务节能实时调度算法。从多处理器偶发任务在线节能实时调度问题出发，提出了基于偶发任务最优实时调度LRE-TL的多处理器在线节能调度算法，通过LRE-TL与独立DVFS和DPM技术相结合，，根据偶发任务动态释放所导致负载不断变化的情况，在每个TL面的初始时刻和偶发任务释放时刻对所有活跃任务实现在线动态电压和频率调节。算法不仅可以保证偶发任务集的最优可调度性，而且实验结果表明其始终优于已有算法，尤其在在高负载情况下能耗节余达到30%。 2.本文提出多核系统中偶发任务在线节能实时调度算法。从偶发任务动态释放问题出发，提出了一种基于TL流调度的多核在线节能实时调度算法TL-DVFS，利用LRE-TL算法实现任务调度，在每个TL面的初始时刻、偶发任务的释放时刻进行动态电压频率调节，能较好适应因偶发任务的动态释放而产生的动态负载变化。经过系统的数学分析和仿真实验，结果表明TL-DVFS算法与现有方法相比，不仅保证了偶发任务集的最优可调度性，而且实现了更多的能耗节余，尤其在高负载情况下节能效果更明显。通过考虑任务实际执行时间往往小于最坏情况执行时间的情况，进一步提出了一种基于动态松弛时间回收的节能实时调度算法DSREM，在每个TL面的提前完成时刻实现动态松弛时间回收，降低后续偶发任务的执行频率，实现更多的节能。实验结果表明，DSREM算法在任务集总负载超过某一个值之后，其节能效果始终优于现有方法，尤其随着总负载的增加，节能效果会更好。 3.本文提出一种基于Global EDF的多核系统一般任务在线节能实时调度算法。针对一般任务模型，提出了一种不基于先验知识，在同构多核系统中基于GlobalEDF在线节能硬实时调度算法GEDF-OLEASA，通过引入速度调节因子，利用松弛时间，结合动态功耗管理和动态电压/频率调节技术，降低多核系统中任务的执行速度，达到实时约束与能耗节余之间的合理折中。实验结果表明，该算法适用于不同类型的片上动态电压/频率调节技术，GEDF-OLEASA算法始终比GlobalEDF算法更节能，最多可节能15~20％，最少可节能5~10%。 4.本文提出一种开销敏感的最优节能实时调度算法。为解决原有最优算法在实际开销不可忽视条件下不再具有最优性问题，提出开销敏感的基于帧任务多处理器最优节能实时调度算法。该算法根据关键速度来判断系统负载情况，确定具有最低能耗值的活跃处理器个数，然后根据状态切换开销来确定最优调度序列。该算法允许实时任务在任意处理器之间迁移，计算复杂度小，易于在实时操作系统中实现。系统的数学分析证明了该算法的最优性。本文通过对多处理器系统偶发任务模型、多核系统偶发任务模型、一般任务模型及实际处理器开销模型的节能实时调度技术研究，对多核/多处理器实时系统的节能设计实现进行了有益的探索。本文的理论分析、仿真实验和评价结果表明，上述节能实时调度技术是有效的，能够有效解决多核/多处理器实时系统的能耗问题。
[Abstract]:Real world demand has promoted the production and development of real-time systems. With the rapid development of electronic technology and computer technology, the application scope of real-time systems is also expanding. The development of these fields is urgently needed to provide more powerful, more flexible, more efficient microprocessor systems to meet real-time applications. The more complex and intelligent the need.
With the rapid development of VLSI technology and the increasing demand for application, the chip manufacturers are introducing multi core chips and on chip multiprocessor systems. The multi-core and multiprocessor platforms have become more common. More and more attention has been paid to the embedded real-time field. However, the high performance of the processor will bring high energy consumption, and the energy consumption is much more. In order to meet the further development of embedded real-time applications, the research of real-time scheduling technology for energy saving has become one of the frontiers and hot topics of common concern in the academia and industry, and with the requirement of "green computing". Out, it's becoming more and more important.
In this paper, the problem of energy consumption in multi-core / multi processor real-time systems is studied from four aspects: from multi processor system to multi-core processor system, from the occasional task model to the general task model, from the ideal DVFS processor model to the actual DVFS processor multidimensional limit model.
1. this paper proposes an energy-efficient real-time scheduling algorithm for multi processor systems. Starting from the on-line energy-saving real-time scheduling problem of multi processor occasional tasks, a multi processor online energy saving scheduling algorithm based on the optimal real-time scheduling LRE-TL is proposed. By combining the LRE-TL with the independent DVFS and the DPM technology, this algorithm is based on the occasional task. In the case of the dynamic load changing, the dynamic voltage and frequency adjustment of all active tasks is realized at the initial time of each TL surface and the release time of the occasional task. The algorithm can not only guarantee the optimal schedulability of the occasional task set, but also the experimental results show that it is always superior to the existing algorithms, especially in the high negative. Energy savings reached 30%. under the load condition
2. this paper proposes a real-time scheduling algorithm for online energy saving in multi-core systems. Starting from the dynamic release of occasional missions, a multi-core online energy-saving real-time scheduling algorithm based on TL flow scheduling is proposed, which uses the LRE-TL algorithm to realize task scheduling. It is dynamic at the beginning of each TL plane and the release time of the occasional task. The voltage frequency regulation can better adapt to the dynamic load changes caused by the dynamic release of the occasional task. Through the system mathematical analysis and simulation experiments, the results show that the TL-DVFS algorithm not only guarantees the optimal schedulability of the occasional task set, but also has more energy savings, especially in the high load situation. The effect of energy saving is more obvious. By considering the fact that the actual execution time of the task is often less than the worst case execution time, a new energy saving real-time scheduling algorithm DSREM based on dynamic relaxation time recovery is proposed. The dynamic relaxation time recovery is realized at the time of advance completion of each TL surface, and the execution frequency of the subsequent incidental task is reduced. The experimental results show that, after the total load of the task set exceeds a certain value, the efficiency of the DSREM algorithm is always better than the existing method, especially with the increase of the total load, the efficiency of energy saving will be better.
3. this paper presents an online energy saving real-time scheduling algorithm for general task of multi-core systems based on Global EDF. For general task model, a hard real-time scheduling algorithm based on GlobalEDF online energy saving, without prior knowledge, is proposed in the isomorphic multi kernel system. By introducing the speed regulation factor, the relaxation time is used to combine the motion. State power management and dynamic voltage / frequency modulation techniques reduce the execution speed of tasks in multi-core systems and achieve a reasonable compromise between real time constraints and energy savings. The experimental results show that the algorithm is suitable for different types of on-chip dynamic voltage / frequency modulation techniques. The GEDF-OLEASA algorithm is always more energy-efficient than the GlobalEDF algorithm and is most available. Energy saving 15~20%, minimum energy saving 5~10%.
4. this paper proposes a cost sensitive and optimal energy saving real-time scheduling algorithm. In order to solve the problem that the original optimal algorithm no longer has the optimality problem under the condition that the actual cost can not be ignored, this algorithm proposes a cost sensitive real-time scheduling algorithm based on the frame task multi processor optimal energy saving. The number of active processors with the lowest energy consumption value, then the optimal scheduling sequence is determined according to the state switching overhead. The algorithm allows real-time tasks to migrate among any processors, the computational complexity is small, and it is easy to implement in the real-time operating system. The system's mathematical analysis proves the optimality of the algorithm.
In this paper, we study the multi processor system contingency model, the multi core system contingency model, the general task model and the real time processor cost model, and study the energy-saving real-time scheduling of the multi core / multi processor real-time system. The theoretical analysis, simulation experiment and evaluation result table of this paper are made. Obviously, the energy saving real-time scheduling technology is effective, and it can effectively solve the energy consumption problem of multi-core / multiprocessor real-time system.
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP332

【参考文献】