基于区域协作的Cache压缩①

曾 露 李 鹏 王焕东

(*计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190) (**中国科学院计算技术研究所 北京 100190) (***中国科学院大学 北京 100049) (****龙芯中科技术有限公司 北京 100190)



基于区域协作的Cache压缩①

曾 露②******李 鹏******王焕东****

(*计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190) (**中国科学院计算技术研究所 北京 100190) (***中国科学院大学 北京 100049) (****龙芯中科技术有限公司 北京 100190)

为提高Cache的有效容量，进行了Cache压缩研究，并提出了一种区域协作压缩(RCC)方法，以提升最后一级缓存的压缩率。与传统的Cache压缩算法不同，RCC方法利用了缓存区域的压缩局部性，使用缓存区域中第一个缓存块的字典信息来协作压缩缓存区域中的其他各个缓存块，而不需要对缓存区域进行整体压缩。RCC有效发掘了缓存区域内缓存块之间的数据冗余，实现了接近以缓存区域为压缩粒度的字典压缩的压缩率，然而压缩、解压缩延时却仍然和压缩单个缓存块时相当。实验结果表明，与单缓存块压缩算法C-PACK相比，RCC方法的压缩率平均提升了12.34%，系统的性能提升了5%。与2倍容量的非压缩Cache相比，有效容量提升了27%，系统性能提升了8.6%，而面积却减少了63.1%。

数据压缩， 字典压缩， 区域协作压缩(RCC)， 高速缓存压缩， 访存优化

0 引 言

长期以来，处理器运算性能的快速提高与访存带宽的缓慢增长之间一直存在着剪刀差，而且这种现象正愈演愈烈。计算性能与访存性能的不平衡导致了系统整体性能的下降，即使有强大的计算能力也没有办法高效利用，大量的时间被浪费在等待数据从存储系统中加载到流水线中。因此，大量的研究工作致力于访存系统的优化，提高访存的带宽，降低访存的延时。

由于半导体工艺的进步，片内可以集成更大的高速缓存(Cache)。增强动态随机存取存储器(eDRAM)技术的成熟使得动态随机存取存储器(DRAM)的高集成度技术被引用到Cache的设计中，进一步增加了Cache的容量。现代的计算机应用通常拥有超大的工作集，提供更大的Cache容量总是能够带来更好的程序运行性能。在体系结构层面上探索更高的Cache利用效率与半导体工艺追求更高的片内容量并不矛盾，反而两者相辅相成，共同为性能的提升做出贡献。然而Cache的设计面临着面积、功耗与延时之间的权衡取舍。通常接近处理器核访存部件的缓存需要更小的延时，从而减少流水线的空等待。为保证延时，其容量不能做到太大。而远离处理器核的缓存层次对访存延时较为不敏感，通常可以设计更大，然而更大的面积的Cache却面临着静态功耗和翻转功耗的问题。

数据压缩是降低数据存储空间的有效手段。而在片上Cache中利用数据压缩的技术理论上可以使得固定大小的Cache存储更多数据，即可以提升Cache的有效容量。已有研究表明，压缩缓存的逻辑容量可以达到其物理存储空间的一倍以上，而代价仅仅是略微增加了访问延时(主要是从压缩Cache中读取时解压缩的延时)和少量的tag位等元数据。由此可见压缩缓存的好处是显而易见的，尤其是对访问延时相对不敏感的最后一级缓存(Last Level Cache，LLC)，增加几个时钟周期的访问延时对于整个访存系统的性能影响很小。因此，大量的研究[1-5]通过实现高效管理压缩数据的Cache结构和适配于Cache的数据压缩/解压缩算法以实现更高的压缩率、更低的访问延时、功耗与面积开销以及更高的Cache性能。因此，数据压缩在提升Cache尤其是最后一级缓存(LLC)的有效容量，控制设计大容量Cache带来的功耗，最终有效提升系统性能上具有很大的意义。本文将探索在LLC中实现高效数据压缩的方法。

1 Cache压缩

1.1 Cache压缩的挑战

