一类异构多处理器片上系统任务调度算法研究与应用

摘要

由于芯片制造工艺的限制，处理器频率的继续提升遇到了物理瓶颈，多处理器技术被认为是维持片上系统性能增长的有效方法。异构多处理器片上系统(Multi-Processor System-on-Chip，MPSoC)兼顾了系统的通用性与灵活性，受到了工业界和学术界的青睐，已经被广泛应用于移动通信、嵌入式多媒体等领域。对于异构MPSoC来说，其性能的充分发挥依赖于所采用的任务调度算法。高效的调度算法可以缓解处理器数目增加所带来的高能耗、高温度、高成本等问题，能够进一步扩大MPSoC的应用范围。在满足各种约束的前提下对异构MPSoC进行优化调度已经证明是NP难问题。因而，针对异构MPSoC的各种应用需求，寻求不同优化目标下的最佳调度方案，已经成为当今多处理器技术的研究热点和重点。
　　随着可重构技术和MPSoC的发展，出现了包含可重构资源的异构MPSoC，它兼具可重构资源的高效性和MPSoC的灵活性，为系统设计和应用提供了更多的选择。对含有可重构资源的异构MPSoC而言，任务调度时还需要完成软硬件划分，因而进一步增加了问题的复杂度。针对具有可重构功能的异构MPSoC，以充分发挥可重构资源的性能、解决异构MPSoC所面临的能耗和温度问题为出发点，分别开展软硬件优化划分算法、节能调度算法和温度感知调度算法研究。论文的具体工作如下：
　　(1)针对双路软硬件划分的特点，借鉴0/1背包问题的相关算法思想，基于模拟退火算法的全局寻优特性，提出了一种融合贪心算法与模拟退火算法的软硬件划分方法。该方法在研究双路软硬件划分系统结构基础上，首先将软硬件划分问题规约为0/1背包问题，采用贪心算法进行快速初始划分；然后设计一种新的接收准则，根据新解在扰动模型中的位置来计算其接收概率，基于贪心算法的预划分结果，采用改进的模拟退火算法进行全局寻优。由于该算法兼具贪心算法的高效性和模拟退火算法的全局寻优能力，从而避免了模拟退火算法初始划分难以设定的问题，在任务划分质量和算法运行时间方面均取得了较好的效果。仿真实验证明了本文所提算法的有效性。
　　(2)针对异构MPSoC中处理器数目增长所引起的高能耗问题，考虑遗传算法的高效搜索能力，采用动态电压缩放技术，提出了一种新的节能调度算法。该算法首先对遗传算法的选择算子和群体更新机制进行改进，增强了群体的多样性，然后基于改进的遗传算法来确定任务优先级，采用链表调度方法确定任务执行顺序；最后根据任务能量和时间关系，设计了一种新的任务缩放优先级计算方法，基于该优先级进行节能调度。该算法在具备遗传算法的高效搜索能力的同时，弥补了其容易陷入局部最优解的缺陷，并且通过对高能耗任务进行有针对性的缩放，很好地实现系统节能。
　　(3)针对能量密度增长给异构MPSoC所带来的温度提升，考虑漏极功率、供电电压和温度之间的关系，以系统峰值温度最小化为优化目标，提出了一种新的温度感知调度算法。温度升高将直接缩短处理器的生命周期，同时影响系统性能和使用舒适度。本文首先针对异构MPSoC应用推广所面临的温度问题，在温度与供电电压关系的基础上，考虑处理器的漏极功率，建立温度模型；然后根据任务关键路径进行初始调度，在温度模型基础上计算任务的运行温度，运用动态电压缩放技术，通过迭代操作优化系统峰值温度。该算法中所考虑的温度模型更为实际，并且直接对具有峰值温度的任务进行优化，从而能够显著降低系统峰值温度和平均温度。
　　(4)针对本文提出的任务调度算法，在相关嵌入式系统中进行了应用研究。针对湖南省科研条件创新专项“三维荧光光谱仪高性能数学分离关键部件研制”，进行了软硬件划分算法应用研究。该部件的核心是“数学分离”算法，涉及到大量的高维矩阵运算，在嵌入式应用中需要解决复杂计算问题。本文通过分析问题的计算特性，采用通用处理器和可重构资源相结合的方式，进行系统结构设计；然后运用本文提出的软硬件划分方法，对任务进行划分，获得了较好的系统性能。针对国家发改委项目“中国网上教育平台”子项--“移动学习平台”，进行了节能调度算法应用研究。嵌入式移动平台特别关注能耗问题，本文采用具有较好电源管理功能的PXA255芯片进行系统设计，并进行动态电压缩放技术的具体实现。在此基础上，运用本文的节能调度方法，对AVS视频解码任务进行节能调度应用研究。应用结果表明了本文算法的有效性。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 课题来源

