摘要:由于芯片制造工艺的限制,处理器频率的继续提升遇到了物理瓶颈,多处理器技术被认为是维持片上系统性能增加的有效策略。异构多处理器片上系统(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芯片进行系统设计,并进行动态电压缩放技术的具体实现。在此基础上,运用本论文的节能调度策略,对S视频解码任务进行节能调度运用探讨。运用结果表明了本论文算法的有效性。关键词:嵌入式系统论文可重构论文多处理器片上系统论文软硬件划分论文节能调度论文温度感知调度论文启发式算法论文
摘要5-7
Abstract7-13
插图索引13-15
附表索引15-16
第1章 绪论16-24
1.1 课题来源16
1.2 探讨背景16-19
1.3 异构 MPSoC 任务调度不足19-21
1.4 本论文主要工作21-22
1.5 论文组织22-24
第2章 相关探讨24-45
2.1 异构 MPSoC 系统结构进展24-29
2.1.1 处理器内核架构24-25
2.1.2 异构 MPSoC 近况25-29
2.2 任务调度浅析29-35
2.2.1 任务调度分类29-30
2.2.2 异构 MPSoC 常用任务模型30-32
2.2.3 异构 MPSoC 任务调度结构32-35
2.3 异构多处理器任务调度相关探讨35-44
2.3.1 异构多处理器任务调度策略35-38
2.3.2 任务调度启发式算法38-44
2.4 本章小结44-45
第3章 一种面向可重构片上系统的软硬件划分策略45-64
3.1 引言45-50
3.1.1 可重构片上系统概述45-46
3.1.2 软硬件划分算法近况46-49
3.1.3 本章策略49-50
3.2 软硬件划分模型50-52
3.2.1 系统结构50-51
3.2.2 相关定义51
3.2.3 软硬件划分的 0/1 背包模型51-52
3.3 贪心算法与模拟退火融合的软硬件划分策略52-58
3.3.1 软硬件划分算法流程52-54
3.3.2 基于贪心算法的预划分54-55
3.3.3 基于改善模拟退火算法的软硬件划分55-58
3.3.4 算法时间复杂度浅析58
3.4 模拟实验及性能浅析58-63
3.4.1 实验案例58-59
3.4.2 实验结果及浅析59-63
3.5 本章小结63-64
第4章 一种异构多处理器节能调度算法64-86
4.1 引言64-68
4.1.1 MPSoC 能耗不足64-65
4.1.2 节能调度的探讨近况65-67
4.1.3 本章策略67-68
4.2 异构 MPSoC 节能调度模型68-70
4.2.1 任务模型68-69
4.2.2 能量模型69
4.2.3 系统模型69-70
4.3 基于改善遗传算法的节能调度70-82
4.3.1 算法框架70-72
4.3.2 任务优先级确定策略72-76
4.3.3 基于缩放优先级的节能调度76-79
4.3.4 优先级链表调度79-81
4.3.5 算法时间复杂度浅析81-82
4.4 模拟实验及结果浅析82-85
4.4.1 实验策略82-83
4.4.2 实验结果及浅析83-85
4.5 本章小结85-86
第5章 一种异构多处理器温度感知调度算法86-101
5.1 引言86-92
5.1.1 处理器温度挑战86-87
5.1.2 温度调度相关探讨87-91
5.1.3 本章策略91-92
5.2 系统模型和不足定义92-94
5.2.1 任务模型92
5.2.2 温度模型92-93
5.2.3 异构 MPSoC 温度感知调度不足定义93-94
5.3 新的温度感知算法94-97
5.3.1 峰值温度最小化调度算法94-96
5.3.2 关键路径任务调度算法96-97
5.4 模拟实验及结果浅析97-100
5.4.1 实验案例97
5.4.2 算法时间复杂度比较浅析97-99
5.4.3 温度比较结果99-100
5.5 本章小结100-101
第6章 任务调度算法运用探讨101-125
6.1 软硬件划分算法运用探讨101-113
6.1.1 运用背景101-104
6.1.2 系统设计104-109
6.1.3 软硬件划分历程109-111
6.1.4 算法实现111-113
6.2 节能调度算法运用探讨113-124
6.2.1 处理器介绍113-114
6.2.2 系统设计114-117
6.2.3 节能调度算法运用117-124
6.3 本章小结124-125
总结和展望125-128