传统数据压缩算法经过几十年的研究，已经发展的较为成熟。诸如LZ77[6]算法以及在其基础上衍生的LZXX算法簇，和基于统计信息编码的Huffman算法在某些情形下甚至能够获得接近信息熵的压缩率。这些算法及其衍生算法被广泛应用于压缩软件中对计算机数据进行压缩，如DEFLATE。然而针对Cache数据的压缩，则面临与传统数据压缩不同的挑战。

首先，硬件实现压缩算法要在取得一定压缩率的同时，需要兼顾压缩算法的实现复杂度以及压缩、解压缩的速度。过于复杂的压缩算法的硬件实现成本和复杂度更高，且延时和面积开销甚至使得数据压缩得不偿失；而简单的算法虽然高效快速，但是压缩率通常较低。另外，缓存的读操作是访存的关键路径，解压缩延时对系统性能的影响大，因此压缩算法还需要具有较短的解压缩延时。

其次，压缩数据的存储结构不同。通常缓存都是多路组相联结构，连续的缓存块被映射到不同的组(set)，压缩算法的压缩粒度难以扩展到更大的数据范围，通常仅以缓存块为单位进行压缩。而软件压缩算法可以在一个较长的数据窗口中发掘冗余数据，甚至可以遍历数据来统计频率信息，使用占用空间最小的编码方式。

最后，缓存的数据是动态变化的，数据的修改需要将数据重新压缩。新数据与旧数据的压缩大小往往不同:如果压缩数据变小，Cache中会空出小块的存储空间，而它们往往不足以存储新的缓存块，这就导致了碎片化；如果压缩数据变大，还需要在组内额外分配空间，如果空间不足，还会导致缓存块的替换，进一步增加了设计的复杂度。

因此，Cache压缩需要综合考虑压缩率、解压缩延时、面积开销和实现复杂度等因素。仅侧重某一方面，而其他方面开销大，最终性能可能不好，甚至更差。

1.2 Cache压缩算法

传统数据压缩算法可以采用更大的数据块和更复杂的编码方法，而缓存压缩算法由于需要同时满足较低的硬件实现复杂度和较好的压缩率以及压缩、解压缩延时，因此，Cache压缩算法通常以缓存块为数据压缩单位，并对有限的常见数据模式进行编码。

零值在Cache中所占比例较大，在某些应用中，零值在Cache中甚至可以占到40%以上的空间。零内容增强高速缓存(ZCA)[7]使用一个额外的缓存记录Cache中为0的缓存块的地址，而不需要在Cache中存储零值，从而实现基本的压缩。然而，由于仅能够压缩零缓存块，ZCA受限于特定的应用，并不广泛适用。

然而，含有零值的缓存块仍广泛存在于Cache中，几乎所有的Cache压缩算法都会对零值进行优先压缩，使其占用最少的空间。

常见模式压缩(frequent pattern compression, FPC[8])将几种较为常见的模式进行定长编码，如连续的0、小值数据或重复值等共分为8类通过3bit的前缀来表示。据此将缓存行以数据字(32bit)为单位划分，依次根据对应的数据模式进行匹配压缩，生成相应的前缀和压缩数据。

C-PACK[2]算法(一种高性能微处理器高速缓存压缩算法)首先采用和常见模式压缩(FPC)类似的常见模式匹配，直接匹配压缩0值和小值数据。对于不能匹配的数据，引入了字典压缩。压缩时所有未匹配的数据将插入字典，后面的数据字除匹配0与小值数据外，同时与字典中的项进行匹配。字典项支持部分匹配，即匹配拥有相同高字节而低字节不同的数据，仅存储低字节不同的部分，从而实现相似数据的压缩。如表1所示，数据压缩以4字节为单位，除0、小值数据和无法压缩的情况为固定模式压缩，其他三项为字典匹配，分别表示完全匹配，匹配高两字节和匹配高三字节。由于字典的引入，大量相似的数据可以被压缩，依次可以实现不错的压缩率。C-PACK虽然增加了压缩、解压缩延时，但对于延时相对不敏感的最后一级缓存(LLC)，提高的数据压缩率相对带来的好处更大。