1.2 研究背景

1.3 异构MPSoC任务调度问题

1.4 本文主要工作

1.5 论文组织

第2章 相关研究

2.1 异构MPSoC体系结构发展

2.1.1 处理器内核架构

2.1.2 异构MPSoC现状

2.2 任务调度分析

2.2.1 任务调度分类

2.2.2 异构MPSoC常用任务模型

2.2.3 异构MPSoC任务调度结构

2.3 异构多处理器任务调度相关研究

2.3.1 异构多处理器任务调度方法

2.3.2 任务调度启发式算法

2.4 本章小结

第3章 一种面向可重构片上系统的软硬件划分方法

3.1 引言

3.1.1 可重构片上系统概述

3.1.2 软硬件划分算法现状

3.1.3 本章方法

3.2 软硬件划分模型

3.2.1 体系结构

3.2.2 相关定义

3.2.3 软硬件划分的0/1背包模型

3.3 贪心算法与模拟退火融合的软硬件划分方法

3.3.1 软硬件划分算法流程

3.3.2 基于贪心算法的预划分

3.3.3 基于改进模拟退火算法的软硬件划分

3.3.4 算法时间复杂度分析

3.4 模拟实验及性能分析

3.4.1 实验方案

3.4.2 实验结果及分析

3.5 本章小结

第4章 一种异构多处理器节能调度算法

4.1 引言

4.1.1 MPSoC能耗问题

4.1.2 节能调度的研究现状

4.1.3 本章方法

4.2 异构MPSoC节能调度模型

4.2.1 任务模型

4.2.2 能量模型

4.2.3 系统模型

4.3 基于改进遗传算法的节能调度

4.3.1 算法框架

4.3.2 任务优先级确定方法

4.3.3 基于缩放优先级的节能调度

4.3.4 优先级链表调度

4.3.5 算法时间复杂度分析

4.4 模拟实验及结果分析

4.4.1 实验方法

4.4.2 实验结果及分析

4.5 本章小结

第5章 一种异构多处理器温度感知调度算法

5.1 引言

5.1.1 处理器温度挑战

5.1.2 温度调度相关研究

5.1.3 本章方法

5.2 系统模型和问题定义

5.2.1 任务模型

5.2.2 温度模型

5.2.3 异构MPSoC温度感知调度问题定义

5.3 新的温度感知算法

5.3.1 峰值温度最小化调度算法

5.3.2关键路径任务调度算法

5.4 模拟实验及结果分析

5.4.1 实验方案

5.4.2 算法时间复杂度对比分析

5.4.3 温度比较结果

5.5 本章小结

第6章 任务调度算法应用研究

6.1 软硬件划分算法应用研究

6.1.1 应用背景

6.1.2 系统设计

6.1.3 软硬件划分过程

6.1.4 算法实现

6.2 节能调度算法应用研究

6.2.1 处理器介绍

6.2.2 系统设计

6.2.3 节能调度算法应用

6.3 本章小结

总结和展望

参考文献

致谢

附录A 攻读学位期间发表的学术论文

附录B 攻读学位期间的研究工作