嵌入式系统节能调度算法研究

发布时间：2020-06-02 16:13

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

嵌入式系统节能调度算法研究 图 4.1 本文调度策略示意图图4.1 通过一个例子来阐述本文所提调度策略的思想内涵。图4.1(a)是原始任务图，代表一个周期性应用。图4.1(c)是该任务在高电压和低电压两种模式下的能耗和计算时间。图4.1(d)是采用传统表调度算法，给两个处理器核都分配高电压的情况下完成该应用的一个周期内的任务所产生的调度情况。可以看出，此种调度需要耗时16μs，，耗能137μJ。图4.1(e)是采用基于DAG的调度方法和动态电源管理方法相结合产生的一个调度，它在处理器核PE2空闲时让PE2进入休眠状态来节能，此种调度耗时16μs，耗能73.4μJ。相比与图4.1(d)所给方法有了很大的进步。但是

图4.2 一个电路示意图图4.3 图4.2电路示意图的变形下面解释延迟的物理意义。如图4.4(b)所示，假设一个延迟用边上的一个横线表示，则n个延迟就用n条横线表示。对于任意节点v ∈V，节点v的重定时函数r :V→Z是经过节点v的延迟数，记作d(e)。对于从节点u到节点v的任意一条边e (u ,v)∈E，若其上的延迟数 d ( e)>0，则表示在第j次循环中，计算节点v时需要用到在第 j d(e)次循环中节点u计算后得到的数据。(a) (b)图 4.4 任务图示例：(a) 原始任务图 G (b)重定时后的任务图 Gr在电路中
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：TP368.1

【参考文献】

相关期刊论文 前10条

1 赵晓莺;易江芳;佟冬;程旭;;利用遗传算法实现CMOS组合电路静态功耗优化[J];北京大学学报(自然科学版);2007年03期

2 陈燕;董世娜;赵宏杰;;影响电解电容器漏电流的因素[J];电子产品可靠性与环境试验;2007年06期

3 骆祖莹;潘月斗;;CMOS电路晶体管级功耗优化方法[J];计算机研究与发展;2008年04期

4 李仁发;刘彦;徐成;;多处理器片上系统任务调度研究进展评述[J];计算机研究与发展;2008年09期

5 蒋湘涛;胡志刚;贺建飚;;基于调用链分析的低功耗编译优化[J];吉林大学学报(工学版);2009年01期

6 夏宏,苏林萍;Cache低功耗技术研究[J];计算机工程与应用;2005年23期

7 张承义;张民选;;片内二级Cache的静态功耗优化技术研究[J];计算机工程与科学;2007年03期

8 贺小川;贾焰;;抢占阈值调度的功耗优化[J];计算机学报;2008年11期

9 王力生;郭振轲;;基于DVS的实时多核嵌入式系统低功耗算法[J];计算机应用研究;2009年01期

10 周宽久;迟宗正;西方;;嵌入式软硬件低功耗优化研究综述[J];计算机应用研究;2010年02期

相关博士学位论文 前1条

1 蒋杰;无线传感器网络覆盖控制研究[D];国防科学技术大学;2005年

本文编号：2693427