表1 C-PACK编码表

注： 压缩模式中每个字母代表一个字节，z表示为0，x表示当前字节未匹配，m表示当前字节匹配了字典项。压缩后大小为使用16项字典时的值。

BDI(Base-Delta-Immediate)压缩[3]认为，大量Cache行中的数据拥有低动态范围(low dynamic range)的数据特性，即数据字之间的差值通常比这些数据本身的值要小。BDI 为缓存块中固定大小(如2，4，8字节)的数据字确定公共基值，而数据字可由占用较小空间的偏移值来表示。缓存块的数据可以被压缩为一个公共基值和若干个数据字的偏移值的形式。BDI要求缓存块中所有数据字都必须压缩成相同大小的偏移值，因此在解压缩时所有的偏移值可以直接并行读取并与公共基值进行运算完成解压缩，可以实现2个时钟周期的解压缩延时。BDI的公共基值+偏移量的方式和C-PACK中字典项的部分匹配拥有一定相似性，不过由于BDI的基值数量固定，对于数值分散度较大的缓存块压缩效果较差，因此其压缩率不如C-PACK。BDI的一个改进策略是额外增加0作为公共基值，首先以0为基值计算偏移值优先过滤小值数据，再确定剩余数据字的公共基值进行压缩。

FVC (frequent value compression，常见值压缩)[5]通过预先计算出的常见值来配置常见值表。在程序执行的过程中，该字典的内容不变，对匹配的缓存数据进行压缩。FVC能够对程序执行过程中最常见的值进行压缩。然而，通常程序的执行随着时间的变化，存储在Cache中最多的值通常会发生变化，因此使用固定的值作为字典进行压缩不如动态字典的压缩效率高。

SC2(一个统计压缩缓存方案)[4]使用定期采样的统计信息进行Huffman编码来进行数据压缩。Huffman编码的生成需要对数据进行采样来生成统计信息，而由于缓存中的数据在程序执行时是动态变化的，该算法需要每隔一段时间定期对缓存数据进行重新采样，更新Huffman编码，使用新的编码进行数据压缩。SC2需要使用一块较大的RAM来存储采样的统计信息，在面积上不具有优势，但SC2能够实现较高的压缩率。因此，该方案在适用性上有较大限制，需要考虑到其实现的面积开销与复杂度。

常见的Cache设计中指令和数据在LLC中不加区分的存储，Cache并不记录某个地址是指令还是数据，并且有时指令还可以被当作数据动态地进行修改。然而指令和数据拥有不同的压缩特性。指令在编码时已经考虑到存储的效率，因此指令本身的信息熵已经很大，其压缩性不足。然而，处理器运行所需的指令类型在指令集中并非均匀分布，大多数时间仅运行了少数类型的指令，而这些指令在Cache中冗余度很高，对于其中出现频率较高的指令进行编码压缩，可以较好地压缩指令所需的存储空间。Benini等在文献[9]中探索了指令压缩的方法。

1.3 压缩Cache的结构

Cache压缩算法决定了数据最大可以被压缩的大小。而有效的压缩Cache结构为压缩算法实现数据压缩提供了基础。如果Cache组织不合理，要么限制了最大的压缩率，要么需要消耗大量的元数据(额外的压缩信息，用于索引压缩缓存子块的指针等)。因此，设计合理有效的压缩Cache结构才能配合Cache压缩算法实现高效快速的Cache压缩。

可压缩Cache的结构需要解决压缩缓存块的存储与索引、压缩缓存块的修改与替换和压缩策略的选择的问题，接下来将分别进行说明。

1.3.1 压缩缓存块的存储与索引

由于压缩后的缓存块大小不一，且压缩Cache的tag数量需要大于未压缩的数据块数量以存储压缩数据，传统Cache的tag与data一一映射的方式不适合压缩Cache。压缩Cache通常使用解耦(decoupled)方式进行tag与data的映射。

VSC[8]使用tag中的size字段来表示压缩的缓存块所占用的段(segment，4字节)数目。VSC的缓存块的偏移地址通过累加组内该缓存块之前所有缓存块的size字段得到。第k路缓存块的偏移地址为第1路至第k-1路缓存块的size字段的和：

