一种面向包含式缓存的共享末级缓存管理策略

娄冕， 肖建青， 张洵颖， 吴龙胜， 关刚强

(1.西安微电子技术研究所， 陕西，西安 710075；2.国防科技大学 电子科学与工程学院， 湖南，长沙 410073)



一种面向包含式缓存的共享末级缓存管理策略

娄冕1， 肖建青1， 张洵颖1， 吴龙胜1， 关刚强2

(1.西安微电子技术研究所， 陕西，西安 710075；2.国防科技大学 电子科学与工程学院， 湖南，长沙 410073)

针对传统LRU替换策略无法感知包含式缓存时间局部性的问题，提出一种适用于包含式缓存的共享末级缓存(SLLC)管理策略. 通过提前将无用数据存储于一个开销较小的旁路缓存，可以避免其与复用频率较高数据对SLLC的资源竞争，同时维护了包含属性. 为进一步寻找复用性最低的数据作为替换对象，构建一种局部性检测电路，有助于将此类数据尽早驱逐出SLLC，文中提出一种统一的管理算法，受益于两种预测器的相互校准，从而达到无用块旁路和低重用块替换的目的. 实验结果表明，所提策略将SLLC缺失率平均降低21.67%，预测精度提升至72%，而硬件开销不到SLLC的1%.

包含式缓存；管理策略；共享末级缓存；多核

现今，航天及空间应用领域明确提出未来片上多核处理器必须具备在辐照环境下较强的生存能力，而包含式(inclusive)共享末级缓存(shared last-level cache， SLLC)凭借其系统级的冗余特性以及对访问延迟的不敏感性[1]，可以与差错控制编码自然结合，因而有效提高了多核处理器的可靠性.然而，包含式缓存存在强制维护缓存层次间包含属性的局限性，以致缓存系统出现严重的抖动现象[2]，使得原本在非包含体系下众多行之有效的缓存优化策略难以为继.

分配策略和替换策略作为缓存设计优化领域的两大研究热点，其目的在于识别无用的缓存数据以及替换局部性较低的缓存数据.基于此，设计将着力解决旁路策略与包含式缓存的融合、替换策略对不同层次缓存数据局部性的预测、以及两种策略的相互校准与协同管理等问题，以求通过较小的硬件开销获得较高的性能提升.

1 动机与背景

1.1 动 机

多级缓存架构类型分为包含式、非包含式(non-inclusive)和独占式(exclusive)[3].相对于其它两种结构，包含式缓存并不具备容量优势，但却能够简化缓存一致性设计并提供天然的错误容忍性，因而广泛用于CMP系统[4-5].然而，包含式缓存同样存在性能瓶颈，其并非实际可用缓存容量的减少，而是由于SLLC的包含属性对于高层缓存时间局部性的干扰，使得高层缓存命中率较高的数据块反而成为SLLC的候选替换块[6].

为寻求有效的包含式缓存管理策略，本文将SLLC中数据块分为3类：① TLH-H块：在一级缓存中具有较高时间局部性特征的块；② TLH-L块：在SLLC中具有较高时间局部性特征的块；③ TLH-N块：在两级缓存中均具有较低时间局部性特征的块.

图1是本文实验所用测试负载在LRU管理的包含式SLLC中，不同类别数据块的分布情况.可以看出，大约75.03%和14.12%的数据块是两类具有较好局部性特征的TLH-H和TLH-L块，剩余11.58%的块直至在一级缓存中替换也未被再次访问，这类块即为TLH-N块，成为本文重点优化的对象.

1.2 相关工作

当前，围绕包含式SLLC性能优化的工作集中在分配策略和替换策略设计实现上.分配策略中最具代表性的是旁路算法[7]，它可以将使用频率较低的数据直接旁路到上级缓存，从而减少与SLLC有用数据的竞争.然而，这类算法要求缺失数据不能分配到SLLC中，因此并不适用于包含式缓存.适用于包含式缓存的旁路算法BBA是在最近的文献[8]中提出，然而它仅能与LRU替换策略配合使用，使得SLLC无法通过正确感知高层缓存的局部性而减少SLLC的抖动.

