单处理器及多处理器系统节能技术的研究

摘要

随着数字化进程的日益加剧，系统的节能问题显得越发的重要。节能技术优劣不但影响电池供电嵌入式系统的使用或工作时间，即生命周期（lifetime），而且很大程度上决定了大规模系统（例如数据中心）的电费开销。为了延长嵌入式系统的生命周期，以及降低大规模系统的运行成本，在软件和硬件层次上，大量工作对节能技术进行了研究。在硬件方面，许多处理器提供了动态电压缩放(DVS)的功能，即处理器可以工作在不同的电压/频率上。同时，几乎所有的外围设备也支持动态电源管理(DPM)，即设备具有多种不同的工作状态或模式。在软件方面，通过调节系统负载（任务）在处理器上的工作状态、任务划分和调度以及使用外设的方式来达到节能的目的。随着片外设备数量的增加和多核系统的普及，多资源以及多核系统的节能问题受到了越来越多的关注。
　　本文从软件层面上，主要对单处理器多资源和多核实时系统的节能问题进行深入的研究。首先，在单处理器系统中，根据设备和处理器的功耗在系统总体功耗中所占的不同比例，给出不同的解决方法。其次，根据多核系统不同的划分以及任务的不同特性，提出相应的解决方法。具体来说，本文工作主要包含以下几个方面:
　　(1)在处理器功耗占系统功耗主要部分（外设功耗可忽略或是恒为常量）的单处理器系统中，考虑处理器模式切换的时间和能量开销，研究能耗敏感的实时任务调度及其可调度性测试条件。首先，提出新的可调度性测试条件，大大降低了其悲观性;其次，通过任务合并消除处理器的空闲模式，大大减少模式切换次数，从而降低功耗;最后，放松对处理器在每个协周期内对休眠时间的限制，使算法适用于更多类型的处理器。
　　(2)针对外设功耗处于系统整体功耗的决定性部分的嵌入式系统，研究了典型的无线传感器网络(WSN)的节能问题。无线传感器网络已经在监控系统等应用中被广泛采用，因为传感节点往往是由电量有限的电池供电，所以，如何恰当的控制每个传感节点的能量消耗从而最大化WSN的生命周期是至关重要的。本文研究输油管道监控系统中传感器节点的线性布置问题，目的是最大化该WSN的生命周期。对于简单的等距布置方式，首先，说明基于被普遍接受的理想功耗模型的一个结论（增加传感器节点可以增加WSN的生命周期）并不适用于真实的功耗模型;然后，研究等功耗放置方式，并将该问题建模为混合整数线性规划(MILP);最后，提出两个高效的启发式算法，从相反的方向搜索各传感节点工作的功耗等级。与等距放置策略相比，提出的两个启发式算法大大的降低了系统能耗，有效地平衡了各传感节点的能耗，显著的增加了WSN的生命周期。其中一个算法的结果与MILP的最优解几乎相同。
　　(3)在处理器与外设功耗相当的系统中，研究单处理器多外设实时系统的节能调度问题。具体工作主要包含两个部分。首先，对于简单的基于帧的周期任务，针对连续和离散处理器频率模型，本文分别提出高效的算法，通过计算使系统运行能耗最小的处理器最优频率和设备最优空闲时间，来实现全系统节能。其次，本文研究具有固定数量实时任务和固定数量外设的系统，考虑不可忽略的设备转换时间和能耗开销，找出能耗最优调度，包括任务的执行顺序，任务的运行频率以及设备状态转换的时间点。对于不同的系统配置，分别采用数学规划结合启发式算法的方式解决该问题，实验结果表明提出的算法大大降低了系统的能耗。
　　(4)对于多核实时系统，研究划分为簇(cluster)或岛(island)的多核体系结构的节能调度问题，这种体系结构下，每个岛上的所有处理器（核）具有相同的工作电压和频率。该研究综合考虑了系统的时间和频率约束，对实时任务提出能耗最小化的调度算法。首先，证明在不考虑时间约束的情况下，每个岛的能耗最小化的最优频率并不依赖于映射到该岛上的负载，而是依赖于该岛的核数及其漏电功耗。然后，针对具有时间约束的系统，在固定任务划分情况下，提出一多项式复杂度的算法最小化能耗，并证明其最优性。最后，给出多项式复杂度的整体算法来确定系统活跃岛的数量，任务划分和任务频率分配。实验表明该算法在节能方面大大优于相关的方法，并且分析了不同簇划分的节能效果。
　　(5)研究同质多处理器/多核系统并行实时任务的节能调度问题。对于执行在固定个数处理器上的并行任务，首先，提出几个基于层装箱(level-packing)的启发式任务调度算法，大大降低各层内的空闲时间;然后，提出一个多项式复杂度能耗最小化算法，并证明其最优性。对于执行并行任务的处理器个数可以变化的情况，提出另一个多项式复杂度的算法来确定执行各个任务的处理器个数，任务调度以及任务的频率分配。实验结果表明提出的算法可以大大的降低系统的能耗。
　　总之，本文综合研究了单处理器及多处理器系统的节能技术。首先，研究单处理器多资源系统的节能技术，对处理器功耗占主要部分的系统，外设功耗占主要部分的系统以及二者相当的系统，分别提出了不同的节能方法;然后，对于多核实时系统，研究了划分为岛的多核系统以及并行实时任务的节能调度问题，大大的降低了系统的能耗。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 相关技术介绍