(1)

缓存块的偏移和大小为offset(k)和size(k)。

SCC(skewed compressed cache, 偏移压缩缓存)[10]根据相邻数据的压缩率相近的特性，将连续地址的压缩数据块集中存储在一个物理缓存块中，使用一个tag来表示超级缓存块。根据缓存块压缩率的不同，tag可表示1,2,4,8个缓存块。然而，SCC针对大缓存块中压缩率不同的缓存块需要通过偏移映射的方式单独存储。SCC所需的元数据较少，不需要提供额外的tag，即可支持较高的压缩率。

Pair-matching[2]限制一个物理缓存块最多保存两个压缩缓存块，在tag与data之间维持了二对一的固定映射，避免了压缩缓存块的索引开销。然而，固定的映射决定了其理想情形下2倍压缩率的上限，而且两个压缩缓存块存储在一个物理块内的限制决定了它放弃了大量的压缩机会。

1.3.2 压缩缓存块的修改与替换

在系统运行过程中缓存块的内容会发生变化，而对修改数据进行重新压缩后的大小也会发生变化。如果变小，那么剩余出来的空间需要通过执行紧缩(compaction)或重映射来回收以避免浪费；如果变大，则需要占用额外的空闲空间，甚至可能需要替换掉现有的一个或多个缓存块。

Cache的紧缩需要读写组内大部分的数据，因此该操作代价巨大。即使该过程可以与读写关键路径并行，其巨大的功耗与复杂逻辑开销仍然使得代价过大。SCC和Pair-matching均对缓存块的大小有限制，不允许任意大小的缓存块，因此避免了复杂的紧缩操作。

压缩Cache的替换策略除考虑时间局部性因素外，还需要考虑缓存块自身的压缩大小，使用最少的替换次数满足插入缓存块的空间需求，以及考虑缓存的存储布局，选择合适的替换块避免碎片的产生导致需要紧缩。ECM(effective capacity maximizer)[11]提出了大小可感知的压缩缓存替换策略，同时利用最不常用(least recently used, LRU)信息和压缩信息大小决定替换策略，保留尽可能多并且被重复利用的缓存块，从而从另一个角度提升了系统的性能。

1.3.3 压缩策略的选择。

Cache压缩算法通常都不能普遍适用于所有情形。对于不同的应用，不同的数据类型以及不同的执行时间点，数据的压缩特性都有不同。有些应用的工作集较小，数据压缩带来的额外空间没有意义，反而产生了额外的延时，Alaa[8]提出了动态方式判断应用是否得益于压缩来决定是否压缩数据。Nitta[12]根据缓存行中超过50%数据的数据类型选择是否压缩、如何压缩，如针对整形、浮点和指针类型，采用不同的压缩算法。

2 区域协作压缩

2.1 Cache压缩的粒度对压缩率的影响

尽管固定大小的缓存块可以使得Cache管理相对简单而且高效，使用更大粒度的缓存数据进行压缩通常可以获得更高的压缩率。应用程序在访存中大多呈现较强的空间局部，即地址相近的数据总会被相继访问。尤其是具有流式访存行为的应用(如applu, equake, ocean, radiosity, raytrace等)，它们会连续访问大片的数据，且由于程序特性，连续访问的相邻数据拥有相似的特性，如拥有相同的高字节，而仅仅是低字节不同，或者是完全相同的数据。这类数据通常不仅仅存在于一个缓存行内部，而通常存在于多个缓存块范围，从而产生了区域压缩(region compression)的概念。

图1 C-PACK压缩算法在块粒度和区域粒度下压缩率对比

如图 1所示，以C-PACK压缩算法为基础，分别为使用缓存块为粒度进行压缩(C-PACK Blk)，使用16路组相联的组为粒度进行压缩(C-PACK Set)和使用16个连续地址的缓存区域进行压缩(C-PACK Reg)在各个应用程序下压缩率的对比。可以观察到C-PACK Reg方式对压缩率有较大的提升，最高可达21%，平均也有17.96%的压缩率提升；而同样为16个缓存块为粒度的C-PACK Set方式则提升很小，平均在5%以下。