替换策略目的是替换复用性最低的数据块.文献[9]中提出一种基于二叉树的伪LRU替换策略，它通过穷举算法搜索整个矢量空间，从而确定每路数据在叶子节点的替换顺序；然而该算法需要预先对目标程序集进行行为感知，因而可操作性低.文献[10]中通过在SLLC替换时预先失效一个上级缓存块，并在时间窗内判断其是否活跃来感知时间局部性，然而该技术仍旧基于LRU优先排序，无法摆脱上级缓存对局部性的过滤效应.Tian和Khan等[11]对每个SLLC请求数据的历史局部性信息进行统计，提出了能够感知两级缓存局部性特征的TMC算法，但它要求缺失块插入SLLC，从而导致一个潜在的活跃数据块被强制反向无效.

2 包含式SLLC管理策略

2.1 旁路策略

为了能够在数据插入到SLLC之前确定缺失块的使用频率，本文提出了适用于包含式SLLC的旁路概率预测器BPP，如图2所示.

BPP基于历史数据生命周期的概率统计对SLLC缺失数据进行预测，如果认定其相对SLLC内数据具有较低的重用性，则暂存于旁路缓存(bypass buffer，BB)中；否则替换插入SLLC.当BB中的旁路数据被替换时，上级缓存的副本同时被无效，以维护包含性.为了有效追踪并动态调整旁路算法的精度，SLLC的每个Cache行均可映射至BB的一个表项.该表项位域分为7段：valid表示该表项是否有效，virtual bypass表示该表项是否为虚拟旁路，competitor pointer指向原始替换块位置，BB-tag存储被旁路(或虚拟旁路)数据的tag信息，segment和inclusive分别指示该表项映射至SLLC的区域段号和该旁路块的包含性.

当一个数据被转存至BB时，对应的竞争者指针将指向替换算法原本选择的路号. 之后若竞争块先于旁路块被访问，意味着旁路块为TLH-N块，旁路有效且旁路概率增加，反之无效且旁路概率降低. 为了逆向评估旁路算法的有效性，一些新分配的块被随机地进行虚拟旁路. 在这种情况下，旁路块与竞争块进行位置调换，同时置virtual bypass有效，而旁路概率的调整则与前者相反.

为了减少BB的硬件开销，BPP并不增加旁路块的数据段，这是由于性能稳定后的旁路算法能够较准确的预测寿命短的BB块. 为进一步减少开销，本文采用文献[8]对典型负载的剖析结果，即set数为16的4路相联结构就能保证足够的精度. 此外，为了直接判定SLLC命中块是否在BB中被指向，所提算法增设了7位segment段，从而以set为单位将SLLC按照BB大小虚拟重映射为27个分区. 这样当SLLC某一分区命中时，BB将在对应行中搜索segment段匹配的旁路块，若竞争者指针的指向匹配，则证明旁路有效且旁路概率提升. 本方案还为BB表项增设inclusive位，目的是使得BB同样具有简化一致性设计和容错的能力.

2.2 替换机制

旁路算法虽有较高的预测性能，仍无法过滤所有TLH-N块.本文提出的包含式缓存替换策略能够对插入的数据块进行二次识别，从而过滤出TLH-N块作为候选替换者.

该策略第一步需要在SLLC层面分离出TLH-L块. 根据文献[12]中的观察：基于已执行程序的部分PC可以动态预测所要发生的事件，且不同缓存分区所对应的访存行为大致相同. 这意味着，相同的PC可能对应类别相同的数据块. 因此，本文使用图3所示的局部性检测电路，主要包括预测表和采样集两部分结构. 预测表由一组饱和计数器阵列构成，通过哈希后的PC索引计数值，以此在TLH-L和非TLH-L(即为TLH-H与TLH-N，简记为TLH-P)中确定访问块的类型. 采样集通过追踪一小部分SLLC块的使用情况来更新预测表，每个采样块内容包括部分tag、部分PC以及块类型. 若访问与采样集中tag匹配，则使用采样块关联PC以及程序PC分别检索预测表，前者用以自减预测计数值，后者用于重新对采样块分类. 若采样集缺失，需按照TLH-N、TLH-P、伪LRU的顺序选择替换块，并同样检索两次预测表，但需要自增计数值. 类似的，SLLC块使用哈希后的程序PC检索预测表，并在TLH-L和TLH-P中选择对应的分类.

