论文部分内容阅读
对于电池供电的嵌入式设备来说,低能耗是一个关键设计指标,嵌入式低能耗研究有着广阔的应用前景和重要的应用价值,逐渐引起工业界和学术界的高度关注。本文研究了嵌入式系统的节能调度问题。针对嵌入式系统中具有严格执行时限要求的周期性任务,提出了四种节能调度算法。还针对无线传感器网络,提出了三维空间K虚拟栅栏覆盖节能调度算法。对于电压可变的处理器,已有研究考虑了理想的具有连续可变电压的处理器模型,而真实的可变电压处理器仅具有离散的电压等级。动态电压缩放(Dynamic Voltage Scaling,DVS)是一个有效的节能技术,它通过降低处理器运行时的电压来节能。但是,降低电压的同时会导致任务执行时间增加,因此需要优化延迟和能耗这对互为矛盾的指标。对于具有离散电压等级的单处理器,本文首先提出了一种最优电压选择算法,使得在不违背给定应用执行时限的前提下系统能耗最少。与已有启发式算法不同,最优电压选择算法将该节能调度问题转化为多选择背包问题的变种,然后采用动态规划方法求得最优解。更进一步,由于在处理器上调度任务时,电压切换会引起额外的跃迁代价,影响系统的延迟和能耗,因此又提出了一种改进的单处理器节能调度算法,该算法考虑了离散电压模型、动态能耗,以及电压跃迁代价。对于多处理器MPSoC架构上的任务,传统任务调度算法关注并行化的挖掘以提高系统吞吐率,降低延迟。现在,MPSoC架构已被广泛的应用到嵌入式系统中,像多媒体和网络处理等计算密集型的嵌入式应用,对能耗和延迟都很关注,因而对任务调度算法提出了新的挑战。针对运行在MPSoC架构上的实时嵌入式应用,提出了两种两阶段的基于重定时的节能调度算法,它们将充分发掘MPSoC架构的并行潜力,并且和减少能耗关联起来考虑,既满足了应用执行时限的要求,又达到了降低应用能耗的目标。在设计算法时,两个算法第一阶段都采用重定时技术进行任务并行化,将一个迭代周期内的迭代内依赖关系转化成迭代间的依赖关系,从而减少了由于迭代内依赖关系和处理器间通信所导致的空闲时隙。这些赢得的空闲时隙在第二个阶段所利用以进行能量优化。在第二个能量优化阶段,第一个算法是模拟弹簧行为的启发式节能调度算法,它考虑了动态能耗和静态能耗。更进一步,由于影响系统能耗的因素很多,这些因素对能耗的影响又是错综复杂的,所以本文又提出了第二个基于遗传算法的节能调度算法,该算法考虑了多种能耗相关的因素,如动态能耗、静态能耗、电压跃迁代价、处理器间通信代价等因素,设计了染色体的基因编码方式、适度函数、交叉算子等。该算法可以充分发掘多处理器MPSoC架构的潜力以及现代芯片的节能特性,实现对能耗和性能的多目标优化。无线传感器网络是典型的分布式嵌入式系统,以上所提出的系统级的节能调度算法在每一个传感器硬件节点上同样适用。但是对于传感器网络,不仅应该关注每一个节点的能耗,还应该从整个网络协同工作角度出发考虑节能。因此,本文还研究了无线传感器网络三维空间栅栏覆盖中的节能问题。研究表明,单个虚拟栅栏覆盖的节点睡眠调度算法是NP-Hard问题,本文提出了单个虚拟栅栏覆盖调度算法求得近似解。在此基础上,又提出了K-虚拟栅栏覆盖调度算法来最优化K-虚拟栅栏调度,使得在同一时刻,在满足传感检测范围的前提下,让最少数量的传感器节点交替工作,既满足网络覆盖要求,又减少能耗,延长了传感器网络的生命周期。