因此，对更大的数据块进行压缩，可以获得比单独压缩一个缓存块更好的压缩性，特别是使用连续地址进行压缩，比在一个组内相对随意地址的多个缓存块压缩，具有更高的压缩率，从而反映了数据压缩的局部特性。本文认为，数据压缩局部性是除时间局部性、空间局部性之外，访存系统特别是可压缩访存系统需要深入挖掘的第三种局部性。

然而，现有的Cache压缩算法大都使用缓存行为单位进行数据压缩，因为这样可以在不改变现有Cache架构的情形下实现数据压缩，而不引入额外的复杂性。在类似常见模式压缩(FPC)这种固定模式的压缩算法下，不同的压缩数据的粒度对压缩率没有影响；而在基于字典的压缩算法(如C-PACK, BDI)中，被压缩的数据粒度越大，可以发掘的数据冗余越多。而基于单一缓存行的压缩算法不能有效压缩跨多个缓存行的冗余数据，需要在每个缓存行中单独进行存储字典项，从而造成了Cache空间的浪费。

利用数据压缩局部性压缩多个连续缓存块可以提升可压缩Cache的压缩率，然而该技术面临如下挑战：

首先，由于缓存行中替换和修改数据块是比较频繁的，且替换和修改需要对数据重新进行压缩、解压缩。如果以较大的数据块为单位进行整体压缩和解压缩，其代价显然过大，在结构设计中应当避免。Cache的压缩和解压缩多个缓存行会带来较大功耗与延时开销，然而可以借助其他缓存块的压缩信息以协助当前缓存行的压缩和解压缩。

其次，连续缓存块通常被映射到不同的set，通常难以通过一次访问获取多个连续的缓存块数据或者压缩信息。在设计中应综合考虑压缩性与延时的平衡：获取更多连续缓存块的信息可以实现更高的压缩率，然而需要更多的访问延时。需要在保证一定压缩率的提升下尽量减少对其他缓存块的访问。

2.2 区域协作的压缩算法

本文提出了一种区域协作压缩(region cooperative compression, RCC)算法，该算法利用了缓存的数据压缩局部性，可以以较小的代价获得比以缓存块粒度进行字典压缩更高的压缩率。

区域协作压缩(RCC)的原理是利用缓存区域内第一个缓存块(first block in region, FBR)压缩时所生成的字典项来协助压缩区域内后续缓存块(successive block in region, SBR)的数据，由于缓存的压缩局部性，该方法可以近似达到对整个缓存区域共同使用一个字典进行压缩的压缩率。

RCC同时兼顾了延时、功耗与压缩率。首先，缓存块的压缩、解压缩仅针对当前命中的缓存块，不会修改组内的其他缓存块，而需要额外读取的FBR字典项可以通过多路命中的方式覆盖延时，因此延时并没有增加；其次，缓存块在压缩、解压缩时仅额外读取了FBR的字典项，带来少量的功耗开销；最后，由于FBR的协作压缩，SBR能够利用FBR字典项进行压缩，其压缩率可以更高。

2.2.1 压缩

RCC过程以C-PACK算法为基础，所不同的是在压缩FBR和SBR时对字典的不同处理过程。

FBR的压缩是一个独立的过程，和C-PACK一样，根据读取到的数据字生成字典进行后续数据字的压缩。FBR作为协作者，如果插入Cache时已有该缓存区域中的其他块存在，则SBR的压缩有所不同，在压缩前如果在Cache中存在FBR，则需要将FBR的字典项读取到压缩器的字典中。如图 2所示，在执行压缩时，若存在FBR，其字典项会被读取到字典中。如果命中，则直接使用该字典项进行压缩；如果没有命中，处理方式与C-PACK相同。

图2 RCC器的字典

由于FBR的字典项需要在SBR压缩时使用，FBR的压缩方式与SBR有所不同。FBR的压缩仅针对自身，不需要从其他缓存块读取字典项。然而，由于FBR需要在SBR进行压缩时被快速访问，因此，FBR在压缩时，选择字典中计数器值最大的两个字典项放置在数据块的头部，在读取SBR字典时，仅读取数据头的8个字节作为SBR字典项。

