开销敏感的多处理器最优节能实时调度算法  

An Overhead-Aware Optimal Energy-Efficient Real-Time Scheduling Algorithm on Multiprocessors

作　　者：张冬松[1] 吴飞[2] 陈芳园[1] 吴彤[3] 郭得科[4] 金士尧[1] 

机构地区：[1]国防科学技术大学计算机学院并行与分布处理国家重点实验室,长沙410073 [2]上海工程技术大学电子电气工程学院,上海201620 [3]国防科学技术大学国家安全与军事战略研究中心,长沙410073 [4]国防科学技术大学信息与管理学院信息系统工程国家重点实验室,长沙410073

出　　处：《计算机学报》2012年第6期1297-1312,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(61170284;60903206);国家教育部博士点基金(20104307110005);博士后面上基金(20100480898;201104439);上海市教委科研创新项目(12ZZ182);国防科学技术大学优秀研究生创新项目(B100601);湖南省研究生科研创新项目(CX2010B026)资助~~

摘　　要：嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.As the energy consumption of embedded multiprocessor systems becomes increasingly prominent, the energy-efficient real-time scheduling in multiprocessor systems becomes an urgent problem. Most research efforts are based on the critical speed to reduce frequencies of processors for reducing the dynamic power consumption. Meanwhile, off-processor approach is also used to reduce the static power consumption. However, such approaches cannot achieve the minimum energy savings. In the other hand, the optimal energy-efficient real-time scheduling ignores the time and energy overhead of switching the processor state and thus is not optimal in actual platforms. For multiprocessors with the independent dynamic voltage frequency and dynamic power manage-ment, this paper proposes an optimal energy-efficient real-time scheduling algorithm for the frame-based tasks. The proposed optimal algorithm determines the system workload cases and the number of active processor cores in terms of the critical speed. Then we can obtain the optimal scheduling according to the switching overhead. The algorithm allows tasks to arbitrarily migrate across processors during their executions at the cost of the small computational complexity. Furthermore, it is easy to be implemented. Mathematical analysis shows that the algorithm is optimal.

关 键 词：实时系统 多处理器 节能调度 动态电压频率调节 动态功耗管理 绿色计算 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]