1．3．1 低功耗设计

1．3．2 实时要求及调度策略

1．4 本文研究内容及贡献

1．5 本文的组织结构

第2章 相关工作

2．1 单处理器系统节能技术

2．1．1 处理器功耗占优的系统

2．1．2 设备功耗占优的系统

2．1．3 处理器功耗与设备功耗相当的系统

2．2 多处理器和多核系统节能技术

2．2．1 同质多处理器系统

2．2．2 异构多处理器系统

第3章 单处理器实时系统节能调度

3．1 问题定义

3．2 节能算法

3．2．1 对ES-RHS算法中调度测试条件的改进

3．2．2 对ES-RHS算法的改进

3．2．3 对ES-RHS算法的扩展

3．3 性能评估

3．3．1 四种算法的性能比较

3．3．2 不同处理器模式切换能耗对系统功耗的影响

3．4 小结

第4章 监控系统中WSN生命周期最大化问题研究

4．1 系统模型及问题定义

4．2 等距传感器节点放置方式

4．2．1 理想功耗模型

4．2．2 Tmote功耗模型

4．3 等功耗传感器节点放置方式

4．3．1 MILP规划

4．3．2 高效的贪婪算法

4．4 性能评估和讨论

4．4．1 等功耗方式性能

4．4．2 实现和真实放置

4．5 小结和未来工作

第5章 实时单任务系统全局能耗最小化问题研究

5．1 系统模型

5．2 节能调度算法

5．2．1 连续频率处理器模型

5．2．2 离散频率处理器模型

5．3 性能评估

5．3．1 连续频率处理器模型实验结果

5．3．2 离散频率处理器模型实验结果

5．4 小结

第6章 单处理器多资源实时系统节能调度

6．1 系统模型

6．2 0-1交叠和可变执行顺序(ZFOV-FLEX)

6．2．1 第一阶段：任务分组

6．2．2 第二阶段：0．1整数非线性规划(0．1 ILNP)

6．2．3 第二阶段：0．1整数线性规划(0-1 ILP)

6．2．4 非工作保持(Non-work-conserving)调度方式的解法

6．3 0-1交叠／部分交叠和固定执行顺序(ZFOV／POV-FIX)

6．3．1 第一阶段：查找活跃区间划分的段

6．3．2 第二阶段：工作保持调度(Work-conserving)方式的解法

6．3．3 第二阶段：非工作保持调度方式的解法

6．4 部分交叠和可变执行顺序(POV-FLEX)

6．4．1 保守近似算法

6．4．2 高效启发式算法

6．5 性能评估

6．5．1 0-1交叠和可变执行顺序(ZFOV-FLEX)

6．5．2 0-1交叠／部分交叠和固定执行顺序(ZFOV／POV-FIX)

6．5．3 部分交叠和可变执行顺序(POV-FLEX)

6．6 小结

第7章 基于簇的多核系统实时任务节能调度

7．1 问题定义

7．1．1 VFI和功耗模型

7．1．2 基于簇的多核系统的功耗管理

7．1．3 问题阐述

7．2 关键速度序列

7．3 给定任务划分下的能耗最小化

7．3．1 漏电功耗敏感的系统

7．3．2 漏电功耗可忽略的系统

7．4 任意粒度DVFS的能耗最小化

7．5 性能评估

7．5．1 比较：能耗最小化

7．5．2 比较：不同簇划分

7．6 讨论及小结

第8章 并行实时任务节能调度-连续处理器频率

8．1 问题定义

8．1．1 系统模型

8．1．2 问题阐述

8．2 刚性任务(Rigid task)

8．2．1 层装箱算法

8．2．2 新启发式算法

8．2．3 能耗最小化

8．3 可塑任务(Modable task)

8．3．1 节能问题的新特性

8．3．2 并行度分配算法

8．3．3 整体算法

8．4 实验结果及分析

8．4．1 实验设置

8．4．2 刚性任务

8．4．3 可塑任务

8．5 小结

第9章 并行实时任务节能调度-离散处理器频率

9．1 问题定义

9．1．1 系统模型

9．1．2 问题阐述

9．2 刚性任务(Rigid task)

9．2．1 0-1线性整数规划

9．2．2 高效启发式算法

9．3 可塑任务(Modable task)

9．3．1 0-1整数线性规划

9．3．2 高效启发式算法

9．4 实验结果及分析

9．4．1 刚性任务

9．4．2 可塑任务

9．5 小结

第10章 结论

10．1 本文的主要贡献与结论

10．2 进一步的工作

参考文献

致谢

攻博期间发表的论文

攻博期间参与的项目

作者简介