2.2.2 解压缩

解压缩的过程与C-PACK相同，只是在为SBR进行解压缩前需要读取FBR的字典项。然而，如果该过程顺序执行，将增加额外的延时。解压缩过程是访存的关键路径，解压缩延时将直接影响Cache的访问延时，从而影响性能。为此，当读取SBR时，FBR字典项的读取需要与SBR同步进行以避免增加额外的延时。

为实现SBR与FBR的压缩信息同步读取，消除额外的等待延时，需要Cache支持多路命中机制。多路命中的意思是在Cache访问SBR时，同时命中FBR(若存在)，使得两者的读取可以同步进行。由于cache的每一路都是独立的RAM，在访问Cache时，可以使得部分路访问SBR所映射组的索引，另一部分路访问FBR所映射组的索引。通过在分配时通过地址哈希函数确定FBR和SBR各自允许存放的路数，使得不同缓存区域的FBR和SBR的路映射不同，从而在整个Cache范围内消除了路限制带来的潜在冲突。映射为FBR的路的tag与FBR的tag比较，映射为SBR的路与SBR的tag比较，最终根据各自的命中情况读取FBR的压缩信息和SBR的数据。

定义W={w1, w2, …, wn}为所有路的集合，WFBR和WSBR分别表示FBR和SBR的候选可分配的way，且定义wk=wk-1+1, w1=wn+1。那么有：

WFBR={w1+h, w2+h,…,wn/2+h}

(2)

其中h=hash(addr[39:10])且0

WSBR=W-WFBR

(3)

WFBR和WSBR的值根据地址10-40位的哈希运算得到，因此不同缓存区域，FBR和SBR所能分配的候选路不同。而在命中查找时，根据hash运算得到相应的WFBR和WSBR，然后再根据FBR和SBR的索引分别对WFBR和WSBR的路进行访问，即可实现一次访问，同时命中FBR和SBR。

2.3 Cache组织结构

RCC采用基于VSC[8]的压缩Cache结构，tag的数量为data的4倍，以最高支持4倍压缩率。

图3所示为RCC的tag字段。addr标识缓存块地址，可据此判断该块是FBR还是SBR；state记录缓存块的状态和一致性信息；LRU保存访问历史以实现LRU替换算法；size是该缓存块被压缩的大小，以segment为单位，所在块的偏移通过将其之前所有块的size相加得到。

图3 RCC的tag字段

对于拥有8个64字节缓存块的组，由于提供了4倍的tag，每个组有32个tag用来保存压缩块的信息。由于RCC使用了多路命中的机制，FBR仅会在其中16个tag中进行查找，SBR则会在另外16个tag中进行查找。多路命中技术对两个地址分别进行16路的全相联比较，而不是各自进行32项的全相联比较，从而避免了额外的延时和功耗开销。

由于SBR的压缩利用了FBR的字典项，如果FBR发生替换，所有使用FBR字典项压缩的SBR都需要进行压缩数据的恢复，而恢复的代价很大。RCC通过以下3种途径解决该问题：

(1) 采用修改的LRU算法，发生替换时如果LRU队尾是FBR，则向LRU队列前面查找，直到找到非FBR为止。如果不存在非FBR的缓存块，在FBR的tag中记录了被SBR使用的次数(usage count，UC，如图 3)，优先选择UC为0的FBR进行替换。

(2) FBR被充分哈希到不同的组，采用如下映射方式：index =hash(addr[39:10]) + addr[9:6]，使得不同缓存区域的FBR均等的映射到所有的组中，且相同缓存区域内的块被映射到不同的组。

(3) 将被替换的FBR插入victim buffer，直到SBR依次被替换，UC降为0后FBR才被替换。

2.4 存储开销

表2列出了RCC, C-PACK, 2X Base与Base存储空间需求比较结果。RCC在比Base多22.6%的面积开销，对于4MB的Cache，RCC需要多消耗992kB的存储空间，以实现大于2倍的压缩率。不过，相比2X Base，RCC的面积开销大大降低，减少了63.1%。

