（计算机应用技术专业论文）动态静态结合的垂直节能优化策略.pdf

浙江大学硕士学位论文摘要 摘要 嵌入式系统中的能耗f 鼋题是与嵌入式设备的便捷相应而生的，由于嵌入式应 用的1 i 断丰富，系统能耗快速增长，但目前作为唯一电源的电池技术进展赶小上 能耗的增加。由此造成嵌入式系统能耗问题日益严重。 目前学术界针对嵌入式系统能耗主要有两种解决方法，即硬件节能和软件节 能，其中软件节能又分为静态节能方法和动态节能方法。静态方法在编译时刻对 代码扫描，找出可以针对目标平台特性优化的部分进行代码重构。动态电压调节 以功率与输入电压平方的线性关系为基础，在电压降低的时候可以取得较大的节 能效果。动态电源管理是设备运行时根据任务负载动态调整未来运行状态的技 术，其主要方法分为三种：基于超时的算法、基于预测的算法和基于随机最优判 断的算法。目前没有针对存储设备的成熟的节能优化方法，嵌入式存储设备的能 耗在以往的研究中受关注不多，随着嵌入式平台的大数据量吞吐需求不断增强， 磁盘能耗问题严重。 本文提出了针对嵌入式存储设备的垂直节能优化模型，包括静态代码重构方 法和动态运行调节方法。该模型从代码和设备两方面藏加节能措施，力求到最大 效果。 针对磁盘设备的静态代码重构关注嵌套循环中对于大规模数组的访问，在讨 论了数据访问模式与快速存储设备数据本地性的关系等问题后，提出了三种循环 优化方法：循环融合、循环分拆、循环扩充。在仿真平台上实现了这些方法，取 得了预计节能效果。基于超时判断的磁盘请求积累调度方法，与使用最基本超时 节能方法的设备相比，可以取得2 0 以上的节能效果。 关键词垂直优化，代码重构，请求积累，节能，磁盘 浙江大学硕士学位论文a b s a - a c t a b s t ra c t t h ee n e r g yp r o b l e mi ne m b e d d e ds y s t e me m e r g e sw i t hi t sm o b i l i t y b e c a u s eo ft h e p o p u l a r i t yo fe m b e d d e da p p l i c a t i o n ，s y s t e me n e r g yg r o w sr a p i d l y b a r e r yt e c h n i q u e c a n n o tf o r w a r da sf a s ta se n e r g y t h ee n e r g yp r o b l e mb e c o m e sm o r ea n dm o r es e v e r e h a r d w a r em e t h o da n ds o f t w a r em e t h o da r ce x p l o i t e df o r s a v i n gp o w e r s o f t w a r e m e t h o di n c l u d e ss t a t i ca n d d y n a m i cm e t h o d s t a t i cm e t h o d s c a n st h ec o d ea t c o m p i l e t i m ea n df i n d st h es e g m e n tt h a tc o u l dh eo p t i m i z e df o rt a r g e tp l a t f o r m d y n a m i cv o l t a g es c a l i n ga n dd y n a m i cp o w e rm a n a g e m e n ta r et w om o s t l yu s e d m e t h o d s b e c a u s et h ep o w e ro fc i r c u i th a sl i n e a rs q u a r er e l a t i o n s h i pw i t ht h ei n p u t v o l t a g e , l o w e r i n gi tc a ng a i no b v i o u se f f e c t d y n a m i cp o w e rm a n a g e m e n ta d j u s t st h e n e x ts t a t eo f d e v i c eb yc u r r e n tw o r k - l o a da n ds t a t e t h e r e 玳t h r e em a i na l g o r i t h m so f d y n a m i cp o w e rm a n a g e m e n t ：t i m e o u t , p r e d i c t i o na n dr a n d o mp r o c e s s e m b e d d e d s t o r a g ed e v i c e sd on o tg a i nm u c ha t t e n t i o no nt h e i rp o w e rs a v i n gp r o b l e m 、i t l lt h e i n c r e a s eo f d a t ap r o c e s s i n gn e e d , t h es e n s i t i v i t yo f s t o r a g ed e v i c ep o w e rg r o w su p t h i sp a p e rp r e s e n t st h ev e r t i c a lp o w e r - e f f i c i e n tm o d e lf o rd i s kw h i c hc o m b i n e st h e s t a t i ca n dd y n a m i cm e t h o d s t h i sm o d e li m p r o v e st h ec o d et ob ee x e c u t e da n dt h e d e v i c e i no r d e rt ot a k ef u l la d v a n t a g eo fc o d ea n dd e v i c e ，i ti n c o r p o r a t e st h e s et w o k i n d so f m e t h o d s t h es t a t i cc o d er e s t r u c t u r i n gm e t h o d sf o c u so nl a r g e - s i z ea r r a ya c c e s si nn e s t e dl o o p s a f t e rd i s c u s s i n ga c c e 鳃p a t t e r n d a t al o c a l i t yi nc a c h ea n dm e m o r y , p r e s e n t st h r e es t a t i c o p t i m i z i n gm e t h o d s ：l o o pf u s i o n ，l o o pf i s s i o n ，l o o pt i l i n g , i m p l e m e n t e dt h e s em e t h o d s o n s i m u l a t i n gp l a t f o r mw i t hs a t i s f y i n g r e s u l t w e e x p l o i t e d an e wd y n a m i c p o w e r - s a v i n gm e t h o d ，c a l l e dr e q u e s ta c c u m u l a t i o nt h r e s h o l ds c h e d u l i n g ，w h i c hi s b a s e d0 nt i m e o u ta n dp r e d i c t i o nm e t h o d s c o m p a r e dt ot h eo r d i n a r yt i m e o u tm e t h o d ，i t c a nr e d u c ea tl e a s t2 0 e n e r g y k e y w o r d s v e r t i c a l o p t i m i z a t i o n ，c o d er e s t r u c t u r i n g , r e q u e s ta c c u m u l a t i o n , p o w e r - e m c i e n t , d i s k 浙江大学磋士学位论文 图目录 图2 - 1 设备运行时功率变化 图目录 图2 - 2d p m 模块与系统组件关系 图2 - 3 请求问隔时问的概率分布 7 图2 4 半马尔可夫决策过程一一1 2 图2 5 实验模拟器与采样器结构 图2 - 6 编译优化的作用对象 图3 - l 磁盘状态转换图 图3 - 2 磁盘设备基于传统挖制方法下的状态转换 1 5 1 7 图3 3 磁盘设备精确预测到空闲状态到来时间的状态转换。2 1 图3 4 程序的能耗状态百分比 图3 5 节能优化的垂直层次 图4 - l 存储的分块布局与交替布局 图5 - lr a t s 框架的信息流 2 3 2 5 图5 - 2 磁盘的s p i n _ d o w n 和s p i n _ u p 过程 4 1 图5 - 3 磁盘设备的等待队列与运行队列。“ 图5 4 设备从状态a 到状态i 的切换 图5 5 进程对c p u 的使用情况 图5 6 基于连续时间预测的闽值设定过程 图争li n t c lx s c a l cp x a 2 5 5 开发平台 图6 - 2 循环代码优化节能效果 图6 3 应用综合循环变换后的能耗状态百分比 图6 4r a t s 模拟器对任务流的调度 图6 5 不同策略下状态时间分配片段 图6 不同策略的能耗比较。 m 4 7 4 9 5 l 5 5 ，5 5 5 6 新扛大学硬士学位论文 表目录 表目录 表3 - 1 磁盘s p i nd o w n 和s p l n _ u p 相关参数 2 2 2 2 5 2 表3 - 2 测试基准包参数信息 表6 - 1s i m p l e s c a l a r 存储部分参数设置 表6 - 2 磁盘运行参数设置 表6 3 使用循环融合重构方法的基准测试运行数据 表6 - 4 使用循环分拆重构方法的基准测试运行数据 表6 - 5 使用循环扩充重构方法的基准测试运行数据 表6 设备任务请求详细信息 5 3 5 4 5 4 表6 - 7 使用不同镶略的模拟能耗对比 j v 5 7 5 7 嚣江大学硕士警靛论文 薯1 蠢绪论 1 1 研究背景 第1 章绪论 进入新的世纪，随着科技的进步和生活节奏的不断加快，嵌入式设备的应用 越来越多的渗透进人们的生活中。手机，个人数字助理、便携式音乐播放器，无 线网络设备成为生活的必需品。各种形态备异，功能丰富的消费类电子产品成为 人们日常生活中必不可少的工具和伙伴。经过了桌面系统和服务器系统几十年的 空前繁荣发展之后，嵌入式系统正以其广阔的应用前景成为计算机领域新的增长 点，建来了曝发式的发展势头。嵌入式应用的触角已经律到了除消费类电子产品 以外的通信、医疗、金融、气象，农业、运输等各个领域中。 通俗地说，嵌入式系统就是外形、体积、功能都经过一定的精简以适用在特 定环境下，以应用为中心。以计算机技术为基础，不以通用计算为目的的计算机 系统【f 1 嵌入式系统对性能的要求不是第位的，最重要的是满足特定条件下的 需求，同时还必须达到可靠性、功能，成本、体积、能耗等诸多要求 2 1 嵌入式 系统的一大特点就是其软硬件都是可剪裁的，根据应用环境的不同可以设计制造 出不同的系统，强大的可定制性和重配置性使嵌入式系统应用焕发出长久的光彩 和无限的生机。 嵌入式系统的移动和便捷能使其深受人们的欢迎，然后事物总是两个方面 的在较小体积带给人们方便的同时也限制了使用时问的扩展，特别是随着高容 量存锗器件的广泛使用，数据交换和存镰方面的能耗惊人嵌入式系统的移动要 求使其电源无法随时补充有限的电量供给只能保证有限的续航时间随着手持 设备向功能复杂化和高度集成化发展，其功率和能耗不断加大，而电池技术并没 有取得突破性的成果，虽然锂电池已经逐步取代了镍氢电池成为新的电源主体， 但其单位体积内的电量集成技术发展速度还远远赶不上系统能量消耗的增长速 度。上述现象导致的一个直接问题就是虽然功能越来越丰富，但是很短的待机和 使用时间给人们带来了极大的不便，同时也限制了这些丰富功能向更大的市场扩 展f 3 1 浙江大学硕士学位论文第1 章绪论 1 2 研究难点 在电源供给和需求有巨大反差这一现实情况下所能做的就是通过嵌入式系 统自身的改造和优化达到节能降耗的目的。在供给条件不断改善的情况下首先通 过内部挖掘提升能耗利用率。和嵌入式体系结构分成嵌入式硬件和嵌入式软件相 适应的是嵌入式节能方法也可以分别从这两方由入手硬件方由的改进和优化多 是从集成技术上对底层的电气性能做相应的修正和增补。软件方面的改进多是从 应用在系统上的一整套执行流程的各个环节协调中入手 嵌入式系统电源管理在任务发出者和服务者两方都有不易解决的问题存在 首先。源程序作为任务供给方，其对部件的可能使用需求并不明确，很多情况下， 任务都是运行时刻动态产生的，在代码分析阶段只有有限的请求可以被识别出来 并加以优化。对嵌入式主处理器与如高速缓存和穴存等高层快速存储设备的节能 研究已经有一定的历史和成果，但是对于如嵌入式磁盘这类大容量存储设备的能 耗特点和节能方法的研究目前开展的并不充分1 4 ) 设备作为服务提供方，其动态节能效果的实现是通过在运行时刻识别空闲时 间并根据任务的到来时间和服务时间的历史信息做出对未来任务情况的判断，根 据判断对设备的未来运行状态做出调整，是一种基于统计数据的策略。虽然动态 的运行状态切换可以帮助降低能耗，理论上应该在所有可能的机会下切换状态， 并且很多动态节能方法也是基于这种考虑，但是由于硬件实现的不同，某些设备 在状态切换时会有较大的瞬时功率，这是不能忽略的，同时由于切换延迟的存在， 总时间中部件的不应期增加，对使用效率也有影响，目前的难点集中体现在如何 在减少状态切换次数的基础上增加节能效果垆i 1 3 本文工作 本文介绍的基于动态运行调度和静态代码重构的垂直节能优化模型主要针 对嵌入式存储设备的特点设计实现，在软件优化层面上综合运用动态静态两种技 术更加合理地优化从源代码编译，目标代码生成、执行等一系列流程上以宏观的 角度综合调度。以期达到最优能耗消耗的目的。 垂直节能优化策略主要包括嵌套循环代码重构和操作系统协同的请求积累 调度方法两个部分 静态代码重构着眼于源代码中对磁盘的读取和写入，这类操作多发生在大容 量数组的存取过程中。复杂操作情况下，其表现形式为嵌套的循环数组操作本 2 浙江大学硕士学位论文第l 章绪论 文提出了三种循环代码优化方法，分析其对于嵌入式存储设备的能耗影响，最后 针对数据在物理设备上的布局提出了创新想法 动态运行时刻节能优化一向是嵌入式系统巾能耗优化的重点，本文针对嵌入 式存储设备提出了操作系统协同的请求积累调度方法，其主要指导思想是在微小 影响甚至不影响系统实时响应性的前提下，尽量延长设备一次处于高功耗状态和 空闲状态的时间，减少其状态切换次数，其主要创新点在于请求积累的节能状态 转出策略和基于连续时问预测的阙值设定该方法集中了基于超时的方法和基于 预测的方法的优点。 1 4 本章小结 本文结构如下； 第一章绪论：简要介绍背景和全文章节结构 第二章嵌入式系统电源管理：介绍了手持嵌入式系统电源管理基础，电源管 理对系统可用性和性能的影响与改善：简要介绍了已有的运行时节能调度方 法和运行前编译优化节能方法 第三章嵌入式存储设备垂直节能优化模型：提出嵌入式存储设备垂直节能优 化模型，在代码从生成到运行的整个阶段中分层次，有步骤地节省能耗。 第四章垂直节能优化模型的静态代码重构：针对嵌入式系统磁盘设备的能耗 问题，提出三大类嵌套循环代码优化技术，综合它们的优点形成新的方法。 第五章垂直节能优化模型的动态运行调度：提出操作系统协同的请求积累调 度方法，以超时机制和预测机制为基础，提出基于请求积累的设备节能状态 转出策略和基于连续时间预测的积累阈值设定 第六章实现与结果分析：实现了本文薪方法，与已有节能方法进行了比较分 析 第七章总结与展望：总结了全文，对本文未解决的问题做了阐述，探讨了可 以继续研究的方向。 3 拼江大学硕士学位论文第2 章嵌入式系统电谭瞢理 第2 章嵌入式系统电源管理 2 1 嵌入式系统能耗分析 嵌入式系统的中央处理器和总线等组件与桌面系统在电源管理方面有很多 相同之处，比如有传统的休眠和挂起等状态 6 1 。当系统处于这些状态时，部件的 供电电流被切断或者只有必要的几个模块维持供电，其他部分都处于断电状态 由于耗电部件的减少使系统总体能耗降低。而进入这种状态的时机都是血用户手 动选择或者按照用户预先设定的定时机制由系统自动执行完成的。上述内容可以 说是最原始的电源管理理念，即在系统需要工作的时候供电，而没有任务的时候 在保持必要的响应速度和计算能力的前提下将空闲设备全部关断川。桌丽系统秘 服务器系统在有交流电源供电的情况下的节能纯粹是从环保角度出发考虑的，其 前提是对性能几乎没有重大影响，所述的关断动作都是在状态完全肯定的情况下 发生的。这种节能方法没有涉及在系统正处于工作状态时的运行参数调节，所以 可以归为静态节能方法的范畴中 对于嵌入式系统来说，电量供给是极为宝贵的，是有限度的资源在系统负 载并不重的时候满负荷运行会造成大量的能量浪费。频繁的使系统进入断电状态 也是不现实的，因为设备开关的瞬间电流要高于平稳运行的电流，所以开关瞬间 的爆发能耗是不能忽略的 s 1 同样，当设备被从完全断电状态冷启动进入正常工 作状态是需要一定的时间延迟的，频繁的开关切换对于系统整体性能有难以估量 的潜在影响。这些原因是导致电源歼关切换方法在嵌入式系统中不能发挥更大作 用的原因。 对于可变电压输入的嵌入式设备来说。时钟和电压的主动调节是一项重要煎 节省能量消耗的手段然而当上层应用处于一种爆发式的对处理器的访问时，是 很难在操作系统和硬件层面上取得良好的节能效果的唧。一种新的观点要求应用 程序是能耗敏感的并且将其未来一段时间的应用请求发给一个新设立的中央调 度控制机构，由这个机构统一调节处理器电压和相应的时钟频率。 2 2 动态电压调节 如上文所述的完全电源开关方法不能满足嵌入式系统的要求，在嵌入式系统 中支持高级的动态电压调节c d y n a m i cv o l t a g es c a l i n g ) 技术“0 1 动态电压调节技 术是从“减速”的角度来达到节省能耗的目的的，即系统或系统的某个部件不以 新江大学硬士学位i e 文 第2 章嵌入式系统电源管理 最高运行频率或速度自始至终的完成所有计算和处理任务，当系统负载不重时， 动态调节各个运行器件的输入电压，使部件的处理能力正好可以满足任务要求， 这样就可以在不显著影响性能的前提下达到最理想节能的目的 新一代的处理器和总线支持动态电压调节( d v s ) 技术，已知的实验证明 d v s 可以取得比常规的关断技术更好的实时能耗调整收益。d v s 技术利用电压 和能耗之间的二次方关系有效地折衷了能耗和延迟，使频率和电压之问呈线性增 长关系。d v s 技术减少能耗的代价就是完成同样任务的执行时问会因为频率的降 低而延长。d v s 技术主要适用于频率可调节范围大的嵌入式主处理器，而因为任 务在嵌入式主处理器中的运行时间延长导致整个系统的带电服务时间延长，嵌入 式主处理器之外的其它部件因为功能和设计关系并不能与嵌入式主处理器一样 傲到输入供电电压的动态调节，因此虽然嵌入式主处理器在延长的时间内减少了 能耗，但是其它部件是有额外能耗产生的l i i l 。 在使用c m o s ( c o m p l e m e n t a r ym e t a lo x i d es e m i c o n d u c t o r ) 技术的嵌入式主 处理器中功耗可以分成两个主要部分： 内核消耗功率和外部输入输出接口消耗的功率总功率是两者的叠加 1 2 1 。对 于内部功率，主要与供电电压大小和时钟频率高低有关；对于外部功率，还与数 据和地址总线的宽度有关内部功率的计算公式为： p 。= c r v 2 f ( 公式2 1 ) 其中p 。是c m o s 芯片的动态功耗，c l 是c m o s 芯片的负载电容，v 是 c m o s 芯片的工作电压，f 是c m o s 芯片的工作频率0 3 1 由该公式可知，c m o s 电路的功耗与供电电压成平方关系供电电压越大，时钟频率越快功率消耗越 大，因此能够在低电压下工f # 的嵌入式主处理器会有更好的能耗表现。对于既定 的处理器，如果能够尽量降低运行时的电匿和频率，会很快的达到降低能耗的目 的。在需要大量存取数据的场合下。嵌入式主处理器的数据和地址总线宽度也是 一个在能耗方面值得考虑的问题，因为每一条总线都有功率消耗，所以较宽的外 部总线必然带来更多的能耗损失。但是如果不恰当地使用了较窄地址总线的话， 大量数据传输会导致存取次数增多，增加读写周期，也会使能耗上升【1 4 】 c m o s 电路的静态功耗不随输入电压和频率的改变而改变，在整体服务时间 延长的情况下，在静态功耗部分会有更多损失这部分损失与系统其它部件因为 时问延长造成的额外功耗一起考虑是否能够抵消嵌入式主处理器使用d v s 技术 带来的节能效果构成了该技术能否达到设计标准的前提。 在众多的运行时能耗管理技术中，d v s 因为卓越的节能效果已经涌现为一种 巍扛大掌磺士学位论奎 第2 章嵌入式系统电源管理 重要的手段，d v s 通过调节能耗部件的供电电压和时钟频率达到调节能耗的目的 ”“。在工作时，d v s 根据运行环境和系统负载等条件将不同的能耗部件置于合理 的电压频率二元组之中。使用d v s 的前提是满足性能要求虽然应用程序级别 的d v s 在当前主流的平台上是支持的，如i n t e lx s c a l e 系列但是更多的d v s 调 节是通过操作系统的级别得到的，这是因为d v s 模式切换带来的时问和性能损 失对单独的程序而言是过大且难以控制的。根据有限的程序和处理器参数，可以 得出达到最大节能效果的d v s 分析模型，寻找出编译时d v s 对节能有正而影响 和负面影响的环境场景，推断当中央处理器的参数改变时使用编译时刻动态电压 调节可以带来的节能效果。然后通过观测实际运行数据得出理论最优的动态电压 调节模式可以取得的节能效果。 早期的研究工作都孤立地把嵌入式主处理器作为研究对象，并且解决了最小 化其动态能耗的蚵题。后来的工作更多的投入到解决包括静态和动态能耗的整体 节能问题上，包括考虑到了减慢计算子系统和通讯子系统的速度以对能耗问题让 步，更近的研究己开始关注将嵌入式主处理器和内存系统联动考虑，得出降低内 存访问速度会导致能耗升高的结论。在关注处理器能耗的同时，有忽视其他挂起 资源能耗的趋势。有数据表明，在整个任务执行期间，内存有3 0 - 9 0 的时问是 处于全功耗状态的”6 】。随着网络通信能力的提高，单机系统需要分发的数据越来 越多，网络子系统和存储子系统活动时间和挂起时间都有增加。 2 3 动态节能调度方法 动态电源管理技术d p m ( d y n a m i cp o w e rm a n a g e m e n t ) 0 7 1 是通过将不工作 的系统组件关断或利用下层的d v s 技术减慢运行速度降低性能，并在负荷加重 对将其重新置于全速状态以减少整体髓耗就是在最小运行代价，最优服务质量 的前提下提供要求的响应质量和性能表现。 d p m 能否发挥作用的前提是系统运行过程中的负载变化和不确定性，无论对 于简单系统还是通过网络链接的复杂系统都是适用的另一个基本前提是d p m 能够有效而准确地预测系统负载的波动并能发出有利于减少能耗的命令并最终 执行，在预测过程中d p m 自身也必然会有能耗损失，这一部分不能超过节省的 能耗l l 研d p m 对负载加以观察和预测并产生控制过程，成为策略策略是在不 同的指导思想和算法的基础上扩展改进得到的，常见的d p m 策略会在本节随后 加以详述。 系统模型是一个能接受外界环境连续的激励的实时嵌入式系统，系统为了响 6 浙江大学磺士。肇符谂文第2 章嵌入式系统电潦管理 应外界激励有能景消耗发生。每一个激励响应对在系统中的表现形式是任务，即 系统的处理单元是以任务的形式给出的在服务任务的过程中，系统可能会使用 包括处理器、总线、内存、存储器、网络的各种资源，这些资源的使用造成的能 耗全部计入该任务总的能耗中。任务刘来的时间是随机的，各个任务是独立的， 且总体的任务到来分布也不严格服从任何概率分布，但是可以根据合格的样本数 量通过建模得出一定符合事实的结论用以验证d p m 方法的有效性。理论情况下， 在已知系统任务到来时间具体信息时，是可以掘此开发出最佳d p m 策略的i 1 9 1 处于系统层级时，系统组件内部结构是不可知的，可以将电源管理系统抽象成由 策略选择机构控制的相互关联的功耗可控部件的组合。组件是完整的系统子模 块，其基本特征是有多种工作状态，各个工作状态的基本能耗水平不一样，且能 耗越岛的状态工作效率越高，同等工作量可以在更少时蜘内完成。各种不同的工 作状态之问转换屉有爆发功率和时间延迟的 图2 - 1 中，在时问点发生7 运行状态改变，在转入正常运行状态之前有一功 率突发时刻，在这段时刻中系统不处于正常运行状态，时间延迟长短与电气性能 有关 图2 - 1 设备运行时功率变化 如图2 - 2 所示，嵌入式系统的d p m 模块和系统各个组件之问都有交互，d p m 模块与操作系统和底层的设备驱动程序之间的交互是双向的，因为操作系统掌控 所有资源，很多命令的执行也是由操作系统发出的【划，而对嵌入式系统外部设备 发布命令时因为效率的关系需要直接与设备驱动程序交互。同样，d p m 的命令也 ， 新托丈擘硬士学静论文第2 章嵌入式系统电源管理 会直接或问接地传达到嵌入式主处理器、系统时钟、电源、内存控制器等各个部 分又因为d p m 模块选择节能策略和做出决策需要信息支援，所以操作系统和 设备驱动程序得到的关于运行的最新信息也会发送到d p m 模块中。 图2 - 2d p m 模块与系统组件关系 综合的动态电源管理是一个统筹整个系统的架构，不仅拥有完善的信息收集 和发布系统，还有复杂而多样的策略可供选择。设计优秀的d p m 系统是层级分 明的，上层d p m 模块会在宏观层级发布运行调整命令接到命令后的系统各个 组件又会启动各自的d p m 子系统，在受限条件下最大化地达到局部能耗最优 “能量优先级调度( e p s ) ”的调度方法 2 i j 可以根据请求的期限和重合度重新 对所有请求排序首先安捧低优先级任务发出的请求，然后是高优先级的任务请 求，这样可以便于低优先级任务请求被后来的高优先级任务请求抢占。e p s 并不 一定能生成最佳的解决方案。但是因为算法本身的复杂程度较低，可以被用来作 为自我增加的再现算法当系统中有新的任务到来或者老的任务终结时e p s 就会 根据当前系统状态动态调节时钟频率对时钟调度模型的定义，分别定义s i ，d i ， 白为任务j 的开始时间，结束时间和在高功耗状态的运行时间。对于某个给定的 时阃段将其划分为若干小时阃段，且在每个小时问段内只有给定任务集的任务执 行对其中每一个任务计算其优先级p j ，选择还没有被调度过并且拥有最低优先 级的任务j 不断重复这个过程直到所有的任务都被调度过，这其实是一个不断 s 游扛大学硬士学位论文 第2 章嵌入式系统电源管理 “水涨船高”的过程。该算法并不总是可以寻找到最优的解法因为其仅仅能避 开与任务j 有交集的其他任务该算法的复杂度取决于需要循环调度的任务i 的 个数从硬件的角度来讲，时钟调度调节是一项重要而有效的节能手段基于操 作系统的方法。如间隔调度确实也会取得节能效果，但是以失去任务执行时间的 有效性为代价的。但是通过将上层应用程序改造成能耗敏感型，就可以在规定的 执行时间内节省更多能量。日后的工作更多的集中于怎样权衡执行时间损失和能 耗降低方面；同样也能够应用在除了中央处理器以外的其他嵌入式系统部件上 面。 对于可变电压输入的处珲器来说，时钟和电压的主动调节是一项重要的节省 能量消耗的手段。然而当上层应用处于一种爆发式的对处理器的访问状态时，是 很难在操作系统和硬件层砸上取锝良好的书能效果的。就嵌入式系统本身应用而 言，是否使用主动的d p m 技术对系统适用性和可靠性有很大的影响相对于硬 件的发展和节能技术来说，人们相对低估了通过修改运行在硬件上面的软件以节 能的巨大潜力系统级的动态电源管理算法通过选择性地将空闻的组件置于低功 耗状态来达到节省能耗的目的能耗管理器观测系统负载并发出状态切换的指令 给具体设备。在性能要求下的节能策略选择是对于很多便携式系统都很重要的策 略优化问题旧j 适用于嵌入式系统的d p m 算法有很多，如预测算法、随机算法等。这些算 法基本上可以归为三类：基于超时的算法；基于预测的算法以及基于随机最优翔 断的算法1 2 3 1 2 3 1 基于超时的算法 基于超时的算法是最简单也是最直接的节能策略假设有两个运行状态分别 是a 和b ，a 是高功耗状态而状态b 相对节能t l 是系统在低功耗状态上运行的时 间，因为状态切换会有时间延迟和额外的能耗发生，而这两个数值都是与具体设 备相关的，所以我们在这里也以已有参数的形式给出：e a b ，1 k ，e h ，1 h 分别为 从状态a 向b 转换消耗的能量和时间以及从b 向a 转换的能量和时间。n ，p b 分 别是设备运行于a ，b 状态的设备功率。为了求得在能耗相当的情况下t s 的值， 可以得到如下等式： t s p b + e a h + 琶b 薯= m b + b + ) p a( 公式2 2 ) t s = 【e a b + e a 一( t a b + t b a ) p a 】( p a p b ) ( 公式2 3 ) 若设备在状态b 的停留时间不能超过t i ，那么两次切换的功耗之和大于在相 9 浙江大学硕士学位论文 第2 章嵌入式系统电源管理 同时间内维持a 状态不变的功耗。所以，为了保证节能效果，设备每次处于b 状 态的时间必须大于t 1 超时方法主要有两个特点：第一，调度不足根据设备负载 来决定的；第二，通过调节预设的超时阈值就可以改善节能效果。简单的原理使 基于超时的策略可以通过修改来进一步提高性能。 适用于块操作设备的简单的基于超时的方法，其方法简单，易行。但是缺点 也很明显，由于缺乏灵活性，如果每次新的访问请求部在超时之后马上来临，那 么系统在时阃延迟和多余能耗方面都会有更大损失陋j 。 2 3 2 基于预测的启发式算法 基础的基于超时判断的算法是很原始的，对于负载的统计特性完全未知的系 统来说，将超时阈值固定的算法是非常低效的1 2 ”。如前文所述，d p m 获得更多 信息有助于选择更优的节能策略虽然系统任务的到来时间点是完全未知的，但 是通过对不同的系统和设备长时间的任务到来情况观察表明：一般情况下，各个 任务到来的时间间隔是独立同分布的，且理论情况下可以抽象成瞬间完成豹。通 过对大量任务到来的学习，可以对其建模。用不同的理论数学模型拟合其分布， 使大多数任务点坐标图中的点在模型曲线上 2 6 1 ，如图2 3 所示 但是对系统任务到来分布进行建模也有很直接的缺点，即必须保存大量的历 史数据。对大量数据进行分析也是非常耗时的，这样会增加嵌入式主处理器和内 存子系统等部件的全功率运行时间。如前文所述，为了节能而进行的动作本身增 加的能耗如果超过了节省的值是得不偿失的。 采用回归等式来预测下个空闲时间的长度，然后根据预测所得的值确定要 使用的d p m 策略是比较可行的网公式( 2 4 ) 展示了使用回归方法预测即将到 来的空闲时间的方法，其中1 n ) 是下一个将要到来的任务相对于已经到来的最后 一个任务的间隔时问：t i ( n - 1 ) 是最后一个已经到来的任务和倒数第二个到来的任 务之间的时问间隔，即最后一个已知的时间间隔：t p ( n 1 ) 是上次t p 的预钡9 值在 这个算法中，只需要保留两个参数作为历史值，且计算部分并不复杂，产生的额 外能耗有限。a 是平衡参数，可以根据预测准确程度动态修正两个历史参数在公 式中的权重 j 挚 江大学硬士学位诗文筹2 章嵌入式系统电源管理 图2 - 3 请求间隔时问的概率分布 基于预测的d p m 算法通过预测可以消除部分负载的不确定性。预测算法是启 发式的，通过模拟仿真可以通过比较其优化程度，如果算法中参数过多就很难调 节其复杂性，难以得出最优化配置。预测算法仅仅从能耗最小化的角度出发， 但是能耗减少要在性能允许的情况下进行，所以预测算法可能会因为过分强调能 耗面导致性能下降过多。这不符合d p m 的基本原则。 t p ( 。) = a 1 ；。一1 ) + ( 1 一a ) t p ( ，i ) ( 公式2 4 ) 2 3 3 基于随枫最优判断的算法 启发式的节能算法的效果必须在模拟环境下或者实际测量效果中得到验证 并且算法也不能够提供任何的全局优化解决方案离散时问马尔可夫决策过程 ( d m p ) 要求任务到来请求符合固定的几何分布，这是在实际生产中不能达 到的理想状态所以这种算法也是实用性较低的 2 s l 。其一大缺点就是决策评估是 周期性不断进行的，即使在休眠期间也不停止，这是相当消耗能量的。离散时间 算法的好处在于策略重估是在周期性时间点重新进行的，所以可以更好的适应不 符合严格几何分布的请求到来情况。 离散时间马尔可夫决策过程的扩展是连续时间马尔可夫决策过程( c t m d p ) 研究显示，完全遵照指数到来分布模型的空闲状态下能耗是相当高的，而且性能 婿打大掌磺士学位论文第2 章嵌入式系统电源管理 也很低下。连续时间马尔可夫决策过程町以进一步演化为半马尔町夫决策过程 ( s m d p ) 该模型将同样时间段内的请求到来作为指数分布对待。进一步的改进 称为时间索引的马尔可夫链决策过程，这种算法融合了事件驱动的半马尔可夫决 策过程和离散时问马尔可夫决策过程的优点，仅仅在有新的事件到来时才对策略 使用做重评估。在空闲状态下，策略决策仅仅在转入休眠状态时才被重估，从而 达到了节能的目的。 图2 4 展示了事件发生后的半马尔可夫决策过程，能耗管理器每次在有新的 事件发生时做决策。t 被定义为事件到来时问问隔集合i = o ，l 2 1 】。每一个 都是两个连续的请求之问的时间闻隔，将s 。定义为在i 决策时段的系统状态。 将a i 定义为在i 决策时段的系统动作。计算在系统状态s 下的系统动作a l 发生 后在时阃瓦内下一个事件将要发生的概率e 圈2 幸半马尔可夫决策过程 每一个状态下的系统描述都是以能耗状态为标准进行的优化后的结果与模 拟的数据也符合的很好。随机最优判断算法相对于预测算法而言有如下几个优 点：i ) 能够从全局观点出发，在多个低功耗状态中找到最优的电源管理方法。2 ) 能够在有一定性能约束条件下给出功耗最低问题在多项式时间内的确定解。 基于随机最优判断的算法不易实现，而且若要达到预计效果，随机过程本身 对计算部件的能耗需求也不可忽略，其效果无法确定。 2 4 编译优化节能方法 能耗问题可以在自项向下的垂直体系结构的各个层级得到解决：设备层、逻 1 2 浙江大学磺士学岔论文第2 章嵌入式系统电源管理 辑层、操作系统层、微体系结构和编译器层目前有很多关于编译器节能的特定 想法，但是很少有系统的将这些想法付诸于系统改进如何用量化的方法确定在 对特定的嵌入式处理器和编译器优化能耗建模过程中的极限，从能耗的角度分析 编译器优化和处理器内部工作机制之问的相互影响是亟待解决的问题 对于低功耗研究领域而言，通过对软件的修改来达到节省能耗的目的一直都 是一个被忽视的问题。造成这种缺失的最主要原因是一直以来都缺少一种有效的 分析软件能耗的方法 2 9 1 近期这方面的工作取得了突破进展，在精简指令集的计 算机上实现指令级的调度管理可以达到控制路径上的选择最小化在i n t e l 4 8 6 d x 2 处理器上的实验表明进行切换操作并不能带来非常大的整体能耗节省。 这种技术主要是针对电路状态损耗的减少来降低能耗的，但是在实验平台上运行 的指令队列重毅捧序并没有使其取得超过2 的能耗节省，在其他平台上的节能 效果也会由于源代码的不同而改变，需要有具体的测量手段。 高层的编译器优化已经被广泛用于基于块的代码加速【卅诸如此类的编译优 化手段在嵌入式信号处理和多媒体系统应用中正变得越来越重要。以往这些优化 方法都是作为性能调优的重点，但是在由电池供电的系统中能耗限制是一个重要 的影响因子嵌入式领域的一大趋势就是将整个系统集成到一块芯片当中快速 发展的硬件技术使软件系统更加复杂，功能更加丰富，但是需要有更强大的编译 器技术来充分利用这些复杂的软件功能 2 4 1 编译优化节能层次 编译代码优化被划分为三个层次：算法级别，数据级别和指令级别o i l 采样 工具及指令周期级别的能耗模拟器使嵌入式系统的单位性能能耗与源代码相连 这些工具可以用来分析和验证。在实验平台上对m p 3 解码工具进行实验表明可以 又快又简单地重新设计m p 3 解码软件以适应实时运行环境并更加节能。在能耗减 少的同时提升运行性能。f p g a ( f i e l d p r o g r a m m a b l eg a t ea r r a y ) 硬件模拟可以 应用于系统除错，但是对于能耗和性能估测无能为力。 代码优化就是将高级语言翻译成目标机上的优化过的机器码。在有限的优化 手段中，倾向于手动优化代码，首先从抽象的宏观层次上解决问题，然后逐步向 下收紧范围。优化层级的最上层是算法优化，首要的任务是识别出一个任务的核 心计算部分，通常上来讲部是消耗时问和能量最多的。大多数编译器的优化方法 定位于高性能的通用计算机，嵌入式系统上使用的优化编译器开发和研究工作甚 少当前，很多嵌入式程序都是由有经验的程序员直接用汇编代码编写的，代码 流大学硕士学位论文 第2 章嵌入式爰统电源管理 优化也是基于人工技术。 算法层是整个能耗优化中最上层的部分，也是最有优化潜力的部分。但是风 险与收益并存，开发和测试新的算法非常耗时间并且极易出错人力资源的有限 性和偶发性决定了将大量人力投入到风险很大的替换算法开发上是很不现实的 对于算法效能的渐进式估测通常都是不准确的。基于以上考虑，首先重点关注的 应是内核，大部分的运行时间和能量部消耗于此；其次是不开发全新的算法，在 原有算法的基础上加以改进，保证兼容性和稳定性。 在算法层之下可以优化的是被算法操纵的数据的表现方式。主要目的就是使 目标系统和未处理的数据之间有良好的匹配。浮点运算是耗时长的，在对浮点运 算支持不好的体系结构中是异常缓慢和高眈耗的。数据优化能带来大量的性能提 丹和能耗优化，且不需要大规模的代码重写。 指令流优化足三个层次中底层的优化手段，紧贴硬件【，2 1 。首先通过广泛分析 确定重要的循环等代码段，然后对该段代码仔细分析，代码重写以取得更好的运 行效率。常见手段有循环展开，循环融合，软件流水线化等。在循环的最里层， 代码可以直接内联展开，得到执行效率的提升研究对象由带有二级高速缓存的 徽处理器，片外存储，数字模拟转换接口和电池组成精确到时钟周期的能耗模 拟器可以对每一个系统组件进行以周期为单位的能耗模拟数据，使高度细节化的 硬件和软件分析成为可能这种精确到每个时钟周期的能耗模拟器的一个重要缺 点是代码优化带来的能耗节省不能很容易地被估测出来 模拟和采样器按如下的步骤运行；源代码由针对指定平台的编译器编译成目 标代码编译器输出的是精确到每个时钟周期的模拟器可以执行的程序( 通常都 是汇编代码) 和各个子程序在可执行程序中的地址映射表，该表可以供采样器收 集数据为了提高模拟运行豹速度，需要预先设定每次采样的时间问黼。对间闻 隔的大小和采样的准确度成反比。和模拟运行速度成正比 系统的总能耗是各个子部分能耗的总和，如公式( 2 ，5 ) 所示 e c y c i e = e c p u + e h + e m 蛐+ e d c + e l 2 + e t 咖 公式( 2 5 ) 采样器和精确到时钟周期的模拟器同步运行，定时对模拟运行结果采样，利 用在编译时刻收集的信息将能耗和性能映射到运行的函数中，图2 - 5 所示是模拟 器与采样器的结构图。 1 4 浙旺大掌硬士学位论文第2 章嵌入式系统电源管理 图2 - 5 实验模拟器与采样器结构 2 4 2 编译优化节能手段 过去的2 0 年中，源代码级的高层优化技术很多针对于循环和控制对于有 着并行体系结构和较深存储层级的系统来说，增加的本地性和并行性是非常有帮 助的 现代代码生成器的指令选择模块通常是由被称作代码生成器的软件自动生 成的，这些程序将目标平台的指令集作为处理规范这些规范定义了在生成的代 码中可以接受的指令集模式。在编译时期，这些代码生成器接受源代码块的中间 表示，使用模式匹配和动态编程技术加以处理。根据指令集模式寻找种能耗最 小的方法将源代码转换成中间表示形式。 包括i c c 在内的多数编译器是根据执行的时钟周期数来测定代价的。值得注 意的是，以能耗为标准和以时钟为标准的代码生成器几乎能生成完全一样的代 码。造成这一现