第二步需要从TLH-P块中进一步分离出TLH-N块. 当SLLC发生替换时，算法将按照TLH-N、TLH-P、伪LRU的顺序选择候选替换者，同时额外选择同行中一个TLH-P块提前进行反向无效. 若处理器立即发起对其访问，则其为TLH-H块，否则为TLH-N块. 与文献[10]中策略不同的是，考虑到LRU算法已经不能有效识别SLLC的局部性特征，本文将使用硬件开销更小的伪LRU算法作为备用算法，使得资源消耗下降76.6%.

此外，图3中的旁路块地址恢复机制，根据旁路命中块中存储的tag段和segment段，配合当前地址的sub-index段，可还原旁路块地址以检索采样集，使得旁路算法能够指导替换算法进一步提高预测精度.

2.3 管理算法

本文进一步挖掘了所提局部性预测器和旁路概率预测器相互校准的能力，提出了管理算法如下.

1.若访问SLLC的Cache块x命中：

使用x.hashedPC索引预测表PTable，并更新x.type；

若x被BB中旁路块y指向：

if BB(y).vb=0

PBB++;

else

PBB--;

2.若访问SLLC的Cache块x缺失：

2a.若x在BB中命中：

if BB(x).vb = 0

PBB- - ;

else

PBB++;

2b.若额外向L1 Cache无效的TLH-P块z被再次访问：

z.type= TLH-H;

若z被BB中旁路块y指向:

if BB(y).vb = 0

PBB++;

else

PBB- -;

2c.若额外向L1 cache无效的TLH-P块z没有再次被访问：

z.type=TLH-L;

若z被BB中旁路块y指向：

if BB(y).vb = 0

PBB- -;

else

PBB++;

3.若x在LLC命中时在BB中有旁路块指向，且还原后的

该旁路块地址与采样集中块k命中：

使用k.storedPC索引PTable，并得到索引值Creplace：

k.set.type=TLH-L;

Creplace++;

两种算法的相互校准发生在3种情况：

① SLLC或BB命中. 当SLLC命中，根据命中块所处虚拟分区位置与BB表项中的各segment段进行对比，确认该块是否被BB指向. 若被真实指向，说明旁路算法有效且旁路概率自增；若被虚拟指向，说明旁路算法失效，旁路概率自减. 当BB命中时，旁路概率的调整方向则与SLLC命中时相反(参见算法1和2a).

② TLH-P块的2次分类. TLH-P块的预先无效不仅可以动态调整替换算法的精度，也可提高旁路算法的精度. 如果该块被二次确认为TLH-H块，并且被一个旁路块真实指向，那么将证明旁路有效且提高旁路概率，虚拟旁路则降低旁路概率；若为TLH-N块，则旁路概率的调整方向相反(参见算法2b和2c).

③ 采样集的更新. 旁路算法的预测结果同样可以提高采样集的预测精度. 如果SLLC中命中数据被旁路块指向，则该旁路块为TLH-N. 利用图3的旁路块地址恢复机制，可还原该旁路块的地址并对采样集进行虚拟查询. 如果该地址在采样集中命中，则可按照TLH-N块对采样集和预测表进行更新(参见算法3).

3 性能评价方法

3.1 配 置

本文使用基于Simics[13]的全系统模拟平台模拟UltraSPARC结构的4核处理器. 每个处理器都有独立的一级指令Cache和数据Cache，片上的4个核共享二级Cache. 仿真系统的配置如下. 片上核数为4；主频为1.2 GHz；微结构为顺序结构，每条指令的执行时间为1周期.① 一级指令和数据Cache:私有；指令Cache 32 kB，4路组相联，块大小16字节；数据Cache 16 kB，4路组相联，块大小16字节，写直达；均采用LRU替换策略，访问命中开销为1个周期.② 二级Cache:共享；2 MB混合结构，16路组相联，块大小32字节；访问命中为20个周期；两级缓存采用包含性策略，写直达.③ 主存:数据宽度8字节，大小1 GB，访问延迟100个周期.系统的其他配置采用模拟器的默认配置.

3.2 测试负载