表2 RCC, C-PACK, 2X Base与Base存储空间需求比较 (Base为4MB存储，8路组相联，64B缓存块)

3 实验数据

3.1 实验平台

本文采用MIT大学发布的Graphite分布式多核模拟器[13]，Graphite可以直接在主机上运行被模拟的程序，基于动态插桩的方式获取执行过程中的信息，模拟目标结构的运行机制，从而获取性能等参数。该模拟器的特性是系统开销小，可并行模拟多核结构，速度较快，但是由于它不是时钟精确类型的模拟器，对于模拟要求具有精确时钟信息的结构如流水线结构模拟准确性较差。然而该模拟器提供了完整的多处理器多路组相联Cache的行为模型和一致性模型，支持对压缩Cache的行为进行建模，因此该模拟器能够满足本文的实验要求。

本文主要研究数据压缩在LLC中的运用，以提升缓存的有效大小，从而降低其失效率最终实现性能的提升。而处理器核的微结构以及缓存一致性协议则不在考察的范围内，因此相关参数仅采用比较常用的设计参数。具体的配置如表3所示。

表3 目标系统的参数配置

3.2 压缩率

如图4所示，与C-PACK相比，RCC压缩率有较大提升。如radiosity, lu_non_contiguous, water-nsquared的压缩率提升超过了13%，对于所有测试程序，压缩率平均提升了12.34%，压缩率从2.2倍提升到2.54倍。实验结果说明了RCC对压缩率的提升是拥有普遍好处的，这是由Cache的空间局部性与压缩局部性决定的。虽然Cache仍然使用缓存块为粒度进行存储和压缩，但是其压缩率已经接近直接对缓存区域进行压缩，而代价仅仅是每次访问需要同时多读一个tag和FBR的字典项。

图4 RCC与C-PACK压缩率实验结果对比

3.3 性能分析

与C-PACK相比，RCC需要在压缩SBR时同时读取FBR的字典项来协作压缩，如果该过程串行，至少需要增加2拍延时(SBR需要等待FBR命中和字典项的读取)，而多路命中很好地并行化了该过程。任意SBR可以和FBR同时被命中，FBR字典项的读取延时刚好被SBR的读取延时覆盖，SBR在压缩、解压缩时，FBR的字典项已经在字典中就绪。因此，RCC的延时与C-PACK相同。而且，实验结果表明，RCC的缺失率相比C-PACK更低，这是由于Cache中存储了更多数据，有用数据被替换的概率降低。如图5所示均一化的IPC数据，RCC相比Base均有10%～30%不等的性能提升，而与2X Base相比，barnes, cholesky, ocean, radiosity, radix, raytrace, volrend等程序均有5%～13%不等的性能提升，而fft, lu, water等程序则有3%左右的性能下降，这是由于程序压缩率的不同导致。压缩率高的程序能带来更低的缺失率，从而从整体上增加IPC；而压缩率较低的程序对数据压缩不敏感，反而由于解压缩等带来的开销降低了系统性能。这种问题可以通过动态关闭数据压缩来解决，且与本文的方案相容，可以共同提升系统的整体性能。

图5 RCC, C-PACK, Base和2X Base的均一化IPC数据

4 结 论

本文总结了目前压缩缓存的结构与算法研究进展，并基于数据在缓存中呈现的压缩局部特性，提出了区域协作的Cache压缩。相比C-PACK压缩，RCC有明显的压缩率提升，同时没有带来额外的延时，因而带来了近乎“免费”的性能提升。另外，RCC对于所有基于字典的Cache压缩算法和结构都具有适应性，而不仅限于特定的结构和算法。

未来的工作包括进一步的发掘数据压缩的粒度，与虚拟内存的特性结合，在页内寻找压缩的可能性；对缓存数据进行分类，对指令、浮点数据这类数据使用专用的压缩算法；以及在保证压缩率的同时，探索进一步降低解压缩延时的方法。

[1] Alaa R A, David A W. Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches. In: Technical Report 1500, Computer Sciences Department, UW-Madison, 2004

