（计算机应用技术专业论文）嵌入式系统节能模型研究.pdf

浙江大学硕士学位论文摘要 摘要 随着嵌入式计算技术的飞速发展，嵌入式系统的功能变得越来越强大，然而 系统的功耗却成为嵌入式系统设计的主要制约因素之一。嵌入式系统的功耗可以 在静态和动态两个技术范畴内来降低，随着系统功能增强和集成度的提高，静态 技术已经不能完全满足系统对功耗的要求，最近的研究集中在动态低功耗的设计 上，即动态电源管理( d p i ) 和动态电压调节( d v s ) 两种主流技术。 在完成本论文的过程中，主要做了如下工作； 1 分析了动态电源管理技术( d p m ) 的主要原理，研究了三种d p m 策略： t i m e - o u t 策略、预测策略和随机策略，并分析了这三种策略的存在的闯题及其改 进方向。 2 研究了动态电压调节技术( d v s ) ，分别研究了非实时d v s 调度算法， 和实时d v s 调度算法。分类讨论了基于时日j 问隔的d v s 调度和基于任务分析的 d v s 调度。研究了f l a t ，p a s t ，p e a k ，a v g n 算法。比较了各算法的优缺点。 3 针对具有多种运行状态的可调节微处理器并且任务间带有网状优先级的 嵌入式实时系统建立了精确的数学模型( r r 工) v s 模型) ，提出了带约束性最短截 至期限优先且可回溯算法( r b e d f 算法) 来对任务集执行顺序排序。 4 针对多种运行状态的可调节微处理器的特性，提出了通过对任务集进行 子集划分，把子集抽象成背包问题来确定任务的工作电压的方法。 关键词嵌入式系统，动态电源管理，动态电压调节，r r d v s 模型 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t a st h et e c h n o l o g yo fs y s t e mi n t e r g r a t i o nk e e p so nm o “n gf o r w a r d ，t h e f u n c t i o n a l i t yo fe m b e d d e ds y s t e mb e c o m e s i t l o r ea n df f l o r ep o w e r f u l b u tt h ep o w e ri s b e c o m i n go n eo ft h ef i r s tc o n s t r a i n t so fe m b e d d e ds y s t e md e s i g n p o w e rr e d u c t i o ni n e r n b e d d e ds y s t e mc a nb er e a l i z e db ys t a t i ca n dd y n a m i ct e c h n i q u e s h o w e v e r , s t a t i c t e c h n i q u e sc a l ln o ts a t i s f yt h es y s t e mr e q u i r e m e n t so np o w e rc o n s u m p t i o nw i t ht h e i m p r o v e m e n to ns y s t e mf u n c t i o n r o n tr e s e a r c hh a sc o n c e r n t r a t e do i ld y n a m i c p o w e rr e d u c t i o nt e c h n i q u e s ，w h i c hi n c l u d ed p m a n dd v s t h em a i ne a n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 w ea n a l y z et h em a i np r i n c i p l eo ft h ed y n a m i cp o w e rm a n a g e m e n t ( d p m ) ， s t u d yt h r e ek i n do fd p ms t r a t e g y ：t h et n n e - o u ts t r a t e g y , t h ef o r e c a s ts t r a t e g ya n d s t o c h a s t i cd e c i s i o nm o d e l 2 w es t u d yt h et e c h n o l o g yo f d y n a m i cv o l t a g es c a l i n g ( d v s ) w es t u d yt h en o n - r e a l t i m ed v sa l g o r i t h m , w i t hr e a l t i m ed v sa l g o r i t h m w es t u d yf 眦p a s t , p e a k , t h ea v g na l g o r i t h m a na n dc o m p a r ew i t hv 撕o u sa l g o r i t h m sg o o da n db a d p o i n t s 3 w ep r o p o an o v e la p p r o a c ht os o l v et h ep r o b l e mo fs a v i n ge l e c t r i c i t ye n e r g y i n 啪b e d d e dr e a l - t i m es y s t e m o b s e r v i n gt h a tt h e r ea r em a n yt y p e so f r u n n i n gs t a t e si n t h ea d j u s t i n gm i c r o p r o c e s s o r sa n dn e t w o r kp r i 嘶t ye x i s t sb e t w e e nt h et a s k sf r o mt h e t a s ks e t , w ec o n s t r u c ta na c c u r a t em a t h e m a t i c a im o d e lf o rt h i sp r o b l e m t h e nw e p r e s e n tar b e d fa l g o r i t h mt os o r tt h et a s ks a 【s 4 i nv i e wo f m i c r o p r o c e s s o rw i t ht h em a n yk i n d so f r u n n i n gs t a t u sc h a r a c t e r i s t i c , w ep r o p o s ean o v e la p p r o a c ht os o l v et h ep r o b l e mo fh o wt os e tt h ev o l t a g ef o rt h e t a s ks e t s w es u b d i v i d et h et a s ks e t si n t os m a l ls u b s e t s a i d e rt h es u b d i v i s i o n , w e s p e c i f yt h ew o r kv o l t a g eb yc o n v e r t i n ge a c hs m a l ls u b s e tt ot h el 【1 1 a p s a c kp r o b l e m k e y w o r d s e m b e d d e ds y s t e m ，d y n a m i cp o w e rm a n a g e m e n t ，d y n a m i cv o l t a g e s c a l i n g , r r d v sm o d e l 浙江大学硕士学位论文图目录 图目录 图1 1i n t e l 微处理器功耗趋势图2 图2 1 系统负载情况简图6 图2 2 没有进行动态电源管理是的能耗图6 图2 3s t r o n g a r ms a 1 1 0 0 的不同工作模式能量转换图7 图2 - 4 采用d p m 策略时的系统能耗图8 图2 5 排队模型1 2 图4 1 任务自j 带有网状优先级的有向图2 4 图4 _ 2 预执行任务l 后的有向图和找2 5 图4 - 3 预执行任务2 后的有向图和栈2 6 图4 - 4 预执行任务3 后的有向图和栈2 6 图4 - 5 预执行任务4 后的有向图和栈2 7 图4 _ 6 预执行任务5 后的有向图和栈2 7 图禾7 任务5 出栈后的有向图和栈2 8 图禾8 任务4 出栈后的有向图和栈2 8 图4 9 预执行任务5 后的有向图和栈2 9 图4 - 1 0 预执行任务4 后的有向图和栈2 9 图4 1 1 全部任务被执行后的s 栈的情况3 0 图4 - 1 2 基于最优和次优模型能耗对比图3 5 图4 - 1 3 最优和次优模型c p u 占有率对比图3 6 i l l 浙江大学硕士学位论文表目录 表目录 表4 1 有向图的初始节点的五元组2 5 表4 - 2h r r d v s 启发式求解方法与d p m ，d v s 等算法在功耗上的比较3 4 i v 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 嵌入式系统概述 1 1 1 嵌入式系统介绍 i e e e 对于嵌入式系统的定义是：a nd n b c d d c ds y s t e mi st h ed e v i c e su s e dt o c o n t r o l ，m o n i t o r , o ra s s i s tt h eo p e r a t i o no f e q u i p m e n t ，m a c h i n e r yo rp l a n t s 嵌入式系统 是“用于控制、监视或者辅助操作机器和设备的装” 在中国嵌入式系统领域，比较得到大家认同的嵌入式系统概念是：嵌入式系 统是以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用系统 对成本、体积、功耗有严格要求的专用计算机系统。 嵌入式系统的核心是嵌入式微处理器。嵌入式微处理器一般具备以下几个特 点： ( 1 ) 可扩展的处理器结构，能最迅速地开发出满足应用的最高性能的嵌入式微 处理器i i l 。 ( 2 ) 嵌入式微处理器必须功耗很低，尤其是便携式及移动通信设备中嵌入式系 统。 ( 3 ) 具有功能很强的存储区保护功能。嵌入式系统的软件结构已模块化，需要 设计强大的存储区保护功能，来避免在软件模块之间出现错误的交叉作用m 。 1 1 2 嵌入式系统发展历程 单片机开创了嵌入式系统独立发展道路。微型计算机的体积、价位、可靠性 都无法满足广大对象系统的嵌入式应用要求，因此，嵌入式系统必须走独立发展 道路。将计算机做在一个芯片上，从而开创了嵌入式系统独立发展的单片机时代 1 1 1 单片机诞生于2 0 世纪7 0 年代末，经历了s c m 、m c u 、s o c 三大阶段： ( 1 ) s c m 即单片微型计算机( s i n g l ec h i pm i c r o c o m p u t e r ) 阶段，主要是寻求 最佳的单片形态嵌入式系统的最佳体系结构。 ( 2 ) m c u 即微控制器( m i g r o c o n t r o l l e ru n i t ) 阶段，主要的技术发展方向是； 不断扩展满足嵌入式应用时，对象系统要求的各种外围电路与接口电路，突显其 对象的智能化控制能力。 浙江大学硕上学位论文第1 章绪论 ( 3 ) 单片机是嵌入式系统的独立发展之路，向m c u 阶段发展的重要因素，就 是寻求应用系统在芯片上的最大化解决n 1 1 2 电源管理概述 1 2 1 电源管理必要性 随着计算机性能的逐渐提高，系统功耗也随之增加，在过去的几十年里，处 理器功耗从l w 增加到了1 3 0 w 。图1 1 【2 1 反映了i n t e l 处理器功耗的增长趋势。 1 觚0 0 0 鲤壁即恻蹦蓼孽鬻群巷秘瀚笋蝤捧a 峨埝) 7 l飘7 8聪徼铷锚抛 图1 - 1i n t e l 微处理器功耗趋势图 据i n t d 公司的c t op a tg e l s i n g e r 先生预测，到2 0 1 0 年i n t e l 公司制造的微处 理器内部将包含1 0 亿颗晶体管，主频将达到3 0 g h z ，其功率密度将与核电站的 相当 2 1 。鉴于此，开发性能、功耗和发热平衡的低功耗微处理器技术迫在眉睫， 经过业界的努力，低功耗处理器获得了突破性进展。 1 2 2 低功耗处理器技术 目前市场上的低功耗处理器主要采用以下几种节电技术： i n t e ls p e e d s t e p ：s p e e d s t e p 技术可以让处理器在最高性能模式，电池优化模式 曲种1 = 作模式之间任意地切换。最高性能模式指的是当笔记本电脑与交流电源连 接时，可提供与台式机相似的性能；电池优化模式是指当笔记本电脑使用电池时， 2 浙江大学硕士学位论文 第1 章绪论 会让笔记本电脑的性能发挥与其电池使用时间之间达到最佳的平衡。 t r a n s m e t a l o n g r u n 采用l o n g r u n 技术，c r u s o ec p u 可以在运行过程中， 自动检测其工作量，并动态、平稳地、分多级、在线调整c p u 的工作频率和工作 电压，使程序运行所消耗的能量达到最优化，而不需要停止c p u 的工作。 a m dp o w e r v o w f ：p o w e r n o w ! 会按不同应用程序的需要，动态的调高或调 低处理器的电压和主频，使处理器更能切合实际应用的需要，从而延长笔记本电 脑电池的使用时间，并延长电池的寿命。 1 2 3 电源管理规范 1 2 3 1a p g 高级电源管理( a d v a n c e dp o w e rm a n a g e m e n t ：a p m ) 是i n t e l 和微软联合开 发并于1 9 9 2 推广的接口规范。 为了适应不同的计算机，a p m 定义了一套代表不同节电水平的“状态”( s t a t e ) ， 下面是a p m 规范所规定的5 种状态： f u l lo n 状态：需要完全的电力供应，系统以全速运行。缺少a p m 或者关闭 了a y m 功能的计算机就是工作在这个状态下。 e n a b l e d 状态：激活a p m 控制系统的状态，但是没有激活任何的节电功能。 虽然处于完全电力消耗模式，但是可以随时响应进入其它a p m 状态的请求。 s t a n d b y 状态：p c 停止处理数据，所有设备的运行状态都保存在内存中，大 部分设备被关闭或者运行速度降低，仅仅以极低的功耗维持并检测外部事件 s u s p e n d 状态：这个状态下系统处于最大节电模式一系统中的大部分支持 a p m 标准的设备都会被关闭，处理器处于最低功耗状态。在这个状态下的计算机 无法做任何事情，直到它转换到更高一级的状态 o f f 状态：这个状态下系统的供电被完全关闭。执行关机操作之后就是进入 这个状态。 1 2 3 z a c p i a c p i 是在a p m 基础上发展出来的，a c p i 就是a d v a n c e dc o n f i g u r a t i o na n d p o w e ri n t e r f a c e 的缩写，意思是“高级配置与电源接口”。 a c p i 可实现以下功能： ( 1 ) 用户可以使外设在指定时间开关； ( 2 ) 使用笔记本电脑的用户可以指定计算机在低电压的情况下进入低功耗状 浙江大学硕七学位论文第1 章绪论 态，以保证重要的应用程序运行； ( 3 ) 操作系统可以根据外设和主板的具体需求为它分配能源； ( 4 ) f 1 0 插即用设备在插入时能够由a c p i 来控制。 ( 5 ) 操作系统可以在应用程序对时问要求不高的情况下降低时钟频率； a c p i 共有六种状态，分别是s 0 到s 5 ，它们代表的含义分别是： s o ：实际上这就是我们平常的工作状态，所有设备全开。 s 1 ；这时除了通过c p u 时钟控制器将c p u 关闭之外，其他的部件仍然正常 工作。微处理器中的所有的寄存器和缓存、内存中的所有数据都保留着。 s 2 ：这时c p u 处于停止运作状态，总线时钟也被关闭，但其余的设备仍然 运转。 s 3 ：所有设备的工作状态都保存在内存中，这个时候除了内存还在工作其余 的配件基本上都处于睡眠状态。当系统唤醒后内存中存储的所有状态都会恢复。 s 4 ：这时系统主电源关闭，但是硬盘仍然带电并可以被唤醒。 s 5 ：连电源在内的所有设备全部关闭。 1 2 4 电源管理发展趋势 电源管理的发展趋势主要表现在以下几个方面： 低功耗：随着能源的紧张以及社会对环保问题的日益重视，功耗问题同益成 为关注热点由于市场对低电压、低噪声的电源管理芯片的需求不断增加，因此 对于工作电压要求越来越低，而工作频率也有越来越高的要求f ，l 。 高效：效率对于便携式电源管理显得非常重要。由于便携式应用大多是由电 尥驱动，高效率、低损耗的电源转换与管理就显得非常的重要。 智能化：利用软件的方法来对耗电部件的用电状态进行控制，对暂不工作的 部件减少或者停止供电，这是一种比较行之有效的方法。比如程序检测到用户超 过一定时间未用键盘或鼠标，则会自动关掉显示屏背景【3 1 。 1 3 课题研究背景 随着嵌入式系统应用的日益广泛，功耗已成为嵌入式系统的最重要的制约因 索z 一。日常生活中，人们在享受现代嵌入式计算等技术带来方便的同时，但又 不得不忍耐频繁更换电池的不便，同时，由于人们对环保意识的日益增强，废电 池；环境带来了很大危害，因此消费者便对低功耗产品有了更加强烈的要求 研究嵌入式系统的功耗，减低系统能耗，延长使用时间，不仅具有重要的“绿 4 浙江大学硕士学位论文 第l 章绪论 色”意义，更具有现实的经济价值。为减低其能耗，延长其使用时间，从软件角 度，各种动态电源管理技术被提出从硬件角度，各厂家在进行系统设计时，也 开始将电源管理考虑在内，从硬件角度支持电源管理，更便于软件进行电源管理。 1 4 本文结构 第一章概述嵌入式系统的概念和特点，嵌入式系统的发展历程，然后论述了 嵌入式系统当中的电源管理技术的必要性，当前市场上的主流的低功耗处理器技 术。介绍了a p m ，a c p i 等电源管理规范。最后探讨了电源管理的未来的发展趋 势以及面临的挑战。 第二章分析了动态电源管理技术( d p m ) 的主要原理，分析了三种d p m 策 略：t i m e - o u t 策略、预测策略和随机策略，并分析了他们的优缺点及其改进方法。 第三章研究了动态电压调节技术，分别研究了非实时任务的d v s 调度算法， 和实时d v s 调度算法。分类讨论了基于时日j 蚓隔的d v s 调度和基于任务分析的 d v s 调度。 第四章针对具有多种运行状态的可调节微处理器并且任务之间有网状优先 级的系统建立了精确的数学模型，提出了带约束性最短截至期限优先且可回溯算 法( r b e d f 算法) 来对任务集排序，再通过对任务集进行子集划分，把子集抽 象成背包问题来确定任务的工作电压，降低了模型求解难度。最后通过实验结果 验证算法。 第五章对论文做了总结，以及下一步的研究工作的展望。 5 浙江大学硕士学位论文 第2 章动态电源管理 第2 章动态电源管理 2 1 基本原理 动态电源管理( d p m ) 是一种电源管理机制，它允许在系统运行时动态的管理 电源。在系统的整个运行过程当中，系统的各个部件如硬盘，网卡，内存等并不 是时刻处于运行状态，我们可以将部分的暂时不用的设备切换到睡眠模式，或者 切断其电源，以此来降低能耗。 一般来说，系统的负载是空闲时间和工作时间相交替的，如图2 1 所示： 图2 - 1 系统负载情况简图 而系统的能耗是不变的。如图2 - 2 所示： 【d 耀 口口 时间t 图2 - 2 没有进行动态电源管理是的能耗图 由于设备有几个的工作状态，不同的状态能耗也不同，图2 - 3 是s t r o n g a r m 6 浙江大学硕士学位论文 第2 章动态电源管理 s k 11 0 0 的能量转换图。 p = 4 0 0 m w w a i tf o ri n t e r u p tw a i tf o rw a k e u p 0 v 0 n t 1 6 m w 图2 - 3s t r o n g a r ms a - 1 1 0 0 的不同工作模式能量转换图 图中很明显可以看出，设备在不同的工作状态有不同的能耗，在工作状态和 阡眠状态的能耗差距很大。如果不管c p u 是否忙碌的话，都使c p u 设景在睡眠 状态的话，很显然这是一种能量的浪费。当各个系统设备当接到请求时，设备处 于工作状态；而没有请求时，就进入了空闲状态当设备进入空闲时，我们可以 关闭设备，进入低耗能的休眠状态；而当设备再次接到请求后，设备被唤起。这 就是所谓的电源管理的原理。 2 2 主要算法 目前已经有很多的d p m 策略【珊1 被提出，主要有以下几种；通常采用的系 统级动态电源管理策略分为3 类：( 1 ) t n n e - o u t 策略：( 2 ) 预测式的策略；( 3 ) 随机模 型的策略。 7 浙江大学硕上学位论文 第2 章动态电源管理 2 2 1t i m e o u t 策略 超时策略( t u n e - o u t ) 是一种原理最为简单，但同时也是应用最为广泛的技术 t u n e - o u t 可分为两种情况：具有固定超时时限的策略( f i x e dt i m e - o u t 和自适应超 时策略( a d a p t i v et i m e - o u 0 ：前者在设备经过一段固定的空闲时间段后会关闭相 应设备，而后者会根据设备的历史记录来动态调整超时时限值。 t i m e o u t 算法当中关键的是确定的t i m e o u t 值，t i m e o u t 必须起码大于某特 定的i d l e 区间的长度，i d l e 区间根据不同的设备特性而不同。简而言之就是其电 能状态切换所能节约的电能能够补偿电能状态切换所耗费的额外电能。图2 - 4 显 示了采用d p m 策略时的系统能耗图。 请求 li 请求 l 。 x 轴 r 忙空闲 i 忙 l li、 x 轴 7 请求 休眠工作i 关闭时延 请求时延 u 【 图2 4 采用d p m 策略时的系统能耗图 从图中我们可以看出，系统在工作休眠状态进行切换的时候，系统会有一定 8 浙江大学硕士学位论文第2 章动态电源管理 额外能量的损耗。因此，只有当系统进入休眠状态后节省的能量大于由于在不同 状态转换所损耗的能量时，我们的电源管理策略才是有效的。 为了能准确的反应系统采用d p m 策略时的最小空闲时间段的大小，我们用 公式来表示： e p ( 2 1 ) z k 表示最小的t i m e o u t 值，e s 表示状态切换所耗费的电能，p 表示在i d l e 状态的功率。等式的含义表示为只有当设备的空闲时间超过瓦。，时，系统的切换 才能够达到降低能耗的目的。对于t u n e - o u t 策略的算法的思路为：当i d l e 时段 到来后，启动计时器，如果新任务在，o 时间之前到来，则不进行电能状态切换； 否则如果系统经过t 时间后还处在i d l e 状态，则进行电能状态切换将其置于节能 模式，直到新的任务到达，再将其电能状态切换成原来的状态来处理任务。算法 的实现是比较简单的。 实验证明t i m e o u t 值的大小直接决定了算法的节能效果。当t i m e o u t 值过小 时，系统频繁的在睡眠运行模式下切换，而任务艺。之i j i 到达，那么系统不仅没 能降低能耗反而增加了能耗，而如果t i m e o u t 过大，前面等待的空闲时问便浪费 了能量。 超时策略都有一个假设条件 如果系统处于空闲状态的时间已经超过了 t i m e o u t 值，则系统在剩余空闲时间内进入低功耗模式所节省的能量能够抵消模 式转换所带来的额外消耗；就是系统至少还可以继续保持艺。的空闲时间，从而 在进入和退出睡眠状态不会带来能量浪费。这个假设条件是不能完全成立的，因 为对于未来的情况我们不能完全根据前面的情况来预测，而且各个系统的任务到 达的性质存在着一定的差别。所以这种固定的超时策略有一定的效果，但却并不 是最理想的。 针对固定超时策略存在的缺点，即对系统的运行状况没有区别对待，所以专 家们提出了自适应的超时策略，即自适应的动态调整算法。d o u g l i s t 7 1 等提出了一 种自适应算法，根据前一次切换的结果的好坏按比例动态的调整时限值大小这 样的算法有一个有点，就是改变t i m e o u t 值就能改变性能。然而其也有相应的缺 点：在进入i d l e 区间开始计时直到t i m e o u t 到达时，还是有大量的能量消耗，而 且在进行电能状态切换时有延迟导致性能损失。因此一些对t i m e o u t 算法进行改 进的算法被提出。比如预关断算法，即通过对系统过去i d l e 区间的观察，如果i d l e 区间大小满足某种要求，便在i d l e 区间的开始就进行电能状态切换，来减少在 9 浙江大学硕上学位论文 第2 章动态电源管理 t n n e o u t 等待过程中浪费的电能。 2 2 2 预测策略 预测策略一般都是基于以前的系统负载情况记录来预测将来的状态，并根据 预测值来控制目标设备的工作模式i ”。一旦预测到设备进入空闲状态的时问能够 弥补工作模式转换所带来的额外消耗时就立即将设备转换到睡眠模式甚至关闭 电源。因此，其与t i m e - o u t 策略相比，有个非常明显的优点：其不需要等待t i m e o u t 便立即进行模式的切换节省了在等待过程中浪费的能耗。 为了分析过去的负载情况，必须要保存过去的数据，而如果将过去的全部数 据都进行保存，这就会浪费磁盘空间，并且也是没有必要的，同时达到的效果与 付出的代价相比也是不合算的。 为此，很多专家提出了高效而可行的预测算法。s r i v a s t a v a 9 1 等提出两种预 测算法，一种算法的思想是基于特殊的系统负载情况：硬盘相邻服务和空闲的时 问长度具有“l 形”特征，即比较长的服务时问之后出现的空闲时间长度较短，而 在比较短服务时间之后出现的空闲时问比较长，算法检测到服务时间小于某个特 定时限值时，则在下一空闲时间开始实施切换设备的工作状态，该算法仅仅适用 于具有“l 形特征的应用，并且服务时间时限值的确定非常关键。另一种则是采 用非线性递归模型，根据历史服务情况的记录和空闲的时间长度来预测将来的空 闲时间长度。h w a n g t ”1 等提出了通过一个回归方程来预测i d l e 空闲时间的大小。 等式如下： 2 “( 行) 2 a 2 ( 嚣一1 ) h 1 - a ) 7 。( 开一1 ) ( 2 2 ) 7 k ( n - i ) 是上一次的实际空闲时间，而7 伽1 ) 是上次的预测时间，如果 预测时间比较符合时间时间，则减少a 的值，即增加z ：。( 一1 ) 的权重。如果预测 的时间和时间的差距大，则增加a 值，即提高z k ( 刀一1 ) 。通过这样的方法来动态 的调整7 k ( n - 1 ) ，z 乙( n - d 权重x d 、来预测值。 预测可能出现3 种结果：1 ) 刚好等于实际时间；2 ) 预测不足；3 ) 过度预 测。过度预测就是预测的i d l e 区间长度大于实际值，在任务到达时，相关设备还 没有启动，这样就会使系统的响应不及时，损害系统性能。而预铡不足使得预测 的i d l e 区间小于实际值，这样在任务还没有到达的时候便将切换设备的工作模式， 使得设备提前进入正常工作模式，便会造成电能浪费。 显而易见，一般算法在预测过程当中会出现预测不足的现象，为了防止出现 i o 浙江大学硕士学位论文第2 章动态电源管理 这种情况，h w a n g 在t i m e - o r e 算法的基础上，提出了一个方法，如果系统仍然处 于i d l e 状态并且还没有关断的是情况下，则重新周期性的预测7 二。( ) ，以此来预 防出现预测不足的情况。 预测算法通过预测来确定接下来的i d l e 值的大小，在i d l e 达到之前采取行动， 这样很好的消除了系统负载的不确定性，但是由于预测算法是启发性的，预测算 法不能完全真实的反应系统未来的负载情况，所以算法的优劣只能通过系统仿真 来评判，同时，考虑到算法的复杂程度，如果引入的参数过多的话，将影响算法 的实用性。 除此之外。还有很多专家提出了许多具有独特思维的算法。例如c h u n g ”1 等 提出了采用自学习树模型描述相邻空闲时间长度之间的规律，根据此模型对空闲 时间长度进行预测，该算法的实际效果取决于系统的负载的特性是否具有比较明 显的规律。g n i a d y ( ”】等提出了利用访闯计数器跟踪应用的请求特性，采用基于路 径的预测方法，估计空闲时问长度的大小，然后再决定是否重新设黄设备的工作 模式。文献【1 3 】【1 4 】【1 5 】【1 6 】【1 7 】也提出了其他一些预测算法。 纵观大多数的算法，如果空闲时间长度具有比较明显的规律性，则算法可以 预测保证较高的准确性，但在实际系统当中，系统负载一般很少具有这种规律性， 而错误预测则带来较大的功耗和响应性能损失，所以不能保证实际效果。 。 2 2 3 随机策略 随机策略将系统负载看成一个随机优化问题，再利用随机决策模型求解d p m 控制算法。 算法一般利用受控的m a r k o v 过程来进行求解。其将系统负载和用户请求抽 象为离散时间m a r k o v 决策过程模型，使得动态电源管理最优化闯题在多项式时 间内有解，而且提供了灵活的方法来处理降低能耗与性能损失的权衡问题。 相应的m a r k o v 模型一般包括如下几个部分： 服务请求：m a r k o v 链的状态集，用来模拟系统任务到来的各个时刻。 服务提供者：模拟系统的各个能耗状态，状态之间的切换由动态电源管理器 来控制。 代价矩阵：用来表示各种行为的代价。 电源管理器：电源管理器通过观察系统与任务的状态，然后作出判断，发出 命令来控制系统的能耗状态的设置。 随机决策一般主要有以下几种模型： 浙江大学硕士学位论文第2 章动态电源管理 排队模型：排队模型将p m c ( 功耗可管理部件) 提供服务抽象为一个排队系 统。服务请求者向服务提供者提出服务请求，服务提供者则向系统提供服务。功 耗管理器控制服务提供者的功耗模式( 如图2 5 所示) 。假设服务请求的间隔时 间是相互独立，并且服从负指数分布，等待队列为先来先服务队列。服务提供者 从队列中提取出服务申请者的服务请求，按照电源管理器发出的命令，并且按照 先到先服务原则为其提供服务。排队模型将排队系统映射成离散的或连续的马尔 可夫链，再通过马尔可夫模型进行求解。 攀 ” 一 “ 1 9 f “一 “。 ； 一 k! 功耗管理器 f 一。”4 。“ 氇 # 矿 飞豳蕊蕊臻褒溺鳓 ，j 簋x + 0 “ 毽 ? 一j ；。 歹 ：g 囊 w “ 飞 z 懋 帮、 、 ” j? j 服务请求者 冷i 吻i专 ，服务提供者 氟 鼍，臻瀚翟藏搿黝 g g 镕蕊黝 图2 - 5 捧队模型 传统的排队论模型是假设系统负载满足指数分布，但是研究表明指数分布的 假设不适用于d p m 策略的研究。原因是计算机系统负载具有自相似性。因此吴 琦【i 硼等根据负载的自相似特性提出了当空闲时间长度服从p a r c t o 分布时，基于截 尾均值法小样本情况下p a r e t o 分布形状参数的稳健有效估计算法和基于窗口大 小自适应技术非平稳业务请求下的d p m 控制算法。 基于m a r k o v 模型的随机控制算法相比较于预测算法有以下两个突出优点： ( 1 ) m a r k o v 模型的随机控制算法从全局出发求得最优解。 ( 2 ) 它使得最优动态电源管理策略在多项式时间内得到准确解。 除此之外，文献d 9 2 0 2 1 还提出了其他一些很有价值的基于随机策略的算 1 2 浙江大学硕士学位论文第2 章动态电源管理 法。 2 3 本章小结 t i m e - o u t 策略是最简单的动态电源管理策略。算法简单，便于实现，但是其 缺是不管空闲时间长短，都得等待一段时间才进入睡眠模式，造成了一定得功耗 浪费。如果能尽量减少等待时间，将会取得比较好得效果 预测策略得缺点是需要假定相邻空闲时间长度具有明显得规律性，并且它较 难控制响应延迟，不适用于具有相应性能约束的应用。如何采用新的数学模型提 高预测的准确性将是研究的重点。 随机策略的缺点是模型需假设服务请求满足某种已知的分布，因此限制了其 在不同服务特征系统的应用。准确研究不同系统的服务特征将会提高随机策略的 应用范围。 1 3 浙江大学硕上学位论文第3 章动态电压调节技术 第3 章动态电压调节技术 3 1 基本原理 d v s ( 动态电压调节) 技术是在任务运行行动态的改变处理器的频率和电压， 以此来降低能量消耗。它主要是利用的c o m s 电路的这样一个特性：由于c m o s 电路的功耗正比于电压的平方和时钟频率的积，对于某个特定的任务来说，完成 它所需要的时钟周期是固定的，因此消耗的能量和电压的平方成正比。通过降低 电压便能降低能耗在降低时钟频率时，完成特定任务的所需的时间也必然会增 加，这必然会影响系统的性能。d v s 技术以延长时间为代价来达到减少能量消耗， 体现了能耗和性能的平衡。因为用户对系统性能的要求时不同的，并不是所有的 任务有都需要最大的性能。 具体来说，c m o s 电路的功耗可以分为静态功耗和动态功耗： p = g k z + k ，口 ( 3 1 ) g 为有效电容，巧为电压，z 为频率k 乇为静态能耗。一般来说，静态功 耗与动态功耗相比是可以忽略不计的。因此c m o s 电路的可以表示为如下； p = c y , 2 z ( 3 2 ) 频率和电压之间有这样的关系： z = x 巧 ( 3 3 ) 因此执行任务i 所需消耗的能量为： e = c y , 2 川 ( 3 4 ) 表示i 个任务的周期数。 因此通过降低任务执行时的电压，便可以降低能量消耗。 嵌入式系统中任务按实时性不同大致分为实时和非实时任务两类：在多媒 体、网络服务等应用中，任务没有确定的截止时间限制，任务执行的延迟只是影 响系统响应性能，这类任务称之为非实时任务。而实时任务都具有严格的截至时 间限制，必须确保任务在其截止时间之前完成，否则会对任务甚至整个系统造成 很大危害。 由于这实时和非实时任务有着不同的特性，因此处理的方法也不同，对于非 1 4 浙江大学硕士学位论文第3 章动态电压调节技术 实时任务来说，一般是在系统功耗与响应速度，q o s 等其他性能之阃作个平衡。 而对于实时任务来说，d v s 调度算法首先必须保证任务在截止时间完成，其实考 虑功耗的最小化。 3 2 非实时d v s 任务调度 3 2 1 基本概念 计算机系统中的非实时任务是指那些没有明确的截止时间限制或不需严格 保证任其截止时间的任务，这类任务一般分为两类： 交互式任务：这类任务主要负责与用户或外界环境进行交互，主要由用户或 外部事件来触发。当输入事件被系统接受时，系统必须在一定时间内唤醒任务， 否则将影响用户体验。比较典型的交互式任务是s h e l l 命令、文本编辑、网络数据 传输等任务。 批处理任务：这类任务不必与用户交互，而是在后台运行，也不必被系统快 速响应。典型的批处理任务是程序设计语言的编译程序、数据库备份及科学计算 任务。 对于非实时任务，系统常采用的调度算法有以下几类： 先到先服务调度：系统将就绪任务按照先到先服务的原则进行调度，每次调 度的任务都是在时间上是最早达到的就绪任务，直到该任务执行结束或阻塞 时间片轮转调度：系统将就绪任务按照先到先服务原则排成一个队列，每次 调度时将处理器分配给队首任务，让其执行一个时间片。如果该任务在时间片结 束前就执行完的话，那么把处理器分配给下一个任务。如果时间片结束时，任务 还没有执行完的话，就暂停当前任务执行，将其放置就绪队列的末尾，进行下一 次调度。 可抢占优先级调度：系统中按照优先级设置多个等待队列，就绪任务被放置 在对应优先级等待队列中，并且按先到先服务原则排队，每次调度时将处理器分 配给最高优先级任务。当新任务产生时，如高于当前任务则抢占执行，否则进入 对应优先级的等待队列。 3 2 2 调度算法 3 2 2 1 基于时间间隔的d v s 算法 目前，按照任务执行需求分析方法不同，非实时d v s 调度算法大致可分为 1 5 浙江大学硕上学位论文第3 章动态电压调节技术 两类，一类是基于时间间隔的算法，这类算法将处理器运行时间划分为长度相等 的阃隔，依据系统执行负荷的历史记录估计下一时段系统的负荷，再确定下一时 间段处理器时钟频率。 比较经典的基于问隔的动态电压缩放算法主要：f l a t ，p a s t ，p e a k ，a v g n 。 下面分别介绍下。 f a l t 算法：f a i t 算法分为预测部分和时钟速度设置部分。预测部分是预测 新的运行百分比为一个常数，这个常数在( o ，1 ) 之间。时钟速度设置部分是设 置一个尽可能快的速度来完成预测的新工作以及上一个区间多出的周期。这个速 度为全速所控制( 即只能小于等于全速) 。f l a t 算法的目的只是使运行百分比 尽可能保持不变。 p a s t 算法：它是由w e i s e r 等【丝1 最早提出非实时d v s 调度算法。假定在c p u 具有动态频率和电压调节能力下，如何提高系统能量效率的方法。主要采用了移 动平均方法估计下一时段的执行需求。它假设即将到来的日j 隔与静一个间隔是一 样地忙，p a s t 算法首先计算上一个完成的日j 隔有繁忙程度，再计算运行周期的 百分比，并预测下一周期的多余周期。然后根据计算得到的上一间隔的运行周期 百分比设置下一个间隔的速度。 p e a k 算法：p e a k 算法预测当前的负载将伴随一个“窄峰值”。即预测到 一个上升的运行百分比必将对称地下降，而下降的运行百分比将继续保持下降。 p e a k 设置速度的时将速度设置得尽可能快，使预期的工作量能尽快地完成。 a v g n 算法：a v g n 由g o v i l 等2 卅提出，他们在w e i s e r 等人的基础上分析了 彰种简单或复杂的估计算法和平滑技术。a v c , n 的基本思想是指采用指数平滑平 均值方法是预测即将到来的间隔的n 个运行百分比的加权平均值。 f l a t ： i p e a k 算法虽然性能较好，但f l a t 算法的预测部分太过于简单。而 p e a k 算法则更适用于突发情况比较到的系统当中p a s t 也有缺点，它仅考虑前 一个间隔来进行预测。并且，它考虑了上一个间隔的多余周期，而忽略了将要延 续到下一个间隔的多余周期。a v c m 算法的预测部分比较好，因为它考虑了下一 间隔之前的n 个间隔。 除此之外，文献【2 4 】 2 5 】提出了其他一些基于时间间隔的算法。 3 2 2 2 基于任务分析的d v s 算法 另一类是基于任务分析的算法，这类算法通过分析每个任务的计算需求估计 将来的执行负荷。h o n g 等嗍提出了一种针对间发任务的电压缩放算法。算法思 想是当一个间发任务到达时，首先运行一个测试程序，检查该任务是否能在其时 1 6 浙江大学硕士学位论文第3 章动态电压调节技术 限达到前完成，并且不影响其它已被接受的任务的运行，如可以完成，则接受， 如不能完成，则不接受。被系统接受的任务将在任务队列中排队等待被调度执行。 f l a u t n e r 等【2 7 1 将任务分为交互任务和周期任务，交互任务通过“生产者与消费者” 关系预测将来的计算需求，周期任务通过估计任务近似周期预测将来的计算需 求。m a n z a k 等心”提出了一种针对非周期任务的动态电压算法。p o u w e l s e 等r 9 1 提 出应用在开发时提供计算需求说明，运行时操作系统根据这些信息进行任务计算 需求估计。这类算法对响应性能控制可以按照不同任务的不同要求而采用不同的 处理方法。其关键是对任务规律的分析，当任务计算需求具有明显的不确定特性 时，这类算法的使用受到限制。 3 3 实时d v s 任务调度 3 3 1 基本概念 在实时系统中，任务具有严格的截至时间要求，特别是安全关键系统，即使 在最坏的情况下都必须保证任务在指定时间内完成，一旦任务超过截止时间，可 能会带来灾