（电路与系统专业论文）面向能耗优化的指令片上存储器动态布局策略研究.pdf

s c h o o lo fe l e c t r o n i cs c i e n c ea n de n g i n e e r i n g so u t h e a s tu n i v e r s i t y f e b 2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：煎是 日 期：垄垒兰心 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：垄赵导师签名： 摘要 摘要 随着集成电路设计进入深微米和纳米级工艺阶段，s o c ( s y s t e mo nc h i p ) 的能耗问题日益严 重，己经成为制约s o c 发展的主要因素之一。作为s o c 能耗、性能和成本的主要瓶颈，存储子系统 设计一直是s o c 研究的热点。业界通常采用高速片上存储器弥补片外存储器和内核的速度差，并降 低系统能耗。片上存储器一般包括高速缓冲存储器( c a c h e ) 和便签存储器( s c r a t c h p a dm e m o r y ， 以下简称s p m ) 等，两者各具优势且存在互补性，因此c a c h e s p m 共存的架构逐渐成为趋势。 本文借助虚拟内存管理的思想，实现了一种基于内存管理单元( m m u ) 管理的、c a c h e 和s p m 共存的片上存储器机制，并对程序指令部分的动态布局优化策略进行研究。为了充分利用程序的时 间局部性，本文提出时隙管理的方法，将程序执行过程分成若干时隙，并根据不同时隙中指令c a c h e 的命中次数、缺失次数以及指令页的搬运成本等，建立系统能耗模型。以系统能耗模型为基础，本 文以系统能耗作为目标函数，将其抽象为非线性最优化的数学问题，利用整数非线性规划对其进行 求解，获得每个时隙内最有优化价值的指令页。借助虚存管理机制，在每个时隙开始时利用定时器 中断处理程序，将本时隙中有优化价值的指令页通过直接存储器访问( d m a ) 搬运到s p m 中，并修 改页表项完成s p m 缓冲地址空间的重映射，最终实现对程序指令段的动态优化。 本文依据上述设计对多个基准测试程序在不同的片上存储器配置下的优化进行了分析和对比。 实验结果表明，采用本文的优化策略，使用4 kb y t e s 直接关联c a c h e 和8 kb y t e ss p m 对程序指令 段进行优化，相比1 6 k b y t e s 四路组关联的c a c h e ，芯片面积降低1 9 0 ：系统能耗平均降低1 1 2 ， 最高降低2 2 3 。同时，系统性能有明显提升：程序执行时间平均降低1 4 4 ，最高降低2 5 6 。 关键词：片上存储器，动态s p m 管理，指令布局，虚拟内存管理 a b s t r a c t a b s t r a c t a sc m o st e c h n o l o g yc o n t i n u e st os c a l ed o w n ，s y s t e m 一0 1 1 - c h i p ( s o c ) s u f f e r sm o r ef r o mt h ee n e r g y c o n s u m p t i o np r o b l e m ，w h i c hi so n eo ft h em a j o rc o n s t r a i n si nt h es t a t e - o f - a r ts o cd e s i g n m e m o r y s u b s y s t e m ，w h i c hi st h eb o t t l e n e c ko fs y s t e me n e r g yc o n s u m p t i o n ，p e r f o r m a n c ea n dc o s t ，h a sb e e na n i m p o r t a n tp a r ti ns o c o n c h i pm e m o r i e su s u a l l ya r ei m p l e m e n t e dt or e d u c ee n e r g yc o n s u m p t i o na n d b r i d g et h em e m o r yg a pb e t w e e nt h ec o r ea n do f f - c h i pm e m o r y g e n e r a l l y , o n - c h i pm e m o r i e si n c l u d e c a c h ea n ds c r a t c h - p a dm e m o r y ( s p m ) i no r d e rt of u l l yt a k ea d v a n t a g eo ft h e i rc h a r a c t e r i s t i c s ，m o s to f t h eh i g h - e n de m b e d d e dm i c r o p r o c e s s o r se m p l o yb o t h o n - c h i pc a c h ea n ds p mt or e d u c et h ee n e r g y c o n s u m p t i o na n de n h a n c et h ep e r f o r m a n c e t h i st h e s i sp r o p o s e sac a c h e - s p m c o e x i s t e do n c h i pm e m o r ya r c h i t e c t u r ec o n c e r n i n gc o d el a y - o u t ， u s i n gv m u n lm e m o r ym a n a g e m e n t i no r d e rt ot a k ef u l la d v a n t a g eo ft h et e m p o r a ll o c a l i t y , t i m e - s l o t t e d s t r a t e g yi si n t r o d u c e d t h ee n e r g ym o d u l ei se s t a b l i s h e di ne a c ht i m es l o tt h r o u g hc o u n t i n gt h ec a c h e1 1 i 协 b u i l d i n gt h et i m e s l o t t e dc a c h ec o n f l i c tg r a p ho fc a c h em i s s e s ，a n da n a l y z i n gt h ee n e r g yo fc o p i n gc o d e p a g e s t h e n ，a t li n t e g e rn o n l i n e a rp r o g r a m m i n g ( i n p ) i si m p l e m e n t e dt os e l e c tt h em o s tp r o f i t a b l ec o d e p a g e s i no r d e rt od y n a m i c a l l yr e m a pt h ec o d es e c t i o no ft h ep r o g r a m ，i n t e r r u p th a n d l e ri sa d o p t e da tt h e b e g i n n i n go f e a c ht i m es l o tt om o v et h em o s tp r o f i t a b l ec o d ep a g e so ft h es l o tt ot h es p mt h r o u g had i r e c t m e m o r ya c c e s s ( d m a ) 勰w e l la sm o d i f yt h ep a g et a b l e s i ne x p e r i m e n t s ，t h er e s u l t so fd i f f e r e n to n - c h i pm e m o r yc o n f i g u r a t i o n sw e r ea n a l y z e da n dc o m p a r e d t h ee x p e r i m e n tr e s u l t ss h o wt h a tc o m p a r e dw i t h16 kb y t e s4 w a ya s s o c i a t ei n s t r u c t i o nc a c h e ，o u r a p p r o a c h ，e m p l o y i n g4 kb y t e sd i r e c t e d - m a p p e dc a c h ea n d8 kb y t e ss p m ，w h i c ho c c u p y19 o l e s sc h i p a r e a ，r e d u c e st h et o t a le n e r g yc o n s u m p t i o nb y1 1 2 o na v e r a g ea n du pt o2 2 3 w h i l er e d u c i n gt h e p r o g r a me x e c u t i o nt i m eb y1 4 4 o na v e r a g ea n du pt o2 5 6 k e y w o r d ：o n - c h i pm e m o r y ，d y n a m i cs p mm a n a g e m e n t ，c o d ea l l o c a t i o n ，v 1 r t u a lm e m o r ym a n a g e m e n t i i 目录 目录 摘要i a b s t r a c t i i 目录i i i 第一章绪论1 1 1 课题研究背景和意义1 1 2 论文的主要工作和意义4 1 3 论文的结构5 第二章c a c h e 和s p m 研究综述6 2 1 存储子系统研究概述6 2 2 c a c h e 的优化技术一8 2 3 s p m 的优化技术9 2 4c a c h e 和s p m 共存架构的优化技术1 2 2 5 本章小结1 6 第三章c a c h e 和s p m 共存架构的动态管理机制1 8 3 1 总体思路1 8 3 2 利用虚存机制建立c a c h e 和s p m 动态管理的平台1 8 3 3 基于时隙对c a c h e 和s p m 动态管理的方法2 2 3 4 系统能耗构成2 4 3 5 本章小结2 7 第四章c a c h e 和s p m 共存架构的动态存储布局优化策略。2 8 4 1 指令c a c h e 的访存特性分析。2 8 4 2 能耗模型的建立3 4 4 3 分配算法3 8 4 4 本章小结4 2 第五章实验与分析4 3 5 1 实验数据分析。4 3 5 2 最终实验效果5 5 5 3 本章小结。5 8 第六章总结与展望5 9 6 1论文总结5 9 6 2j 琵望5 9 j l 殳谢61 参考文献6 2 攻读硕士期间发表论文情况6 5 i i i 第一章绪论 1 1 课题研究背景和意义 第一章绪论 嵌入式系统经过十几年的迅速发展，从简单的电子表、电子计算器到现在高数据吞吐量和密集 计算的个人数字助理、移动式多媒体终端，所包含的产品出现了显著变化，功能也日益强大。嵌入 式系统产品逐步走入了人们的生活，成为人们生活中不可缺少的一部分。与桌面系统不同，嵌入式 系统产品往往采用片上系统( s y s t e m o nac h i p ：s o c ) 芯片作为系统设计的核心。其原冈在于：1 ) 系统对能耗有较高要求。嵌入式系统产品不同于桌面系统主要追求性能，而需要将能耗纳入最主要 的考虑冈素之一；2 ) 系统的低成本考虑。从消费类电子的角度来说，成本考虑非常迫切；3 ) 系统 小型化和高可靠性的要求日益突出；4 ) 产品上市时间( t i m e t o m a r k e t ) 的压力越来越大。 自上世纪8 0 年代以来，存储器访问速度与处理器速度的差距不断增大。处理器的速度以每年 5 0 1 0 0 的比例增长，而作为片外主存储器的d r a m 的速度增长则一直维持在每年7 左右【l j ，严 重滞后于处理器发展需求。该差值一般被称为存储墙( m e m o r y w a l l ) ，如图1 1 所示。随着处理器速 度与存储器访问速度的差距不断增大，s o c 芯片存储子系统已经成为系统性能、功耗和成本的瓶颈， 因此如何优化存储子系统的架构及管理策略，一直是s o c 研究的关键。 m e m o r yb o t t l e n e c k r e l a t i v e p e r f o r m a r l c e 器裂 图1 - 1 存储墙( m e m o r yw a l l ) 0 9 1 在s o c 存储子系统优化设计中，通常采用高速的片上存储器来弥补片外存储器和内核的速度差， 并降低一定的能耗。考虑到不同存储器之间性能、功耗和成本差异，s o c 存储子系统通常采用层次 结构( m e m o r y h i e r a r c h y ) ，如图1 2 所示。片上存储器通常由高速s r a m 构成，一般包括高速缓冲 存储器c a c h e 和便签存储器s c r a t c h - p a dm e m o r y ( 以下简称s p m ) 。片外存储包括s d r a m 、r o m 等以及相应的外部存储器接口控制电路。由图1 2 中的参数可以看出，片上存储器的速度要远快于 片外存储器的速度，能耗也低于后者。但是由于工艺和成本的限制，往往片上存储器不能做的太大， 面积要远小于片外存储器。 因此，如何设计合理的存储层次结构，并通过恰当的分配算法最大限度发挥片上存储器的优势， 一直是学术界研究的热点。 东南大学硕士学位论文 片上存储器 访问延时 ： 单次访问能耗： 每兆字节成本： 片外存储器 访问延时1 0 1 0 0n s c c 单次访问能耗：1 - 1 0 0r d 每兆字节成本：s o 1 图1 - 2 不同存储子系统的分层图 快 s o c 系统根据应用需求通常选用只配备c a c h e 、只配备s p m 或同时配备c a c h e 和s p m 的片上 存储器层次。同为片上存储器，c a c h e 比s p m 多了一部分比较电路和t a g 存储器，然而c a c h e 体部 分和s p m 一样都是由片上s r a m 构成。 l 地址 土 国 剧 互三 互三 亟固 亟困 ( a ) c a c h e 结构 图1 - 3c a c h e 与s p m 的结构比较 ( b ) s p m 结构 c a c h e 通过t a gm e m o r y 和比较电路对c a c h e 存储体( 即s r a m 部分) 进行硬件管理。基于程 序的局部性原理( 1 0 c a l i t yo f r e f e r e n c e ) ，c a c h e 可以在不需要程序员干预的情况下，动态的将数据换 入片上存储器或换出到片外存储器。当处理器发出数据请求时，c a c h e 的硬件首先通过地址比较检 查该数据是否已经存放在c a c h e 体中，如果数据已经存放在c a c h e 中则直接将该数据返同给c p u ， 这种情况称为c a c h e 命中( c a c h eh i t ) ，一般只需要一个时钟周期的延时。如果c p u 的数据请求不 在c a c h e 中，c a c h e 的硬件预取逻辑将自动将被请求的数据从下一级存储器层次搬运到c a c h e 体， 2 第一章绪论 这种情况称为c a c h e 缺失或c a c h e 不命中( c a c h em i s s ) 。由于c a c h e 缺失时需要访问外存并将内容 写入c a c h e ，针对数据c a c h e 写脏的情况还需要首先将原有的c a c h e 内容写回到外存中，引入的延 时及能耗通常与c a c h e 命中情况相比有一个数量级的差距，这被称为c a c h e 缺失的惩罚( p e n a l t y ) 。 c a c h e 缺失不仅带来了速度和能耗上的开销，还将导致程序执行时间不可预知。 经过多年的研究与改进，单纯使用c a c h e 作为片上存储器已经取得较好的优化效果，但是其高 功耗、占用面积大、程序执行时间不可预知等不足一直限制其在嵌入式系统中的广泛运用，如何在 保证性能的前提下降低其能耗一直是研究的热点c a c h e 可以通过改变其设计参数来满足对c a c h e 能 耗、性能、面积的需求。从内部结构看，c a c h e 的设计参数包括容量大小、行大小、关联度、替换 策略和写策略。从外部结构看，c a c h e 又包括l l 和l 2c a c h e 、统一和分立c a c h e 。根据s o c 芯片在 性能、功耗和面积的不同要求下选择合理的c a c h e 设计参数，己成为研究和设计c a c h e 的一个重点。 s p m 是一种高速片上存储器，通常由s r a m 实现，是现代嵌入式系统中一个非常重要的系统 框架设计考虑因素。s p m 处于处理器可直接访问的地址空间之内，由于传统的s p m 控制器不包含 任何辅助管理数据的逻辑电路，s p m 中的所有内容必须经由软件显式的管理，即通过软件控制决定 在什么时间将什么样的代码或数据放入s p m ，相对于对程序员透明的c a c h e ，增加了程序管理的复 杂性。虽然s p m 的管理相对较为复杂，但是s p m 依然有超越c a c h e 的优点：( 1 ) 由于没有管理逻 辑电路带来的额外代价，相较于传统c a c h e ，s p m 硬件实现更为简单；( 2 ) 由于s p m 没有t a g 存储 器和地址比较逻辑，同样容量s p m 比c a c h e 占用更少的芯片面积，同时单次访问能耗低于c a c h e ： ( 3 ) 由于s p m 使用软件进行管理，并且其访问时间是同定的，因此可以保证了程序执行时间的可 预测性，这对于强调实时性的系统具有很大的吸引力。 早期的s p m 研究以静态的方式进行优化，通过算法将访问最频繁的数据放入s p m 中。程序执 行过程中，s p m 中的数据不与外存发生交换。随着嵌入式系统功能日益强大，传统的静态分配算法 很难高效率地利用有限容量的s p m 资源。冈此，如何在程序运行时动态地将数据、代码、堆栈等换 入换出s p m 逐渐成为研究的重点。动态分配算法一般基于对程序指令、数据的分析，选择适合的代 码片段或数据片段放入s p m 中，往往需要在程序执行映像中插入显式的搬运代码。这些方法要么需 要修改所有对搬运代码或数据的地址引用，要么需要对可被装载的数据或指令片段做诸多限制。由 于l o a d s t o r e 指令效率较低，处理器执行这些指令时将带来额外的系统开销，对于有c a c h e 的系统， 这些插入的指令可能导致原有编译器或连接器对c a c h e 的优化失效，甚至导致指令c a c h e 出现人量 的缺失。另外，由于指令和数据特性不同，一般的动态分配算法仅能针对其中一种进行分析，并且 对程序执行过程中动态使用的堆( h e a p ) 数据和栈( s t a c k ) 数据的优化比较困难。针对这些问题， 文献【2 】 3 通过m m u ( m e m o r ym a n a g e m e n tu n i t ) 的地址映射机制实现s p m 数据或指令的动态管 理，文献 4 】开始采用专用存储器直接存取d m a ( d i r e c tm e m o r y a c c e s s ) 的方式来进行数据搬运。 通过上述对c a c h e 和s p m 特性的说明和比较可以看出，c a c h e 和s p m 各具优势且存在互补性， 因此对两者共存的异构存储资源进行研究，可以充分利用两者优势，从而最大限度降低系统能耗、 提升系统性能。实际上，越来越多针对移动计算和嵌入式计算的新处理器采用了c a c h e 与s p m 共 存的体系架构。比如，a r m y 6 处理器内核p j ，i n t e l 公司的i x p 网络处理器【6 j ，n ) ( p 公司的l p c 3 1 8 0 微控制器【7 】以及s e p 4 0 2 0 处理别驯等等。但是，工业界在推出这些嵌入式s o c 芯片架构时，并没有 给出针对c a c h e 和s p m 的存储布局方案，从而导致对s p m 的使用并不充分。一些早期的研究通常 分别针对c a c h e 和s p m 进行优化，较少考虑c a c h e 与s p m 间的相互关联与影响，这样的优化方案 很雉适用于两者共存的架构。 本文研究工作的重点是c a c h e 与s p m 共存架构下的指令动态布局优化问题。本文首先构建出时 钟周期精确的高层模型，采用m m u 的地址映射机制实现对程序内容的重映射。为了充分利用程序 的时间局部性，本文提出时隙管理的方法，在每个时隙开始时利用中断处理程序，将本时隙中有优 化价值的指令页通过d m a 搬运到片上存储器中，并修改页表项完成s p m 中的内存单元的映射，实 现对程序的动态管理。由于程序的指令部分自身局部性较好，c a c h e 命中率较高，因此在选取最优 3 东南大学硕士学位论文 指令页的策略中，本文通过对指令c a c h e 的命中和缺失进行分析，建立能耗函数并通过整数非线性 进行求解，从而得到在每个时隙中最有优化价值的指令页。 1 2 论文的主要工作和意义 1 2 1 论文的主要工作 本文将建立利用虚存管理机制实现对s p m 进行管理的平台，并利用时隙方法对s p m 进行动态 管理。通过对指令c a c h e 的命中和缺失信息的分析，建立能耗模型并使用整数非线性的算法对其进 行求解，可以获得每个时隙中最有优化价值的指令页。在程序优化时，利用时钟中断，在每个时隙 开始时通过d m a 将本时隙最有优化价值的页搬运到s p m 中，并通过修改页表完成s p m 内容的动 态映射。本文的主要工作为： 1 利用虚存机制建立对s p m 动态管理的实验平台。本文首先建立了基于s y s t e m c 的时钟周期精 确的系统性能及能耗高层模型，并通过修改和增加相关模块来完善仿真平台：通过修改t l b ， 支持对5 1 2 b y t e s 虚拟页的管理，以增加对s p m 的利用率；在t l b 中增加s 位，判断所访问的 地址映射到c a c h e 中还是s p m 中，以减少寻址能耗；扩展传统的、仅能实现寻址功能的s p m 控制器，使其支持对不同粒度的页管理，并能通过主动配置专用d m a 实现对程序的动态换入 换出。 2 提出基于时隙的动态管理方法。为了充分利用程序的时间局部性，本文对程序按照时隙进行划 分，并统计每个时隙中c a c h e 的追踪( t r a c e ) 信息。本文的优化目标是能耗，也会提升一定系统 性能，而性能上的收益会直接导致当前时隙程序执行时间缩短，因此需要通过迭代求解的方法 对时隙进行调整。在程序优化时，在时钟中断中由中断处理程序配置s p m 控制器完成s p m 中 内容的换入以及对页表项的修改，适应本时隙的程序访存模态，同时将按照时隙数给时钟模块 加载当前时隙的长度信息，当时钟模块再次发生时钟中断时，进入下一时隙。 3 通过对指令c a c h e 访存特性分析，得到优化策略的基本思路：按照时隙对程序进行划分，分析 时隙t s k 中指令页的重定位的收益以及搬运成本，形成能耗模型。之后，对能耗模型予以数学 抽象，并经过节点初选后，利用整数非线性的算法中予以求解，最终得到每个时隙中最有优化 价值的指令页。 4 使用本文所提出的优化机制与策略，对多个基准测试程序在不同c a c h e 和s p m 配置下进行验证、 分析和对比，探讨合理的片上存储配置，对系统的能耗，性能及芯片面积予以优化。 1 2 2 论文的主要意义 本文实现了一种利用虚存机制对片上存储器c a c h e 和s p m 管理的机制和策略，并采用时隙管 理的方法对s p m 进行动态管理，以降低系统的总能耗、提升系统性能。 在微处理器的设计中，嵌入式存储子系统已经成为能耗、性能、面积的瓶颈，对存储子系统的 优化是有意义的。随着移动式应用的普及、处理器性能的提升、可靠性问题以及散热成本的限制， 能耗问题已经成为微处理器设计面临的至关重要的一个方面。本文重点关注面向能耗的片上存储子 系统指令动态布局优化，探索一种系统总能耗低、系统总性能高、占用芯片面积小的共存架构的动 态优化机制和策略。 传统的s p m 优化技术依赖于对源程序的分析以及对程序源码的修改。利用虚存机制对程序进 行管理，则不需要在用户程序中显示增加s p m 的搬运代码，而是在中断处理中通过配置d m a 和修 改页表来完成对程序内容的重映射，因此可以实现对用户程序非侵入式的分析和优化。由于本文对 4 第一章绪论 程序的分析和优化基于对c a c h e 的t r a c e 分析，因此基于虚存管理的平台不仅适用于本文所研究的 程序指令部分，而且很容易扩展到程序的数据部分，包括全局数据、常量池数据、堆数据和栈数据。 另外，为了充分利用程序执行的时间局部性特点，本文采用时隙管理的方法，统计每个时隙中指令 c a c h e 的命中次数、对指令c a c h e 缺失信息建立时隙冲突图、分析指令页的搬运成本，以建立完善 的能耗模型并利用整数非线性规划进行求解。基于时隙的分析方法可以将每个时隙中最有优化价值 的指令页利用虚存管理的机制重定位到s p m ，从而获得相较于静态优化更为可观的性能和能耗收 益，最终动态地利用了有限的片上s p m 资源，提高了s p m 利用率。 本文提出的优化机制与策略可以完成对程序指令的动态布局，以充分利用片上存储空间，最终 降低系统能耗、提高系统性能、节省芯片面积。 1 3 论文的结构 本文一共包括六个部分，除去本章绪论所介绍的课题研究背景、论文的主要工作与意义外，后 续各章的内容如下： 第二章对当前存储子系统的研究方向进行了归纳和总结，分别介绍了c a c h e 优化策略、s p m 优 化策略以及共存架构下的优化策略，其中重点分析了针对指令部分的c a c h e 和s p m 共存架构下 的优化策略。 第三章首先阐述了论文的总体思路，将本文的工作重点归纳为动态管理的机制与策略两部分。 之后，建立了c a c h e 和s p m 共存架构下的动态优化机制。机制部分包括基于虚存机制管理的平 台建立，以及利用时隙对程序进行动态管理的方法。为了系统评估本研究所提出的机制与策略， 本文建立了基于s y s t e m c 的时钟周期精确的系统性能及能耗高层模型。同时，本文采用时隙管 理的方法，以充分利用程序的时间局部性，提高s p m 的利用率。最后，给出模型各部分的能耗 参数。 第四章提出了本文所提出c a c h e 和s p m 共存架构下的动态优化策略。通过分析每个时隙中 c a c h e 的命中信息，对c a c h e 缺失信息建立时隙冲突图，以及计算指令页的搬运成本，可以得 到完善的能耗模型。本文以系统能耗作为目标函数，将其抽象为非线性最优化的数学问题，利 用整数非线性规划求解，从而获得每个时隙内最有优化价值的指令页。 第五章本文通过实验验证了本研究的机制与策略。首先分析有代表性的基准测试程序c j p e g 、 b l o w f i s h 和s h a 的设计空间探索及系统总能耗的构成，并分析和归类s p m 容量大小变化对不 同基准测试程序系统总能耗和性能的影响。最终选出两组较优的配置，并对多个基准测试程序 进行能耗和性能分析。 第六章对论文进行总结，并提出了未来继续研究的方向。 5 东南大学硕士学位论文 第二章c a c h e 和s p m 研究综述 本章将分析、整理国内外c a c h e 和s p m 的研究动态，总结别的团队在本领域研究中的创新与不 足，作为本论文研究与设计的理论基础。首先，第一节存储子系统研究概述将分析c a c h e 和s p m 的 特征及区别，指出c a c h e 和s p m 共存架构可以充分利用片上存储资源，因此逐渐成为发展趋势。第 二节和第三节将分别分析针对c a c h e 和针对s p m 的优化技术。第三节重点分析针对c a c h e 和s p m 共存架构的存储子系统优化的几组相关研究，包括日本九州大学的i s h i t o b i 等人提出的共存架构优 化策略的研究，韩国首尔大学e g g e r 等人关于利用虚存管理实现地址空间的动态重映射的研究，意 大利v e r m a 等人关于c a c h e 冲突行为建模的研究等。 2 1 存储子系统研究概述 存储器访问速度与处理器速度之间的差距一般被称为存储墙，随着处理器速度的不断增加、存 储器访问速度增加较慢，该差值一直不断扩大1 9 j 。因此，s o c 芯片存储子系统已经成为系统性能、 功耗和成本的瓶颈，如何优化存储子系统的架构及管理策略，一直是s o c 研究的关键。 片上存储器通常由高速s r a m 构成，速度较快，一般用来弥补片外存储器和内核的速度差，并 降低系统能耗。s r a m 的全称是静态随机存储器( s t a t i cr a n d o m a c c e s sm e m o r y ) ，由六个晶体管构 成，以双稳态电路形式存储数据，不需要刷新电路即能保存它内部存储的数据。与动态随机存储器 ( d y n a m i cr a n d o ma c c e s sm e m o r y ) 相比，s r a m 结构复杂、制造成本高，但其读写性能也较高且 能耗较低，并且其制造上艺与普通c m o s 工艺兼容。因此s r a m 主要用在比主内存小得多的片上 存储子系统中。 在嵌入式系统中，s r a m 通常以高速缓冲存储器c a c h e 和片上便签存储器s p m 两种方式实现 c a c h e 通过t a g 存储体和比较电路对c a c h e 数据存储体( 即s r a m 部分) 进行硬件管理。基于程序 的局部性原理，c a c h e 可以在不需要程序员干预的情况下，动态的将数据换入到片上存储器或换出 到片外存储器c a c h e 的物理结构较为复杂，其参数一般包括c a c h e 的容量、c a c h e 的行大小、组关 联度、写策略以及替换策略( 分配策略) 等。衡鼍c a c h e 性能和能耗的一个重要的标准是命中率。 由于c a c h e 不命中时，需要访问外存，带来的性能和能耗惩罚( p e n a l t y ) 较大，因此一般认为高于 9 0 的c a c h e 命中率才能保证性能和能耗收益不会被惩罚抵消。一般而言，增加c a c h e 容量，提升 c a c h e 的组关联度可以增加c a c h e 的命中率。但是增加容量和提升组关联度本身会带来c a c h e 单次 访问时间及访问能耗的提高，并增加芯片面积。因此，在设计空间探索时，可以通过改变c a c h e 参 数来寻求面向性能、面向能耗、面向面积的最优配置。此外，也可以通过对软件程序布局( l a y o u t ) 优化来提高c a c h e 的命中率，增添编译阶段对c a c h e 组织特性的适应。 桌面机领域对实时性、芯片面积、能耗等要求较低，因此引入c a c h e 可以取得较好的优化效果。 但由于嵌入式系统具有不同于桌面机的一系列要求，利用传统c a c h e 提升嵌入式系统性能还存在一 些务必解决的问题，主要包括： 1 由于c a c h e 由硬件进行控制，需要增加比较电路和t a g 存储体；在对c a c h e 进行读写操作时， 又需要增加决定c a c h e 行中缓冲的数据在当前是否有效的v a l i d 位；对于数据c a c h e ，还有写脏 标志位( d i r t yb i t ) ，用于标明c a c h e 中的数据内容发生变化，在进行c a c h e 行内容替换时需要 将写脏的行换出到主存中，以保证数据的一致性。这些管理电路都将占 j 额外的芯片面积，从 而导致芯片成本的上升。例如，根据c a c t i3 2 ，4 k b y t e s 的s p m 所占用的芯片面积，仅为4 k b y t e s 四路组关联c a c h e 的5 7 8 。 6 第二章c a c h e 和s p m 研究综述 2 嵌入式系统中，便携式电子产品及以消费类移动设备被广泛使用。由于这些移动设备体积小， 流动性大，为了避免频繁充电和更换电池，工业界通常对移动设备的能耗设计有较高要求。由 于c a c h e 每次对存储体的访问都需要进行地址比较，与直接进行访问的s p m 相比，这一部分操 作消耗了额外的能耗。在a r m 9 2 0 t 中，c a c h e 部分可以占用系统能耗的4 3 以上【1o 】【 c a c h e 的单次读写能耗随着容量和组关联数的增加而提高。 3 c a c h e 缺失时需要实际访外存操作，开销较大( 也被称为c a c h e 缺失的惩罚) 。由于c a c h e 物理 组织结构的特点还可能带来c a c h e 的某些行反复换入换出某些地址空间的问题，即c a c h e 冲突。 在c a c h e 发生冲突的时候，被映射到同一c a c h e 行的内容会不断的替换，带来大量的访问外存 和替换操作，从而导致系统性能急剧降低，系统能耗急剧增加。通过增大c a c h e 容量、增大组 关联数等方法，可以减小c a c h e 冲突，但是这样又会引入新的芯片面积并提升单次c a c h e 读写 的能耗，并且不能从根本上解决冲突问题。 4 在嵌入式系统应用中，c a c h e 不适用于一些对实时性有严格要求的系统。虽然c a c h e 可以提高 系统访问速度，降低存储访问的平均延时，但是c a c h e 缺失时带来的数据写网( 仅针对有写回 要求的数据c a c h e 部分或者统一c a c h e ) 、重新填充c a c h e 行等操作会引入长时间的延迟。由于 出现c a c h e 缺失的时间受制于诸多冈素，比如中断处理程序、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 r a m 实现，是现代嵌入式系统中一个非常重要的系统 框架设计考虑冈素。s p m 处于处理器可直接访问的地址空间之内，任何对s p m 地址范同内的访问 都会经由总线仲裁器触发。在扣除总线延时的前提下，所有对s p m 的访问都可以在一个时钟周期内 完成。由于传统的s p m 控制器不包含任何辅助管理数据的逻辑电路，s p m 中的所有数据必须经由 软件显式的管理：由于没有管理逻辑电路带来的额外代价，在相同容量下，s p m 占用的芯片面积和 单次访问的能耗都小于c a c h e ，访问速度也高于c a c h e 。由于s p m 不像c a c h e 需要由硬件自动完成 缓冲数据的换入换出操作，因此s p m 不存在访问缺失的情况，始终能够保证一个时钟周期的访问时 间，从而保证了程序的确定性。但是，由于需要软件进行管理，相对于对程序员透明的c a c h e ，s p m 增加了程序管理的复杂性。总的来说，相比于传统c a c h e ，s p m 是一种硬件实现更为简单、单次访 问功耗更低、占用芯片面积更小而且访问时间可预知的片上存储器实现形式，更适合用于构建实时 性要求高的嵌入式系统。s p m 和c a c h e 的区别如表2 1 所示。 表2 - 1c a c h e 和s p m 的区别 c a c h es p m 容量大小、行大小、关联度 主要参数容量大小 替换策略、写策略 管理方式硬件管理，软件配置软件管理 硬件结构复杂简单 命中一个时钟剧期一个时钟周期 速度 其它由行大小和片外存储器的访问速度决定 _ - - _ _ _ 。一 程序简单情况下性能低，程序简单情况下性能高， 相同 性能 复杂情况下性能商复杂情况下性能低 容量功耗 高低 面积 大小 7 东南大学硕士学位论文 由于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 的基本配置信息。本章 第三节将介绍针对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 的不同特性，将程序划分为合适的存储区域，使得程序在执行的过程中， 可以根据优化算法，自动的选择合适的片上存储器类型。 2 2c a c h e 的优化技术 受到芯片面积、系统能耗的制约，嵌入式系统使用的c a c h e 容量较小，一般采用单级架构；对 于高端的、面向媒体计算的嵌入式系统中，也开始配置二级统一c a c h e ，如a r m l1 7 6 i j 2 j 等。 一些研究针对c a c h e 的硬件配置进行设计空间探索c a c h e 的硬件参数一般包括c a c h e 容量、行 大小、组关联数以及c a c h e 分级等。z h o n g 等人和a l e k s a n d a rm i l e n k o v i c 等人在确定某些c a c h e 参 数不变的情况