本文采用由SPEC 2006与SPEC 2000中部分应用组合而成的多道负载来评测所提管理策略的性能. 根据应用程序在两级缓存缺失率的高低程度，本文进行如下分类：① 私有缓存密集型：在私有缓存中缺失率较低的应用，包括deal2，h264ref，perlbench，povray，sjeng；② 共享缓存密集型：在共享缓存中缺失率较低的应用，包括astar，bzip2，calculix，vortex，xalancbmk；③ 非存储密集型：在共享缓存中缺失率较高的应用，包括gobmk，art，mcf，equake，ammp. 这其中，测试程序ammp，mcf，art，equake，vortex的旁路块比例较高. 表1列出了本文所使用的全部负载组合.

表1 4核多道程序测试程序集

4 实验结果及分析

4.1 SLLC缺失率

图4给出了在包含式体系下TMC、BBA、本文所提策略(记为HMP)以及非包含式体系下LRU策略各自产生的SLLC缺失率，所有数据均以包含式缓存下LRU策略作为基准.

结果显示，旁路策略BBA在mix04与mix07的效果优于替换策略TMC，这是因为它们均不包含非存储密集型程序，但因拥有旁路概率较大的mcf和vortex，使得旁路操作多于替换操作. 相比之下，mix03不包含旁路概率较大的程序，因此旁路效果与非包含式结构差距不大. 所有程序集中，mix01使用TMC与BBA效果差距不大，这是因为虽然含有旁路概率较大的程序art与ammp，但其中ammp数据的复用距离较大，使得容量有限的旁路缓存难以发挥作用. 相对于TMC和BBA，HMP策略明显优于包含式LRU策略，其SLLC平均缺失率降低21.67%；同时与TMC和BBA策略相比， SLLC缺失率平均降低7.40%和3.75%. 这种性能的提升不仅源自HMP对两种技术的综合运用，也得益于其对两种技术互补性的挖掘.

4.2 预测精度分析

HMP算法的有效实施依赖于其对旁路块和替换块的预测精度. 图5给出了HMP算法对于表1中所有多道程序负载的预测分析. 从图中可以看出，替换块和旁路块的平均预测精度分别高达72%和60%. 算法之所以具有较高的预测精度，一方面是因为旁路策略增加了虚拟旁路的假设，而替换算法使用数据块地址和导致数据失效的指令PC来定位TLH-N型数据；另一方面则是HMP算法增加了两种策略的相互学习，进一步提高各自的预测精度. 这其中，替换块的预测精度略高的原因在于，进入Cache的数据块已经经过了旁路策略的初步筛选，从而降低了无用块对采样集和预测表性能的干扰.

4.3 硬件开销

HMP策略的存储开销主要来源于3方面：SLLC各Cache块的局部性分类标识；旁路缓存；采样集和预测表.

表2给出了HMP策略的存储开销，仅有14.51 kB，不到SLLC面积的1%.

由表2可知，SLLC增加的分类标识占整个额外开销的55%，这反映出以SLLC缓存块为单位进行优化将产生较大的开销. 相反地，旁路缓存采用行数为16的4路相联结构，而采样集采用行数为64的12路相联结构，预测表为3套4 096个两位计数器，这些开销较小的辅助结构均不受SLLC容量影响，因而适用于对开销和可靠性要求较高的空间处理器.

表2 HMP策略硬件电路的存储开销

5 结 论

包含式缓存有助于简化多核处理器一致性设计复杂度和提高可靠性，但相关的管理策略却依旧存在性能瓶颈. 本文提出的SLLC管理策略，围绕分配策略和替换策略两方面进行性能优化. 分配策略通过使用开销较小的旁路缓存，首先将使用频率较低的无用数据直接旁路到上级缓存，不仅避免对SLLC复用频率较高数据的竞争，同时也维护了缓存的包含属性. 替换策略基于预测表和采样集，利用缺失数据的地址和PC进行局部性特征的分析，从而在SLLC的数据中选择复用性最低的数据作为替换对象. 两种策略通过相互学习和完善，在有效降低SLLC缺失率的同时，更进一步提高了管理策略的预测精度，而其较低的硬件开销同样符合未来空间应用对资源消耗的苛刻要求.

