（电子科学与技术专业论文）面向性能优化的压缩cache技术研究.pdf

国防科学技术大学研究生院博士学位论文 别，并将其记录到一个错误记录表m r t ( m i s t i i r - e c o r dt a b l e ) 中，然后根据此 记录表对l r u 替换错误进行及时纠正。模拟实验表明，m l r u c 能有效地改善 l 2 压缩c a c h e 的替换行为，减少l 2 压缩c a c h e 的失效率。 4 研究了压缩c a c h e 技术对多线程处理器性能的影响，并通过模拟实验验证 了u c c h 结构能够改善多线程处理器的性能。由于多线程处理器中有多个同时运 行的线程共享整个片内c a c h e 层次结构，破坏了从l l 数据c 础伦到l 2c a c h e 的数 据局部性，增大了c a c h e 失效率，并使l 1 l 2 主存之间的总线传输带宽压力显著增 长，因此，虽然多线程处理器降低了对访存延迟的敏感性，但却显著增加了对c a c h e 层次结构的容量以及访问带宽的敏感性。由于u c c h 结构能够显著增加l 1 数据 c a c h e 和l 2c a c h e 的有效容量，同时由于在l 1 l 2 主存之间直接以压缩格式传输数 据，能显著降低l l - l 2 主存之间的总线传输带宽需求，因此u c c h 结构能够改善 s m t 处理器的访存性能。 主题词：s f p c 压缩算法，压缩c a c h e ，部分c a c h e 行预取，压缩c a c h e 替换 策略，s m t ，m l r u c 替换策略 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t s m c e 劬o v a t i o n si nc m o st e c h i l o l o g ) ri nr e c e n ty e a r sh a v el e dt 0 耐o 咖a n c e g a pk 帆瞎e np r o c e s s o r 觚dm e m o 哆w i d e l l i n g ，m o d e mp f o c e s s o f su o n eo rm o f e l e v e l so fo n c l l i pc a c h e st 0a l l e v ia ：t et h ee v e r i n c r e a s i n gp r e s s u r eo fm e m o 哆a c c e s s e s i n a d d i t i 吗舔也ec 螂d e i l s 蚵硫r e a l s i n g ，c 螂m u l t i 即c e s s o r s ( m p ) 觚dm u l t i 缸e a d 魄 似t ) a r eb e c o m i n gm 2 l i n s 缸e a i i la r c l l i t e c 加r e so fc u n e n tp r o c e s s o rd e s i g n t h eb o t l l a r c l l i t e c t u r e sc a i lg r e a t l yi i l l p r o v ep r o c e s s o rp e 墒珊a n c ea n dt t l r o 咖u tb ye x p l o i ! t i i 玛 b o t l lm r e a d 一1 e v e l 锄dh 1 舭t i o n - l e v e lp a r a l l e l i s r 玛b 毗m e 粤o w i l l gm e m o 巧a c c e s s d e m a r l di nm p m te n v i l - o 伽n tc h a l l e i 培et 1 1 et 王l r o u g h p u ta b i l 埘o f 廿1 e i ri n e m o 巧 s u b s y s t e m t h ep r o c e s s o rd e s i g n e r 咖_ l s td e t e m l i n em et r a d e o f fb e t 、) v nc o r e s 锄d c a c h e si 1 1a 缸x e da r e ab u d g e ts o 也a tn e 弛【e rc o r e sn o rc a c h e si s 也eo i l l yp e 雨粼e b o t t l e n e c k c o m p r e s s e dc a c h et e c l l n o l o 影c 趾c l l a i l g e 也e 砌e o f fb e 押e e nc o r e s 觚d c a c l l e sa 1 1 da 1 1 0 wad e s i 口w h e r em o r eo m c l 卸a r e ai sa l l o c a t e dt op r o c e s s o rc o f e ss i i l c e o n - c k pc a c h ec o m p r e s s i o nc 觚i i l c 麟et l l ee 廊c t i v ec a c h es i z e 埘也o u ts i 鲥6 c 锄t l y i n c r e 硒i i 培i t sa r e a 赳l da v o i ds o r n em i s s e s u 0 n l m a t e l y ，c a c l l ec o m p r e s s i o na l s oh 嬲a n e g a t i v cs i d ee f i f e c t ，s i n c ec o m p r e s s e dc a c h el i i l e sl m ，et ob cd e c o m p r e s db e f 0 r e b e i i 坞u s e db yp r o c e s s o r t h i s l e a n sm a ts t o r i n gc o m p r e s s e dl i i l e si i l c r e a s e sc a c h e 胁 l a t e n c y s ot h i sp a p e rr e a r c h e do nt 1 1 ec o m p r e s s e dc a c h et e c l l n o l o g yf o rp e r f o n 】姐n c e o p t i l l l i z a t i o n t h em e t h o d s ，s u 盘舔o p t i m i 咖gc o m p s s e dc a c h el i i e r a r c h y ，s i n l p l i 母试g c o m l ) r e s s e da l g o r i n l i i l 趾d 妇p r o 讥n gc a c h er e p l a c e m e n tp o l i c ye t c w e r ep r o p o s e dt 0 i m p r o v ep e 0 m 啪c eo fc o m p r e s s e dc h e t h em a i l lc o n t r i b u t i o n so ft h i sp 叩e ra r e 舔 f o l l o 、s ： 1 w 池s i i n p l i 矽i n gm ef r e q u e n tp a 他mc o m p r e s s i o n ( f p c ) a l g o r i t h i i l ，w m c h u s e db yl 2c a c h ec o m p r e s s i o 玛觚dd i v i d i n gt l l ed e c o l p r e s s i o np r o c e s so f c o n l p r e s s e dc a c h el i i l ei i l t ot w os t a g e s ，、v ep r o p o s e dan o v e ld e c o l n p r e s s i o n p r o c e s so fl 2c o m p r e 豁e dc a c h e l i n eb a s e d0 ns i i n p l ef r e q u e n tp a t t e m c o n l p r e s s i o n ( s - f p c ) a l g o r i n 1 1 1 ep r o p o s e ds c h e r n e c a i id e c r e a s el 2 d e c o m p r e s s e dl a t e n c ylc y c l e 锄ds u p p o r tc o n l p r e s s i n gl ld a 协c a c h ed a t a w ee v a l u a t e dt l l es c h e i n eb ys 妇u l a t i o ne x p e r h e n t s 趾dd e s c r i b e d 吐l e h a r d 、硼埴ei i l l p l e m e n t a t i o no f 也ec o m p r e s s i o ns c h e m ei i ld e t a i l 2 w ep r o p o s e dau i l i f i e dc o n l p r e s s e dc a c l l e1 1 i e r a r c l l y c c h ) m a tu s e sa u n i f i e dc o m p f e s s i o na l g 嘶t l 皿i i lb o t l ll 1d - c a c h e 锄dl 2c a c h e ，c 2 l l l e d s i m p l ef r e q u e n tp a 呛mc o m l ) r e s s i o n ( s - f p c ) u c c hc a i li n c r e a t h ec a c h e c a p a c 时o fl 1d c a c h e 觚dl 2c a c h e 谢t l l o u ta i l ys a c r i f i c eo f t l l el 1c a c h e a c c e s sl a t e n c y t h el a y o u to fc o m p r e s s e dd a t ai nl ld a t ac a c h eo fu c c h c n a b l e sp a n i a lc a c h el i n ep r e f e t c h i n g 觚dd o e sn o ti n 仃o d u c ep r e f l e t c hb u f f e r s o ri n c r e a c a c h ep o l l u t i o na i l dm 锄。巧仃a m c t h ee x p e 血n e n ts h o w su c c h 第i i i 页 国防科学技术大学研究生院博士学位论文 c a nd i s t i i l c t l yi i i l p r o v et ：h cp e r f o m 砌c e 3 w e p r o p o s e dan o v e lm 础f i e d l r ur 印l a c e m e n tp o l i c yf o rc o m p r e s dc a c h e 。 ( m l r u - c ) m l l w - cr e p l a c e m e mp o l i c yu s e se x 仃at a g si i lc o m p r c s s e dc a c h e t oc o n s t n l c tas h a d o wt a gs t n l c t ，w m c hb eu s e dt 0i d e m i 母a i l dr c l c o r dt h e i i l i s t a k er e p l a c e m e mi 1 1l r u p o l i c y t h e 面s t a k er e p l a c e m e 鹏i 1 1l r up o l i c y r e c o r d e db ys h a d o wt a gs 咖c tw o u l db es t o r e di nm i m 妇r e c o r dt a b l e ( m r n l em l r u c 、o u l dc o n e c ta 舱m i s t 2 d 汜r e p l a c e m e n td e c i s i o n a c c o r d i i 培t ot h ei i l i s t a 】k er e p l a c e m e n tr e c o r di 1 1mr 1 t h ee x p e r i i i l e n ts h o w s l a tm l r u cc a ne v i d e n t l yd e c r e a s el 2c o n l p r e s s e dc a c h en l i s sr a t e 4 w ep r o p o s e du s i i l gc o i n p r e s s e dc a c h et e c l l i l o l o g ) ，t o 卸r o v em l l l t i 吐l r e a d i n g p r o c e s s o rp e r f 0 册a j l c e b e c a u s e l ei l a t al o c a l i t vo fl1d c a c h ea n dl 2c a c h e i sh 1 1 n e db y 蛐g o n 出pc a c h eh i 眈眦h yb e m e e nt l l i e a d s ，m tt e c h n o l g y d i s 墙t l yi r l c r e a s e st h ec a c h ei n i s s 瑚l t e 锄dm e m o r y 仃a 伍c t h ed e m a l l d sf o r c a c h ec a p c i 锣锄1 d 纰b u sb 锄d 、) l r i i b e t w e e nl e v e l so fc a c h = c si r k r e a s e a p p a r e n t l y b e c a u s eo l l ru c c hs c h e r n ec a ni r l c r e a s ec 印a c 埘o fl ld c a c h e 趾dl 2c a c h ea n dd e c r e a s e 血s sr a 沧o fb o t l ll 1d c a c h ea n dl 2c a c h e d i s t h l c t l y ，i tc 锄a l l e v i a t et 1 1 el1 - l 2 i 瑚i i lm e m o 珂b a l l d 惭d 也d e m 弛da n d i m p r o v em ep e r f o n n a n c eo fm tp 】0 c e s s o r k e yw 0 r d s ：s - f p c ，c o m p r e s s e dc a c h e ，p a r t i a ic a c h el i n ep r e f e t c h i n g ， c o m p r e s s e dc a c h er e p i a c e m e n tp o c y ，s m t ，m l r u - c r e p l a c e m e n tp o “c y 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 常见模式压缩( f p c ) 编码1 7 表2 2c a c h e 重叠压缩的常见值编码2 4 表3 1s f p c 压缩编码3 l 表3 2 基准处理器配置4 7 表4 1l 2 压缩c h e 在l r u 、m l 烈j c 、o p t 替换策略下的失效率6 9 表5 1s m i 处理器的基本配置8 1 表5 2 多线程工作负载8 2 第l v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 11 9 8 0 年以来存储器和c p u 性能随时间而提高的情况( 以1 9 8 0 年时的性能为 基准) ：! 图1 2c a c h e 子块大小对内部碎片的影响。7 图2 1 动态常见值字典结构1 6 图2 2m x t 系统中的l 3c a c h e 行通过c t t 映射到物理的压缩存储行。1 8 图2 3h a l l n o r 的i i c c 压缩c a c h e 结构19 图2 4e k m a i l 的基于f p c 编码的压缩主存的寻址方式正文内容2 1 图2 5 面向低功耗的常见值压缩l 1 数据c a c h e 结构2 2 图2 6 面向高性能的常见值压缩l l 数据c a c h e 结构。2 3 图2 7c a c h e 重叠压缩存储结构一2 4 图2 8p p u j 撒的l 1 压缩c a c h e 的压缩数据布局2 5 图3 1 砧舱设计的f p c 压缩c a c h e 层次结构2 9 图3 2a 1 a a 设计的f p c 压缩c a c h e 的解压缩流水线结构2 9 图3 3 各种常见模式在测试程序引用中的分布31 图3 4s f p c ，f p c ，x r l ，b r c l 的平均压缩率3 3 图3 5 压缩c a c h e 层次结构3 4 图3 6l 1 压缩数据c a c h e 数据存放格式3 5 图3 7l 1 压缩数据c a c h e 结构3 6 图3 8l 1 压缩数据c a c h e 的访问流程3 7 图3 9l 2 压缩c a c h e 的数据存放格式3 8 图3 1 0l 1c h e 的解压缩器4 0 图3 1 ll 1 数据c a c h e 的压缩器4 1 图3 1 2l 2 到l l 压缩c a c l l e 行拆分流水线4 3 图3 1 3l 2 到l 1 压缩c a c h e 行拆分流水线第一站由前缀计算压缩字长度模块4 4 图3 1 4 拆分流水线第二站4 4 图3 1 5l l 数据c a c h e 有效容量随c a c h e 行尺寸变化时的改变4 9 图3 1 6 四种不同配置下基准处理器l l 数据c a c h e 失效率相对于b c 配置的比较5 0 图3 1 7 四种不同配置下基准处理器l 2c a c h e 失效率相对于b c 配置的比较。5 0 图3 1 8 四种不同配置下基准处理器性能( i p c ) 相对于b c 配置的比较5 0 图4 1 一个存储引用序列的实例5 4 图4 2图4 1 的引用序列分别在传统c a c h e 的l r u 与o p t 替换策略下的c a c h e 行为 ! ；! ； 第v 页 国防科学技术大学研究生院博士学位论文 图4 3 压缩c a c h e 替换行为的描述5 8 图4 4l i 替换错误探测机制的结构。6 0 图4 5l r u 压缩c a c h e 行为仿真器6 4 图4 6o p t 压缩c a c h e 行为仿真器6 6 图4 7 压缩c a c h e 替换策略仿真系统结构图6 7 图4 8l 2 压缩c a c h e 在l r u 、m l r u c 、o p t 替换策略下失效率相对于l r u 的比较 6 9 图5 1 指令发射槽的利用情况7 5 图5 2s m 与c 中启动新线程后对l 2c a c h e 访存压力的变化情况( 来自【8 2 】) 7 8 图5 3 模拟的多线程处理器压缩c a c h e 层次结构8 0 图5 4 四种c a c h e 配置在不同工作负载下的性能( i p c ) 比较。8 3 图5 5 四种c a c h e 配置在不同工作负载下l ld c a c h e 的失效率相对于b c 配置的比较 8 z i 图5 6 四种c a c h e 配置在不同工作负载下l 2c a c h e 的失效率相对于b c 配置的比较8 4 图5 7 四种配置下，l 1 l 2c a c h e 之间的总线占用率相对于基本配置的比较8 5 图5 8 四种c a c h e 配置下，l 2c a c h e 与主存之间访问带宽需求与b c 的比较8 6 第v l 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他入已经发表和撰写过的研究成果，也不包含为获得国防科 学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本文研究所做的任何贡献，均已在论文中作了明确的说明并表示 谢意。 学位论文题目：亘自性能笾丝鲍匡缉曼地呈撞苤巫究 学位论文作者签名： 翌耋b 聋日期：z 叫年午月“日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本 人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的 复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部 分内容编入有关数据库并进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：亟囱性能岱他的匡缠咝丛撞莶硒究 学位论文作者签名： 里墨丛釜日j 朝：卅年牛月二5 日 作者指导教师签名： ；幺红丝 r 期：枷7 年p 月形日 国防科学技术大学研究生院博士学位论文 第一章绪论 为填补处理器与主存在速度上的巨大差异，现代计算机系统一般都在处理器 内核与主存之间设置一级或多级快速小容量的c a c h e ，形成层次式访存结构，利用 局部性原理来改进系统的访存性能。因此，提高c a c h e 的性能对于提升整个计算机 系统的性能有着重要的意义。 c a c h e 的性能与它的容量、访问延迟和带宽、c a c h e 行大小，相联度、替换策 略等结构参数【1 9 】有关，同时程序本身的局部性也对c a c h e 性能的发挥起着重要的作 用。随着多线程技术的出现，处理器内核虽然对访存延迟的容忍度有了很大提高， 但同时也要求更大的c a c h e 容量和访问带宽。压缩c a c h e 是一种利用数据压缩方法 保存c a c h e 数据的技术，它能够在不显著增加c h e 面积的情况下显著提高它的有 效容量、降低失效率，减少存储层次间的数据交换。 本文研究了利用压缩c a c h c 技术改善处理器性能的方法，对压缩c a c h e 的压缩 编码算法以及层次结构的设计实现，压缩c a c h e 替换策略的优化，以及利用压缩 c a c h e 技术改善多线程处理器的访存性能展开了深入研究。 本章的组织结构如下：1 1 节介绍了压缩c a c h e 技术的研究背景与意义：1 2 节 介绍了面向性能优化的压缩c a c h e 技术所面临的几个问题；1 3 节结合压缩c a c h e 的性能估算公式给出本文对压缩c a c h e 性能进行优化的方法；1 4 节叙述了本文的 主要工作；1 5 节给出本文的组织结构。 1 1 1 存储墙问题 1 1 研究背景和意义 存储器是计算机系统的核心部件之一，它的性能好坏直接影响到整个计算机 系统的性能。如何平衡存储器系统的容量、速度和价格，始终是计算机体系结构 设计的关键问题之一。但是，在计算机系统中，处理器与存储器性能的提升并不 同步。随着半导体工艺水平的发展以及处理器微体系结构技术的进步，处理器时 钟频率增长的速度远远超过了存储器访问周期缩短的速度，这导致两者之间的性 能差距越来越大。如图1 1 i l 】所示，在1 9 8 0 年至1 9 8 6 年间，处理器的性能以每年 3 5 的速度递增，而从1 9 8 7 年开始，处理器的性能则是以每年6 0 的速度递增。而 存储器性能提高的速度却相对慢很多。例如，d r a m 的访问速度每年大约只提高7 。 因此，两者的差距每年都在以大约5 0 的速度增加，从而产生了“存储墙”问题。另 外，随着处理器中i l p 开发技术的不断发展，对存储器性能的要求也随之增强。 由于在每个时钟周期，处理器需要同时执行多条指令，这就要求存储器能够及时 第l 页 国防科学技术大学研究生院博士学位论文 向计算内核提供更多的指令和数据。为此，现代微体系结构设计者普遍采用在处 理器片内设置一级或多级c a c h e ，利用程序的局部性原理来解决这一问题。 毋$ 毋毋毋孝尊霉害毋窜霉毋葶零擎露霉窖拿葶爷荸毋零孝 图l ，l1 9 8 0 年以来存储器和c p u 性能随时问而提高的情况( 以1 9 踮年时的性能为基准) c a c h e 是位于处理器内核与主存之间的一级或多级速度快、容量较小的高速缓 冲存储器，它与主存一道形成层次式访存结构，以便减少具有高延迟开销的主存 访问次数，提高系统性能。在使用c a c h e 访存结构的基础上，一些微体系结构技术 也被应用于缓解t 存储墙问题：如存储前瞻1 2 ，3 】、乱序执行【2 眙1 】技术通过提前调度 访存指令，或者将访存指令与其它有用指令的执行相重叠来隐藏访存指令的延迟； 预取h ，5 ，6 ，7 ，8 、线程级前瞻和多线程执行i l o ，1 2 ，1 3 t 1 4 ，15 1 、r l 麟虹a d 执行1 1 6 ，1 7 j 等技术则通 过增加访存操作的并行性来缓解访存延迟对性能的影响；值预测【ls 】技术则通过预 测l o a d 指令载入的值，并在验证正确后提交来减少访存延迟。上述这些消解或屏 蔽访存延迟的技术都能有效的减少系统的平均访存延迟，但是，除乱序执行技术 以外，这些技术都会产生许多无效的访存操作，从而加重系统存储访问的带宽压 力。更直接地隐藏访存延迟的方法就是增加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 技术不会增加系统访存带 宽需求，这对于目前面向吞吐率的计算机系统很有吸引力。 1 1 2p i n 带宽瓶颈 目前，随着在线事务处理、b 搜索与浏览、电子商务等应用的不断涌现、普 第2 页 辑= k 嘶 一c 扩?呶能畔 攀一 p 舌舅毫 恍m 、，。， 国防科学技术大学研究生院博士学位论文 及与发展，这些面向高吞吐率的多线程应用越来越依赖于能同时运行多个线程的 高性能处理器。而随着微处理器的主频进入g h z 时代，单纯依靠提高主频来改善 处理器性能的方式已经渐趋于饱和f 2 羽，处理器性能的提高将更多地依赖于更好地 开发程序中存在的各种并行性( 包括指令级和线程级并行性) 此外，随着半导 体工艺水平的提高，单个芯片上的晶体管数量不断地增加，使得将多个处理器内 核集成到一个芯片的单芯片多处理器( c l l i pm u l t i p r o c e s s o rc m p ，简称多核) 技术， 以及一个处理器内核集成多个执行线程的多线程( m u l t i t h r e a d i n g ，m t ) 技术成为 可能。与传统的超标量超长指令字处理器仅仅开发单个程序内细粒度的指令级并 行( i l p ) 不同，多核多线程处理器同时还开发工作负载中存在的粗粒度的线程级并 行性( n 鹏a d l e v e lp a r a l l e l i s m ，t l p ) 。t i j 的开发极大地提高了系统的计算吞吐率， 因此，在可预见的将来，多核多线程处理器，甚至基于多线程内核的多核处理器 将成为未来微处理器结构的主流。 多核多线程处理器的使用显著增加了对片外p i n 带宽的需求，因为1 1 j 的开 发增加了片间以及处理器存储器之间的通信需求。但是，p i n 带宽的增长速度也远 低于片内传输管性能的增长速度。根据2 0 0 4i t r sr o 础n 叩的报掣】，在未来的 1 5 年内，每个芯片可用的p i n 的数量以每年大约1 1 的速度增长，这远远低于片 内器件数量2 6 的年增长率。这意味着片内处理器计算能力的增长速度远远高于 片外通信能力的增长速度。另外每个p i i l 的封装成本以每年5 的速度降低，远低 于p i i l 数量的年增长率，这意味着芯片的封装成本也以每年5 的增长率增加。缓 解p i n 带宽瓶颈有赖于提高片内c a c h e 的性能。压缩c a c h e 技术通过增加c a c h e 的 有效容量，降低失效率来减少处理器与片外存储器的数据交换需求。另外，如果 处理器多个存储层次能够以统一的压缩编码方式保存数据，则这些层次间的数据 交换就能直接以压缩格式进行传送，从而显著降低各存储层次间数据交换带宽的 需求，这对于缓解p i i l 带宽瓶颈问题也有重要的意义。 1 1 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 的有 效容量和访问带宽。 第3 页 国防科学技术大学研究生院博士学位论文 目前，支持多线程的处理器结构主要有多核( m p ) 结构和多线程( m d 结构两 种。在多核处理器中，每个处理器内核都有自己私有的l 1 指令和数据c a c h e ，多 个处理器内核共享片内二级c a c h e 。如果将压缩c a c h e 技术应用到l 2c a c h e ，就可 以使芯片内留出更多面积来集成更多的处理器内核，从而提高多核处理器的计算 能力，增加它的计算吞吐率。对于多线程处理器，由于有多个线程共享l 1c a c h e ， 使l 1 数据c a c h e 中数据的局部性变差，导致l 1 数据c a c h e 失效率显著增加。这造 成m t 结构相对于m p 结构而言，对l 2c a c h e 的访问量急剧增加【2 3 j ，可能使l l 与 l 2c a c h e 之间的存储带宽成为影响处理器性能的瓶颈。因此，如果能将压缩c a c h e 技术同时应用于多线程处理器中的l 1 数据c a c h e 与l 2c a c h e ，且使用统一的压缩 编码，则这两级c a c h e 就能够以压缩格式交换数据。这对于减少多个线程之间相互 干扰造成的c a c h e 容量资源冲突，以及l 1 - l 2c a c h e 之间的总线带宽资源冲突，缓 解多线程处理器对l 2c a c h e 访问压力增大的问题将很有益处。 1 2 面向性能优化的压缩c a c h e 技术引入的几个问题 1 2 1 几个相关术语 兹镭醐就是把输入数据( 源流或原始数据) 转变为另一种占用空间较少 的数据( 输出流或压缩数据) 的过程。 压鳓嬲数据压缩过程需要提供一个从原始数据到压缩数据的映射关系， 这种映射关系称为压缩编码。因此数据的压缩过程又称为数据的编码过程，从压 缩数据还原到原始数据也需要利用压缩编码对压缩数据进行反向映射，故解压缩 过程又称为解码过程。 压旃密在本文中，压缩率被定义为原始数据大小与压缩数据大小的比值。 因此，压缩率越大，则数据的压缩效果就越好。 勖幽p 织在传统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 行仍是指数据 未被压缩前，一个c a c h e 行的数据所代表的信息单位。 荐黼主存页面中的数据行，它所代表的信息单位与c a c h e 行相同。 q 幽p 子赞：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 行作为压缩粒度，而有些压缩主存系统则往往以一个主存页面作为压缩 粒度。 1 2 2 面向性能优化的压缩c a c h e 技术引入的几个问题 性能一直是微处理器体系结构设计者追求的一个主要目标，而处理器的访存 性能是影响处理器性能的一个重要因素。近年来，有很多研究组开始研究片内c a c h e 与主存的存储压缩系统来缓解处理器、主存以及硬盘【2 5 l 之间巨大的性能差异所带 来的负面影响，提高存储系统的性能或者降低存储系统的能量消耗瞄】。利用压缩 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 替换行为复杂化等。 1 2 2 1 存储访问命中延迟增加 由于处理器在进行计算时使用的是非压缩的原始数据，因此它在访问压缩 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 命中延迟增加带来的开 销时，系统的实际性能会下降。为此，我们需要谨慎分析并评估压缩技术的各环 节对于存储系统性能的影响。 压缩存储系统中数据的解压缩延迟开销分为两个部分：一部分是压缩数据的 寻址延迟，寻址延迟开销的大小与压缩存储系统中数据的存放布局方式紧密相关。 由于数据的可压缩性能不是固定的，相同尺寸的不同原始数据在压缩后将占用不 同大小的存储空间，这必然导致压缩存储系统中数据存放的实际物理地址与传统 存储系统中数据存放的物理地址有很大的差异，从而使压缩数据无法像传统存储 系统中那样可以进行直接地随机寻址。因此，对比传统的存储系统，压缩存储系 统的数据寻址过程有额外的延迟开销，这部分额外的寻址延迟开销成为解压缩延 迟的一个重要组成部分。解压缩延迟的另外一部分开销是对已寻址的压缩数据进 第5 页 国防科学技术大学研究生院博士学位论文 行解压缩操作的延迟，解压缩操作延迟开销的大小与压缩算法的压缩编码复杂程 度以及压缩粒度有关。一般来讲，压缩粒度越大，压缩编码算法越复杂，则解压 缩操作的延迟就越大。 因此，为减少压缩c a c h e 中存储访问的命中延迟，降低数据的解压缩延迟开销， 需要对压缩数据的存放进行合理布局，以简化寻址；同时尽可能采用简单的压缩 编码算法，合理确定压缩粒度，以加速解码过程。 1 2 2 2 存储管理的元数据开销增加 在存储系统中，用于管理数据的存储以及寻址访问所需要付出的各种硬件存 储单元的开销，我们称为元数据开销。例如，在传统c a c h e 结构中，t a g 阵列的开 销，就是一种元数据开销。与传统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 行进行寻址、访问并解压缩，压缩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 子块尺寸越小， 则每个物理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 子块中的内部碎片开销增加， 降低压缩技术的空间效率。图1 2 说明了当c a c h e 子块尺寸分别设定为c a c h e 行大 小的一半和1 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 设计时，