[2] Chen X, Yang L, Dick R P, et al. C-pack: A high-performance microprocessor cache compression algorithm.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems, 2010, 18(8): 1196-1208

[3] Pekhimenko G, Seshadri V, Mutlu O, et al. Base-delta-immediate compression: practical data compression for on-chip caches. In: Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques, Minneapolis, USA, 2012. 377-388

[4] Arelakis A, Stenstrom P. SC2: A statistical compression cache scheme. In: Proceedings of the 41st Annual International Symposium on Computer Architecuture, Minneapolis, USA, 2014. 145-156

[5] Yang J, Zhang Y, Gupta R. Frequent value compression in data caches. In: Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture, Monterey, USA, 2000. 258-265

[6] Ziv J, Lempel A. A universal algorithm for sequential data compression.IEEETransactionsoninformationtheory, 1977, 23(3): 337-343

[7] Dusser J, Piquet T, Seznec A. Zero-content augmented caches. In: Proceedings of the 23rd International Conference on Supercomputing, Yorktown, Heights, USA, 2009. 46-55

[8] Alaa R A, David A W. Adaptive cache compression for high-performance processors. In: Proceedings of the 31st Annual International Symposium on Computer Architecture, Munich, Germany, 2004. 212-223

[9] Benini L, Macii A, Macii E, et al. Selective instruction compression for memory energy reduction in embedded systems. In: Proceedings of the 1999 International Symposium on Low Power Electronics and Design, San Diego, USA, 1999. 206-211

[10] Sardashti S, Seznec A, Wood D. Skewed compressed caches. In: Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, Cambridge, UK, 2014. 331-342

[11] Baek S, Lee H G, Nicopoulos C, et al. ECM: Effective capacity maximizer for high-performance compressed caching. In: Proceedings of the IEEE 19th International Symposium on High Performance Computer Architecture, Shenzhen, China, 2013. 131-142

[12] Nitta C, Farrens M. Techniques for increasing effective data bandwidth. In: Proceedings of the IEEE International Conference on Computer Design, Lake Tahoe, USA, 2008. 514-519

[13] Miller J E, Kasture H, Kurian G, et al. Graphite: A distributed parallel simulator for multicores. In: Proceedings of the IEEE 16th International Symposium on High Performance Computer Architecture, Bangarlore, India, 2010. 1-12

The Cache compression based on region cooperation

Zeng Lu******, Li Peng******, Wang Huandong****

(*State Key Laboratory of Computer Architecture(Institute of Computing Technology,Chinese Academy of Science), Beijing 100190) (**Institute of Computing Technology, Chinese Academy of Science, Beijing 100190) (***University of Chinese Academy of Science, Beijing 100049) (****Loongson Technology Corporation Limited, Beijing 100190)

The Cache compression was studied to increase Cache’s effective capacity, and a region cooperative compression (RCC) algorithm was proposed to improve the compression ratio of the last level Cache. Different to traditional Cache compression algorithms, the RCC algorithm exploits the compression locality to compress Cache blocks in a Cache region by the cooperation of the first block in the region, instead of compressing the whole Cache region. RCC effectively explores the duplications across the Cache blocks in a Cache region and shows a comparable compression ratio with dictionary compression approaches with the whole Cache region as the compression granularity, whereas the (de)compression latency is not increased. The experimental results show that RCC provides the better average compression ratio than the compression algorithm of C-PACK by 12.34%, which causes the performance improvement of 5%. Compared to the non-compressive Cache with double size, the effective capacity increases by 27%, the performance increases by 8.6% and the area decreases by 63.1%.

data compression, dictionary compression, region cooperative compression (RCC), Cache compression, memory access optimization

10.3772/j.issn.1002-0470.2016.05.003

①国家“核高基”科技重大专项课题(2014ZX01020201, 2014ZX01030101)，国家自然科学基金(61232009, 61432016)和863计划(2013AA014301)资助项目。

2016-01-18)

②男，1987年生，博士生；研究方向：计算机系统结构；联系人，E-mail: zenglu@ict.ac.cn