[1] Jianwei D， Lei W. An energy-efficient L2 cache architecture using way tag information under write-through policy[J]. IEEE Trans on VLSI systems， 2013，21(1):102-111.

[2] Jorge A， Pablo I， Victor V， et al. Exploiting reuse locality on inclusive shared last-level caches[J]. ACM Trans on ACO， 2013，9(4):38.1-39.19.

[3] Jue W， Xiangyu D， Yuan X. Preventing STT-RAM last-level caches from port obstruction[J]. ACM Trans on ACO， 2014，11(3):23.1-23.19.

[4] Viacheslav V F， Sheng Q， Narasimha R， et al. ARI: adaptive LLC-memory traffic management[J]. ACM Trans on ACO， 2013，10(4):46.1-46.19.

[5] Pierfrancesco F， Marco S. Exploiting to improve performance of NUCA-based CMP systems[J]. ACM Trans on Embedded Computing Systems， 2014，13(3):117.1-117.23.

[6] Geng T， Michael L. An effectiveness-based adaptive cache replacement policy[J]. Microprocessors and Microsystems， 2014，38(1):98-111.

[7] Eom Y S， Kwak J W， Jhang S T， et al. Bypass extended stack processing for anti-thrashing replacement in shared last level cache of chip multiprocessors[J]. IEICE Trans on Information and Systems， 2013，96(2):370-374.

[8] Saurabh G， Hongliang G， Huiyang Z. Adaptive cache bypassing for inclusive last level caches[C]∥IEEE 27th international Symposium on IPDPS. Boston， USA: [s.n.]， 2013:1243-1253.

[9] Ni Y L， Zhou X F. A novel pseudo-LRU based shared cache partitioning mechanism[J]. Acta Electronica Sinica， 2013，41(4):68-684.

[10] Aamer J， Eric B， Malini B， et al. Achieving non-inclusive cache performance with inclusive caches[C]∥43rd Annual IEEE/ACM International Symposium on MICRO. Atlanta， USA: [s.n.]， 2010:151-162.

[11] Yingying T， Samira M K， Daniel A J. Temporal-based multilevel correlating inclusive cache replacement[J]. ACM Trans on ACO， 2013，10(4):1544-3566.

[12] Yoav E， Dror G F. Exploiting core working sets to filter the L1 cache with random sampling[J]. IEEE Trans on Computers， 2012，61(11):1535-1550.

[13] Huang Z B， Zhu M F， Xia L M. A cache dynamic power analysis tool in full-system Simics[J]. Journal of Shanghai Jiaotong University， 2013:47(1):103-107.

(责任编辑：刘芳)

A Shared Last-Level Cache Management Policy for Inclusive Cache

LOU Mian1， XIAO Jian-qing1， ZHANG Xun-ying1， WU Long-sheng1， GUAN Gang-qiang2

(1.Xi’an Micro-Electronics Technique Institute， Xi’an， Shannxi 710075，China； 2.School of Electronic Science and Engineering， National University of Defense Technology， Changsha， Hunan 410073， China)

For the problem that the traditional LRU replacement is unaware of the temporal locality in inclusive cache, a shared last-level cache (SLLC) management policy was presented for inclusive cache. With a cost-less bypass buffer stored the useless data beforehand, the policy could avoid the resource competition in SLLC between these data and highly reused data, while it still maintains the inclusion property. To further find out the least reused blocks to replace, a temporal locality detector applied was helpful to evict these blocks from SLLC as early as possible. Finally, benefited from adjustment mutually between two predictors, a unified management algorithm was proposed to bypass the useless blocks and replace the less reused blocks. Test results show that the approach reduces miss rate by 21.67% on average and improves the prediction accuracy up to 72%, while requiring less than 1% overhead of SLLC.

inclusive cache; management policy; shared last-level cache; multiprocessors

2014-09-08

国家“八六三”计划项目(2011AA120204)；航天创新计划项目(YY2011-012)

娄冕(1987—)，男，博士生，E-mail：citydremer@163.com.

吴龙胜(1968—)，男，研究员，博士生导师，E-mail：wls771@163.com.

TN 47

A

1001-0645(2016)01-0075-06

10.15918/j.tbit1001-0645.2016.01.014