（计算机应用技术专业论文）基于spm的寄存器抛出能耗优化研究.pdf

摘要 随着集成电路设计技术与制造工艺的不断提升，以片上系统为核 心的嵌入式系统的处理能力出现了飞跃式的发展，与此同时，能耗问 题成为制约嵌入式系统发展的重要瓶颈之一。研究表明，存储子系统 是片上系统的主要能耗来源，如何有效降低存储子系统能耗成为降低 整个片上系统能耗的关键，包含有片上存储器s p m 的存储子系统层 次体系结构的出现成为降低存储系统能耗的有效手段。 本文以s p m 对存储子系统的能耗影响为核心，着重研究基于 s p m 的寄存器分配算法抛出管理策略，以及基于s p m 布局的存储子 系统能耗优化。 针对图着色寄存器分配过程中，无寄存器可用时将待分配变量抛 出到片外存储器的情况，本文提出一种基于s p m 的寄存器分配算法 抛出策略。通过分析应用程序编译阶段生成的静态单向赋值图，在抛 出变量的前后插入s p m 存取指令( s t s l f s ) ，将针对片外存储器的抛 出，修改为针对s p m 的抛出，s p m 存取指令在s p m 管理器s p m m 的协助下完成抛出变量在s p m 存取。通过将抛出变量置于s p m 空间 来降低存储器访问能耗。 鉴于抛出变量在s p m 中管理对存储子系统能耗影响的局部性和 有限性，本文提出一种基于s p m 布局优化的存储子系统能耗优化策 略。通过综合考虑应用程序的全局变量、数据、代码、堆栈对系统能 耗的影响，构架反映程序调用关系和访问次数的权重扩展控制流图， 采用以节点能耗密度为优先权的o 1 背包算法，选择程序中的能耗热 点。将s p m 空间进行分层管理，第一层用于抛出变量管理，第二层 用于存储程序能耗热点。通过对s p m 空间的合理划分和能耗热点的 优化布局，有效降低存储子系统的能量消耗。 实验结果表明，上述抛出变量管理策略和s p m 空间布局策略， 分别取得约4 2 4 和3 4 8 的能耗优化结果。 关键词嵌入式系统，片上存储器，图着色寄存器分配，能耗优化 a bs t r a c t w i t ht h et e c h n o l o g yo fi n t e g r a t e dc i r c u i td e s i g na n dm a n u f a c t u r i n g p r o c e s s e sc o n t i n u o u s l yi m p r o v i n g ，al e a p t y p ed e v e l o p m e n th a sb e e n m a d ei nt h ep e r f o r m a n c eo fe m b e d d e ds y s t e m sw i t hs y s t e m o n - c h i pa s t h ec o r e a tt h es a m et i m e ，h o w e v e r , e n e r g yc o n s u m p t i o nb e c o m e sa n i m p o r t a n t b o t t l e n e c ki nt h e d e v e l o p m e n t o fe m b e d d e d s y s t e m s a c c o r d i n gt o f o r m e rr e s e a r c h e s ，s t o r a g e s u b s y s t e mi sm a i ne n e r g y s o u r c e so f s y s t e m - o n - c h i p ，h o w t o e f f e c t i v e l y r e d u c et h e e n e r g y c o n s u m p t i o no fs t o r a g es u b s y s t e mh a sb e c o m et h ek e yt od e c r e a s i n gt h e w h o l es y s t e m - o n - c h i pe n e r g y a n dt h eh i e r a r c h i c a la r c h i t e c t u r eo fs t o r a g e s u b s y s t e mw i t ht h es p m h a se m e r g e da st h ee f f e c t i v em e a n so fr e d u c i n g e n e r g yc o n s u m p t i o n w i t ht h ee f f e c to nt h es t o r a g es u b s y s t e m se n e r g yc o n s u m p t i o n b a s e do ns p ma st h ec o r e ，as p m b a s e dr e g i s t e ra l l o c a t i o na l g o r i t h ms p i l l m a n a g e m e n ts t r a t e g ya n das p m - b a s e d - - l a y o u ts t o r a g es u b s y s t e me n e r g y o p t i m i z a t i o ns t r a t e g ya r ei n t r o d u c e di nt h i st h e s i s d i f f e r e n tf r o mv a r i a b l e st ob es p i l l e do no f f - c h i pm e m o r y , w h e nn o r e g i s t e rw i l lb ea v a i l a b l ei ng r a p hc o l o r i n gr e g i s t e ra l l o c a t i o np r o c e s s ，a s p m b a s e dr e g i s t e ra l l o c a t i o na l g o r i t h ms p i l lm a n a g e m e n ts t r a t e g yi s i n t r o d u c e di nt h i st h e s i s b ya n a l y z i n gt h es t a t i cs i n g l ea s s i g n m e n t ( s s a ) f o r mg e n e r a t e di nt h ep h a s eo fa p p l i c a t i o nc o m p i l e r , b e f o r ea n da f t e r s p i l l e dv a r i a b l e ss p ma c c e s si n s t r u c t i o n s ( s t s l f s ) a r ei n s e r t e d ，s p m i n s t e a do fo f f - c h i pm e m o r yb e c o m et h et a r g e ts p i l ls p a c e ，s p ma c c e s s i n s t r u c t i o n sa s s i s t e db ys p mm a n a g e r ，s p mm a n a g e rm a k es p i l l e d v a r i a b l e ss t o r e do rl o a d e df r o ms p ms p a c e i tr e d u c e s e n e r g y c o n s u m p t i o no f a c c e s sb yp l a c i n gs p i l l e dv a r i a b l e si ns p ms p a c e g i v e nt h el i m i t a t i o na n dl o c a l i z a t i o no ft h es t o r a g e s u b s y s t e m e n e r g yc o n s u m p t i o nb yt h em a n a g e m e n to fs p i l l e dv a r i a b l e si nt h es p m ， as t o r a g es u b s y s t e me n e r g yo p t i m i z a t i o ns t r a t e g yb a s e do ns p ml a y o u t o p t i m i z a t i o ni sp r e s e n t e di n t h i sp a p e r g e n e r a l l yc o n s i d e r i n gt h ee n e r g y c o n s u m p t i o no fa p p l i c a t i o np r o g r a mg l o b a lv a r i a b l e s ，d a t a ，c o d e ，s t a c ko n t h es y s t e m ，i tw i l lc o n s t r u c tw e i g h te x t e n d e dc o n t r o lf l o wg r a p h ( w e c f g ) r e f l e c t i n gt h er e l a t i o n s h i po fp r o c e d u r ec a l l sa n dt h en u m b e ro fv i s i t s ， c a l c u l a t et h en o d ee n e r g yd e n s i t yi nt h ew e c f g , a n du s i n go 一1k n a p s a c k a l g o r i t h mw i t he n e r g yd e n s i t ya sp r i o r i t yt o s e l e c te n e r g yc o n s u m p t i o n h o ts p o t si np r o g r a m t h i st h e s i sd i v i d e ss p ms p a c ei n t ot w ol a y e r s ：t h e f i r s tl a y e rf o rs p i l l e dv a r i a b l e ss t o r a g e ，t h es e c o n df o rs t o r a g eo fh o t e n e r g yc o n s u m p t i o n i ta i m sa tr e d u c i n gt h ee n e r g yc o n s u m p t i o n o f s t o r a g es u b s y s t e mt h r o u g ht h er a t i o n a ll a y o u to fa p p l i c a t i o np r o g r a mi n t h es p m s p a c e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea b o v e - m e n t i o n e ds t r a t e g y , v a r i a b l e s s p i l l e dm a n a g e m e n t i ns p ma n ds p m s p a t i a ll a y o u t o p t i m i z a t i o n ，a c h i e v e d a b o u t4 2 4 a n d3 4 8 e n e r g yc o n s u m p t i o n o p t i m i z a t i o ni ne m b e d d e ds y s t e m sr e s p e c t i v e l y k e yw o r d se m b e d d e ds y s t e m s ，s c r a t c h p a dm e m o r y , g r a p hc o l o r i n g r e g i s t e ra l l o c a t i o n ，e n e r g yo p t i m i z a t i o n i i ! 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： z 垒丝日期：丑年上月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：趔导师签名垌睦型3 日期： 年 月旦日 1 1 研究背景 第一章绪论弟一早珀丫匕 近年以来，得益于集成电路设计技术与制造工艺的不断提升，以片上系统 ( s y s t e mo nc h i p ，s o c ) 为核心的嵌入式系统得到快速发展，随着芯片处理能 力的不断提升，芯片的能耗问题同益突出，目前能耗因素已经成为制约嵌入式系 统发展的主要瓶颈之一。 嵌入式系统是指以应用为中心，以计算机技术为基础，软硬件可剪裁，对功 能、可靠性、成本、体积和能耗严格要求的专用计算机系统。随着集成电路设计 技术、半导体产业制造技术、以及计算机应用技术的不断进步，嵌入式系统以每 年2 0 左右的速度快速增长，广泛应用在工业、军事、通讯、运输、金融、医疗、 气象、航天、农业等人类生活的方方面面。除了应用场合日益广泛，嵌入式系统 在发展过程中也出现了一些新特征，最显著的特征是嵌入式处理器以及整个s o c 的电路集成度不断提高、体积不断减小、处理能力和速度不断增强，同时嵌入式 系统的能耗也在高速增长，能耗增长导致以下两个方面的主要问题。 一方面，单位体积的电池容量每年1 0 的增长速度明显滞后于嵌入式系统对 能耗的增长需求，同时移动系统考虑到移动性、便携性等因素，系统尺寸受限， 因此对于由电池提供能量的嵌入式系统而言，工作时间受到严重限制；另一方面， 由于嵌入式系统芯片体积小，特别是移动式和便携式设备，能耗增大使其散热困 难，容易形成高温，从而加速了硅电路失效机理，研究表明，工作温度每提高 1 0 度，系统的失效率将提高l 倍【l 】。因此，如何降低能耗成为当前优化嵌入式 系统的研究热点。 为应对嵌入式系统的能耗问题，出现了大量的嵌入式低功耗技术，嵌入式低 功耗技术主要是指利用特殊设计技术、制造工艺、功能部件、以及管理算法等来 降低嵌入式设备的功耗。过去的一个研究重点是如何有效降低处理器的能耗，而 当前大量研究表明，存储子系统是整个片上系统中能量消耗的主要部件【2 】【3 1 ，其 能耗比例可占到整个存储系统的2 5 至5 0 ，因此降低存储子系统的能耗成为 有效降低整个系统能耗的关键。在存储子系统中，研刭4 l 【5 】显示能耗主要来源于 处理器对片外存储器的访问过程。为解决这一问题，现在嵌入式系统中开始考虑 采用层次性的存储子系统结构，通过内置片上存储器，让片上存储器缓存片外存 储器的数据等各种手段，力图减少处理器访问片外存储器的次数，进而减少存储 子系统的整体能耗。 目前常用的片上存储器有：s c r a t c hp a dm e m o r y l 6 】( s p m ，高速暂存存储器 或者片上s r a m ) 和c a c h e 。s p m 是针对c a c h e 的高能耗和不可预测性( 程序执 行过程中，变量在c a c h e 的命中与否很难确定) 而新设计的片上存储器结构，相 对于硬件管理的c a c h e 来说，s p m 具有体积小、访问快速、功耗低、有实时性 保证以及与片外内存统一编址等特点。与c a c h e 不同的是，对s p m 的管理必须 在编译器或者特定管理部件的协助下完成。实验表明，相同的应用的场合，采用 s p m 的系统比采用c a c h e 的系统可节省功耗4 0 左右，同时系统的执行时间还 可缩短1 0 【_ 7 1 。因此，基于s p m 部件的低功耗优化管理研究，对于延长电池供 电式嵌入式设备的工作时间并提高系统性能具有重要的意义。 本文基于带有片上存储器s p m 嵌入式存储子系统结构，提出一种全局寄存 器分配算法抛出阶段的优化策略，以及相应的s p m 空间管理策略，改进嵌入式 系统应用程序执行时的性能和能耗特性；同时针对上述策略对存储子系统整体能 耗优化的有限性，提出一种基于权重扩展流图( w e i g h t e de x t e n dc o n t r o lf l o w g r a p h ，w e c f g ) 存储子系统能耗优化策略，以优化存储子系统在程序执行时的 整体能耗。 1 2 国内外研究现状 1 2 1 片上存储器 在嵌入式系统发展过程中，优化存储器子系统，依此来改善整个系统的能耗 和性能成为嵌入式发展的研究重点之一。众所周知，考虑到容量、速度和价格等 方面的因素，嵌入式系统中存储子系统也通常采用层次性存储结构( m e m o r y h i e r a r c h y ) 【8 1 ，而不只是依赖单一的存储部件或技术。以往研究中，针对嵌入式 系统，系统设计师和研究人员提出了许多不同的层次结构，其中包含两种最重要 的片上存储部件，c a c h e 和s p m 。图1 1 给出了片上存储器c a c h e 和s p m 在存 储子系统层次位置。 图1 - 1 存储子系统分层结构 2 高 低 从图l 一1 可以看出，c a c h e 和s p m 是仅次于寄存器的高速存储部件，如何有 效使用c a c h e 和s p m 是嵌入式系统低功耗技术研究的重点。 c a c h e 称为内部高速缓存，没有独立的地址空间，也是目前桌面系统处理器 广泛采用的硬件结构。当处理器访问的对象在c a c h e 命中时，访问可以立即完成， 减少了外部总线的激活次数和外部存储器的访问操作次数；否则，c a c h e 会将该 对象所在地址附近的一块内容从外部存储器复制到内部高速缓存中，再将所需内 容返回。它对于节约能耗的贡献在于利用程序运行过程中访问的局部性，尽可能 地使处理器访问的内容被提i ； 复制到内部高速缓存中，从而减少片外的访问次 数，进而减少能耗。 s p m 作为一种片上存储器的存在形式，也是现代嵌入式系统中一个非常重 要的系统框架设计考虑因素。s p m 具有自己的独立地址空间，并和外部存储器 共用地址和数据总线，处理器对任何处在s p m 地址空间内的对象访问都会触发 它，且立即完成。利用s p m 进行能耗优化的前提在于通过软件优化的手段或通 过特定辅助部件，将程序部分内容安排在s p m 中，以减少处理器对片外存储器 的访问次数。 c a c h e 和s p m 这两种片上存储部件有着很多不同之处。c a c h e 通过硬件电路 管理缓存中的数据，它可以通过调整诸如容量大小、行大小和关联度等等参数来 改善它的性能【9 】，或者通过软件的数据布局优化来提高c a c h e 的命中率【1 0 】。但 是，s p m 中没有任何辅助管理数据的逻辑电路，所有数据必须被软件显式地搬 入搬出。因此，s p m 也被称为软件管理的c a c h e ( s o f t w a r em a n a g e dc a c h e ) 。而 且，这使得相同容量情况下s p m 的面积和功耗都要小于c a c h e 。由于s p m 不会 自动换入换出数据，所以它不存在访问不命中的情况。s p m 始终能够保证一个 时钟周期的访问时间，而c a c h e 在未命中或冲突等情况下会导致对片外存储器的 访问，这使得c a c h e 很少应用于实时性要求高的嵌入式系统，s p m 更适用于对 内存访问时间稳定性有较高要求的实时系统。 表1 - 1 片上存储器和片外存储器的比较 表1 1 列出了片上存储器和片外存储器的典型参数。可以看出，就单次访问 能耗来说，s p m 不仅远小于片外存储器，也小于c a c h e ，考虑到c a c h e 还可能发 3 亟堂焦i 金室 簋= 童绪论 生不命中，引发额外的片外访问，所以相比之下，s p m 低能耗优势更加明显。 从面积上考虑，相同容量下s p m 也明显小于c a c h e 。但是和c a c h e 采用硬件机 制自动完成片外存储器至c a c h e 的复制和交换不同，s p m 由于没有附加的硬件 电路对数据进行管理，需要通过软件人员通过软件手段进行干预。那么对于空间 有限的s p m 来说，如何确定哪些内容应该置入s p m ，以最大限度的减少能耗， 成为摆在软件人员面前的关键问题。 针对有限的s p m 空间，将应用程序的那些部分置于s p m 空间以得到最好的 能耗优化结果，从存储子系统体系构成的角度来考虑，以往的研究主要分为三种 类型： ( 1 ) s p m 和c a c h e 共存：文献 1 1 1 6 研究s p m 和c a c h e 共存情况下，如 何利用s p m 降低系统能耗。其中文献【1 1 1 3 主要研究利用s p m 作为i c a c h e 的 辅助存储部件，降低i c a c h e 的失效率，优化的对象为程序指令；文献 1 4 1 6 研 究如何利用s p m 减少d c a c h e 冲突，这类研究仅考虑把数变量放入s p m ，并未 考虑指令。 ( 2 ) 无c a c h e 的情况下的s p m ：文献 1 7 ，1 8 针对无c a c h e 时，研究如何利 用程序在内存中的合理布局来减少功耗，这类研究考虑把程序中访问最频繁的部 分放入s p m 来减少对片外存储的访问，优化的对象是成组数据，或者整个程序 中的所有数据，既包括数据变量也包括成组数据。 ( 3 ) 硬件协助的s p m ：文献 1 9 2 5 研究在特殊功能部件协助下，s p m 对存 储子系统能耗的影响。其中文献 1 9 2 1 在无c a c h e 情况下，使用s p mc o n t r o l l e r 控制对s p m 存取访问，将程序指令在s p m 空间进行动态分配，算法没有考虑数 据的影响。文献 2 2 2 5 研究s p m 与c a c h e 共存的情况下，通过改进的内存管理 单元( m e m o r ym a n a g e m e n tu n i t ，m m u ) 完成对s p m 的分段或者分页式管理， 分别针对指令或者数据在s p m 空间存储时对存储子系统的能耗影响给出分析。 以往的研究表明，虽然上述算法可以得到较好的能耗优化结果。但是，这些 研究中对应用程序的划分较为简单，所放入s p m 的要么是程序的数据，要么是 指令或者代码，很少全面分析应用程序执行时各个组成部分的对系统功耗影响。 本文综合考虑应用程序的各部分组成，提出一种基于权重控制流图( w e c f g ) 的s p m 空间管理策略。 1 2 2 全局寄存器分配 寄存器是位于c p u 内部的高速存储器，由于它的数目有限和高速存取的特 性，使得寄存器成为计算机系统中的关键性资源。寄存器分配算法是一个研究最 早，发展最成熟的算法之一。全局寄存器分配处于编译器的后端，在对应用程序 4 进行编译时，编译器总是假设有数目无限的虚拟( 符号) 寄存器可用，寄存器分 配算法的主要任务就是建立一种数目无限的虚拟寄存器到数目有限的物理寄存 器之间的映射关系。全局寄存器分配策略从分配思想的角度可以分为两大类： ( 1 ) 线性扫描寄存器分配策略( l i n e a rs c a nr e g i s t e ra l l o c a t i o n ) ( 2 ) 图着色寄存器分配策略( g r a p hc o l o r i n gr e g i s t e r a l l o c a t i o n ) p o l e t t o 2 6 等人提出的线性扫描寄存器分配策略，将应用程序中的各个变量 按照其出现时的活跃范围进行排序，在对变量活跃范围的一次线性时间扫描里， 完成寄存器分配，活跃期重叠的变量不能分配相同的寄存器，该分配策略的时空 开销较少，但是所生存的代码效率不高。 图着色寄存器分配首先是由c h a i t i n t 2 7 】提出的，他将寄存器分配问题转换成 等价的图着色问题，图着色是一个n p 完全问题，对该问题处理通常采用“启发 式 策略。c h a i t i n 算法首先为应用程序变量分配数目无限的虚拟寄存器，每个 变量拥有一个虚拟寄存器，接着建立一张表示虚拟寄存器变量分配过程中各种资 源限制的干涉图( i n t e r f e r e n c eg r a p h ) ，如图1 2 所示，图中的结点表示生命期， 边表示生命期之间的干涉关系。一般说来，如果两个生命期在函数的某一点是同 时活跃( 1 i v e ) 的，它们就相互冲突，不能占有同一个寄存器。假设k 就是机器 中可供分配的寄存器数目，如果图中的所有结点可以用k 种或者更少的颜色染 色，有边相连的一对顶点接受不同的颜色，那么这种图染色方案对应一种寄存器 分配方案，寻找可着色方案时采用的是“启发式”策略。如果找不到一种k 染色 方案，只好修改干涉图重新染色。修改干涉图是指将干涉图中的某些生命期按照 “抛出( 溢出) 代价最小的原则s t o r e 到内存，后续使用时再从内存l o a d ，从而 重新构造干涉图进行寄存器分配，这个过程称为寄存器“抛出( s p i l l ) 。 图1 2 简单干涉图 图着色算法从出现到现在一直处于不断的改进当中。b f i g g s l 2 s 】等人对 c h a i t i n 算法进行改进，提出一种乐观的着色方案，给待抛出的寄存器变量二次 分配寄存器的机会，有效的改进了c h a i t i n 算法中的两个缺陷菱形着色问题 以及深度嵌套循环的着色问题。g e o r g e 【2 9 】则进一步消减了b r i g g s 算法中相互拷 贝变量数目，以提高编译器生产的代码质量。p a r k 【3 0 】提出一种乐观的合并策略， 5 最大程度的消除了互相拷贝的变量数目，同时也避免了c h a i t i n 中所产生的不必 要的抛出。 图着色寄存器分配算法都力图最大化着色的可能性，减小抛出( s p i l l ) 变量 的数目及代价。然而，受到物理寄存器实际数目的限制，上述算法在特定情况下 都可能产生抛出。减小应用程序寄存器分配时的抛出是寄存器分配算法的研究重 点之一，但是寄存器变量的抛出在一定的情况下是不可避免的。在传统带有 c a c h e 结构的嵌入式设备中，抛出变量通常放置在片外存储器中，由于片外存储 器相对c p u 的低速性，对应用程序的性能和能耗都有一定程度的影响，再加之 c a c h e 的不可预测性将可能导致更糟的性能和能量结果。本文从寄存器抛出变量 存储空间的方面进行考虑，提出一种将寄存器抛出变量存储于s p m 的管理策略。 1 3 课题研究意义 能耗问题成为限制嵌入式系统发展的重要问题，s p m 是嵌入式系统中优化 系统能耗和性能的重要功能部件。研究基于s p m 的存储子系统能耗优化对嵌入 式低功耗优化有着重要的意义。 本文针对图1 3 所建立的存储器子系统，首先提出一种基于s p m 的寄存器 抛出管理策略，将寄存器分配过程中针对片外存储器的变量抛出，修改成为针对 s p m 的抛出，利用s p m 的低功耗、高访问速率等特性，来降低嵌入式设备应用 程序的能耗和执行时间。 图1 3 存储子系统框架 基于s p m 的寄存器抛出管理虽可有效降低程序访问能耗，但是s p m 的空间 利用率和能耗优化结果欠佳，本文对s p m 进行分层，第一层用于寄存器抛出， 其余存储空间用于应用程序布局优化，提出一种综合考虑应用程序执行时各个组 成部分( 数据、指令、全局变量等) 的s p m 空间管理策略，通过s p m 的布局优 化最大限度的减少存储子系统的能耗。 6 1 4 课题研究内容 全局寄存器分配算法都力图最大程度上进行寄存器分配，最小化抛出变量对 系统的所造成的影响，然而，在嵌入式环境中，受到程序执行环境和寄存器实际 数目的限制，寄存器变量抛出在一定程度上是不可避免的。针对传统的基于片外 存储器抛出，访问能耗高、延时长的不足，本文研究利用s p m 作为变量存储空 间时对系统能耗的改进，以及如何有效管理s p m 空间达到整个系统能耗优化。 本文的主要研究内容如下所示： ( 1 ) 基于s p m 抛出变量管理策略的研究。 传统的寄存器分配算法在抛出阶段都将变量放置到片外存储器，在以后的使 用中再重新导入，这将引起处理器对c a c h e 以及片外内存的访问，访问时间和能 耗较大，将抛出变量放置到s p m ，则可有明显的性能和能耗提升。本文通过修 改寄存器分配算法，完成寄存器的抛出代码管理，将抛出变量在原算法中针对片 外内存的抛出和导入过程，设计成为针对s p m 的抛出以及导入过程。在抛出时 依据s p m 空间使用情况进行抛出，变量的导入导出应通过扩展的l o a d s t o r e 指 令来完成，为了支持对s p m 空问的动态访问，提供一个片上存储器管理模块 s p m m ( s p mm a n a g e r ) 来完成对s p m 存取操作。 ( 2 ) s p m 空间分配策略的研究。 由于受到嵌入式设备空间以及成本的影响，s p m 的内存空间十分有限( 通 常情况下很小) ，利用s p m 对存储子系统进行能耗优化，必须提出一种高效、合 理、有针对性的s p m 空间分配和管理算法，以便编译器根据应用程序的抛出变 量的实际需要为其在s p m 空间中分配合理的空间。课题根据寄存器抛出变量的 类型大小，对s p m 的空间进行合理划分，划分采用“等分划分原则，不同长 度的寄存器抛出变量划分的同等的s p m 空间，划分以系统的最大抛出变量为依 据。通过s p m m 按照抛出变量生命期长短，完成变量在s p m 空间的动态管理。 ( 3 ) 基于能耗优化的s p m 空间管理的研究。 能耗优化是嵌入式系统中引入s p m 的主要动因之一。从降低系统能耗的角 度考虑，基于s p m 的寄存器抛出变量管理对存储子系统的能耗优化效果将很有 限，而且由于抛出变量的不确定性，将导致对s p m 空间的巨大浪费。基于能耗 优化的s p m 空问管理对s p m 空间进行分层，使用其中的一层空间来完成寄存器 抛出管理，使用其余空问存储应用程序的能耗热点，针对以往研究对应用程序能 耗热点对象选择的不足，本文基于权重扩展控制流图，全面考虑应用程序中变量、 数据、代码块、堆栈等对系统能耗影响，提出改进的0 1 背包分配算法。 ( 4 ) 实验评估策略研究。 将寄存器抛出阶段的变量在s p m 中进行管理，会导致处理器能耗和性能的 7 改进，必须建立相应的评价标准。本文主要对影响能耗和性能优化因子进行的研 究。分析寄存器抛出变量在s p m 中管理时其他因素，如寄存器分配算法、可用 寄存器数目、基准测试程序大小、以及s p m 空间大小对s p m 管理过程的影响， 以便确定最优的s p m 参数。在相同的测试环境下，评估基准测试程序在s p m 中 抛出同传统c a c h e 结构中抛出时的绝对能耗节省、相对能耗节省以及程序性能的 提升。 1 5 论文组织结构 本文总共包含六个部分，各章节的内容如下： 第一章介绍了本文的研究背景、国内外研究现状、研究内容和意义。 第二章详细介绍论文的研究背景，在仔细研究s p m 体系结构的基础上，仔 细介绍和分析s p m 静动态分配策略，以及所存在的不足；接着系统研究图着色 寄存器分配的抛出策略。 第三章系统研究全局寄存器分配算法中抛出策略，针对抛出变量存储于片 外存储器时的能耗和性能缺陷，提出一种将抛出变量放置于s p m 的抛出变量管 理策略。 第四章充分研究了现存的s p m 分配算法基础上，针对现有的s p m 分配算 法在选择存储对象时的局限性，全面考虑应用程序各组成部分对存储子系统能耗 影响，提出一种基于权重扩展流图的s p m 管理算法。 第五章在能耗模拟器s i m p l e s c a l a r 中，对所提出的基于s p m 的寄存器分配 抛出管理策略和基于权重扩展流图的s p m 空间管理算法进行仿真，验证其性能。 第六章总结全文，对本文的后续研究进行展望。 8 第二章相关研究背景 本章主要介绍论文相关研究背景知识，首先介绍片上存储器s p m 的结构组 成和功能特点，以及其空间分配的静动态分配算法；接着分析图着色寄存器分 配算法的主要过程和其抛出阶段的缺陷，提出基于s p m 的抛出变量管理框架。 2 1 片上存储器s p m 简介 s p m 是一种高速片上存储器，通常使用片上s r a m 实现。一般而言，s p m 和片外存储器的地址空间互相分开，共用相同的地址总线和数据总线，s p m 和 片外存储器拥有统一的地址空间。它处于处理器可直接访问的地址空间之内，任 何对s p m 地址范围内的访问都会触发它，而且，所有对s p m 的访问( 不论读写) 都可以在一个时钟周期内完成。因此，软件程序在s p m 中执行将获得非常显著 的性能提升。对于单纯基于s p m 设计的硬件系统，传统编译器采用的优化技术 无法充分发挥出s p m 的优势。基于s p m 进行性能和能耗优化的关键问题在于， 对于有限的s p m 空间，如何确定哪些程序内容存入其中，从而最大限度地提高 软件的运行速度并降低存储器能耗。 2 2 片上存储器s p m 体系结构 相对于c a c h e ，s p m 是一种硬件实现简单、功耗更低、面积更小而且访问时 间非常稳定的存储部件【6 1 。s p m 的众多优点都是由它的硬件结构所决定的，图 2 1 给出了c a c h e 和s p m 的体系结构，从图中可以看出，s p m 存储器由数据存 储部件( d a t ar a m ) 和少量的地址译码电路组成，c a c h e 存储器除了拥有数据 存储部件和地址译码电路外，还拥有大量的地址标记t a g 和地址比较逻辑。 c a c h es p m 图2 - 1c a c h e 和s p m 体系结构 9 c a c h e 通过较为复杂的硬件电路来管理存储区所存放的数据，和c a c h e 不同， s p m 存储区中所存放的数据是由软件来完成存取的，对于空间有限的s p m 存储 器，选择应用程序的那些部分放入s p m ，依此来提升系统的执行速度和降低系 统能耗，成为人们研究的重点。 2 3 片上存储器s p m 分配策略 按照置放于s p m 空间的对象是否可覆盖，s p m 的分配方式可分为静态分配 和动态动态两类3 1 1 ，s p m 空间分配的主要目的是降低存储子系统整体能耗，同 时也有部分研究关注如何利用s p m 部件来提高嵌入式系统的性能和可靠性。 2 3 1s p m 静态分配算法 s p m 静态分配算法是指所有对s p m 内容的分配操作在编译阶段完成，程序 运行过程中，s p m 的空问内容不在发生改变，即s p m 中存储的单元与程序元素 的映射关系是固定不变化的。静态分配研究重点是寻找一种高效的分配策略，将 程序中使用最为频繁的元素置入s p m 部件，来降低系统的执行能耗。 文献 1 4 1 6 考虑s p m 与c a c h e 共存的情况下，提出了将程序的标量变量和 数组变量数据访问频繁者分配到s p m 中的s p m 管理算法，利用s p m 提高数据 c a c h e 的命中率，该算法仅考虑规则的数组变量结构，没有考虑指令等其它因素。 文献 3 2 将优化对象扩大到所有类型的全局变量，通过对应用程序的静态 分析，统计全局变量的访问次数，并按访问次数由高到低的顺序将全局变量置入 s p m 中，直到s p m 填满，剩余变量则置入片外s d r a m 。 文献 1 7 提出将指令置入s p m 中，算法全面考虑程序数据和指令，按照自 然粒度把应用程序分解成函数块、基本块和数据块等不同类型的块，并为每类块 定义相应的能耗模型，根据各块在执行过程的访问次数得到相应的能耗值，最终 利用整数线性规划算法来求解当置入s p m 中时能带来最大功耗收益值的程序块 集合，以放置于s p m 空间。 文献 3 3 ，3 4 】对按照自然粒度划分应用程序时，导致大尺寸( 甚至大过s p m 的容量) 的数组变量不能作为优化对象的弊端，提出了分割数组的方法，对于尺 寸较大的数组，分割为几个子数据块，由于采用了更小的分配粒度，取得更好船 耗优化效果。 文献 3 5 ，3 6 针对同一函数的两个基本块置入不相邻的存储区需要增加跳转 指令，算法考虑了跳转指令所带来的额外能耗开销。基于应用程序的指令流建立 扩展控制流图( e x t e n d e dc o n t r o lf l o wg r a p h ，e c f g ) ，对内部有跳转指令的函 数进一步划分为子块，直到e c f g 的每个节点均是可连续执行的无跳转指令块。 l o 算法减小了程序块尺寸、考虑了增加跳转指令对尺寸、能耗的影响；同时算法综 合考虑局部变量、全局变量、指令块、以及堆栈等多种因素，并考虑了大跨度空 间跳转对对象能耗带来的影响，进一步提高了低功耗优化效果。 2 3 2s p m 动态分配算法 s p m 静态分配取得了一定的低功耗优化效果，然而由于在程序运行过程中 存储于s p m 空间的内容不再改变，生命周期提前结束的元素至始至终占用着 s p m 空间，使得s p m 的总体利用率偏低。不同于静态管理，s p m 动态管理则在 应用程序执行期间，动念管理s p m 中的内容，通过将部分生命周期结束的程序 元素移出s p m ，并从片外存储器中移入当前执行过程中所需的程序元素，从而 提高s p m 的空间利用率，降低整体功耗，并提高程序运行性能。 从s p m 动态分配是否有硬件辅助单元的角度分析，动态分配策略分为两类： 第一类，编译器协助动态分配，第二类，硬件协助动态分配。 1 编译器协助动态分配 文献 3 7 3 9 中k a n d e m i r 等人较早提出s p m 的动态管理方法，算法结合编译 器将频繁访问的多维数组分割成许多数据块，并相应将s p m 分割一系列空问以 存储不同的数据块，按照最大化s p m 中可存储数据变量的数目和最小化存储内 容在s p m 与片外存储器问传送次数的原则，动态调整s p m 中的内容。该算法的 优化对象局限于应用程序中每个循环中的规则数组数据变量，是一种局部的优化 分配方案。 文献 4 0 】针对k a n d e m i r 算法按照多维数组的维数大小分配s p m 空间的不 足，将同一维数组中数据按照访问频率的不同进行压缩，访问不频繁的数组段可 以按其生命期前后顺序使用同一段s p m 空间。压缩后的数组将产生不同长度的 数据段，分配过程难于管理，文献【4 l 】将s p m 空间划分为不同的b a n k ，尽力为 不同长度的数据段寻找合适的b a n k ，降低算法管理难度。文献 4 2 】将k a n d e m i r 算法推广到不规则数组。上述动态分配都是针对数组进行的s p m 动态优化。 文献 4 3 ，4 4 将应用程序划分为一系列的区域，每个区域用一个数据结构 d p r g ( d a t ap r o g r a mr e l a t i o n s h i pg r a p h ) 中的节点来表示，其中每个函数和循 环体为一个节点，这些节点中的相关变量就是待移入或移出s p m 中的存储对象。 d p r g 将节点按时i 白j 的执行顺序描述形成一个按执行时间排序的数组，需要动态 替换s p m 中内容时，选择与当自订执行节点距离最远的节点中的变量作为候选移 出对象，而当前节点的下一个节点的变量作为候选移入对象，并依据收益模型最 终确定是否完成内容替换。算法可以同时处理全局变量和栈变量，而且是对整个 程序进行分析；不足之处是不能处理含有跳转指令的函数集，也不能处理数组尺 寸大于s p m 存储容量的数组变量。 文献 1 8 】提出程序指令s p m 动态管理。方法核心为：( 1 ) 待置入s p m 的 程序块的所带来的能耗收益高于移动该程序块相关代码的能耗代价；( 2 ) 优化对 象只考虑程序指令中的循环部分。该方法的研究对象局限于循环指令代码段，而 没有考虑程序数据；其次它只考虑了程序中循环代码部分，而没有考虑其它影响 执行频度的因素，诸如无条件跳转，条件分支等。文献 4 5 ，4 6 提出了该策略的优 化算法，将置入s p m 中的侯选对象扩大到全局变量、n o n s c a l a r 局部变量以及指 令代码，但同时还不能处理指针变量、栈数据以及堆数据，也未考虑非连续对象 之间跳转对功耗和体积的影响。 文献 4 7 】将图着色的思想运用在s p m 动态管理算法中，把s p m 划分成一 系列假想的寄存器文件，按照各程序元素的生命周期分其分配空间。文献 4