一种改进的抗干扰性可预测的协作缓存机制

苑风凯+季振洲

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163

Abstract： The Last Level Cache （LLC） in private configurations offers lower access delay and better isolation performance， but extinguishes the ability of sharing underutilized cache resources. Cooperative Caching （CC） provides capacity sharing by spilling a line evicted from one cache （spiller） to another （receiver）. The CC successors took efforts to efficient cache sharing， however no approach had undertook both the reusability of evicted lines for spillers and the anti-interference to the spilled lines for receivers. This paper proposes Reusability and Anti-Interference Predictable Cooperative Caching （RAPCC） to further improve the cache sharing ability of CMPs with private LLCs. RAPCC exploits the Reuse Position Distribution （RPD） to predict the reusability and anti-interference for the determination of a private LLC to be a spiller， receiver， neither， or either （a novel neutral spilling state to both spill and receive）. Experimental results have proven RAPCC performs best in HPKI and IPC among previously proposed CC， DSR， CBS， and ASCC.

0引言

將Last Level Cache（LLC）配置成私有LLC可以提供诸多优势：更小的Cache访问延迟、天然的性能隔离性、更好的可扩展性以及功耗优化简易性。然而，私有LLC剔除了Cache容量共享的能力，拥有闲置LLC资源的处理器核无法向LLC资源紧缺的处理器核提供未被充分利用的Cache容量，因而导致更多片外缺失，影响了系统性能。协作缓存[1]（Cooperative Caching，CC）机制允许本地LLC驱逐的牺牲块通过溢出（Spill）操作放置到另一个处理器核可能拥有空闲Cache容量的远程LLC上，达到共享片上LLC资源的目的。

CC机制的缺陷是任意LLC都可作为溢出者，同时任意LLC都需要承担接受者的义务，没有考虑到溢出者是否可以通过额外的容量获益，也没有考虑到接受者是否可以提供额外的容量而保证自身性能不受影响，削弱了私有LLC结构的性能隔离性优势。后继的CC研究试图解决CC机制的盲目溢出问题，进化出可以动态地调整接收溢出角色的机制：作为溢出者，可以获知是否有可观的可能性重用溢出块；作为接受者，可以获知是否拥有未利用的容量可供分享，同时不会损害自身的性能。此外，一种中立的接收溢出角色已经被提出，既不作为接收者也不作为溢出者，避免接收者和溢出者中的任何一个角色对性能造成损害。

本文提出重用性和抗干扰性可预测的协作缓存（Reusability and Anti-Interference Predictable Cooperative Caching，RAPCC）机制，进一步增强私有LLC的Cache容量共享能力，利用重用位置分布（Reuse Position Distribution，RPD），借助干扰注入实验，根据重用性和抗干扰性预期，将RPD划分为4种类型，采用运行时的RPD类型识别算法，监控周期性的RPD并动态地决定LLC的接受溢出角色。RAPCC提出另一种全新、中立的接受溢出角色，即LLC既可以作为溢出者，同时又可以作为接收者，有助于私有LLC更合理地分配片上存储资源。此外，RAPCC引入旁路机制，进一步扩展具有特殊RPD的接收者的接纳能力。实验结果表明，RAPCC机制在HPKI和IPC两方面的性能表现均超越了CC、DSR[2]、CBS[3]以及ASCC[4]机制。

1重用位置分布

本文遵从Tiled多核处理器作为基准架构，每个tile拥有本地的私有L2，且L1和L2为独占关系，最大限度地利用Cache存储空间。L1s和L2分别配置为16 KB 4-way和1 MB 8-way。在典型的协作缓存机制研究中，每个Cache块只有一次溢出的机会，然后在另一个LLC经历第二次LRU栈行走，直至远程命中或者被替换并驱逐出片上Cache系统。因此，本文将L2的LRU栈扩展加倍，如图1所示，利用扩展的LRU栈保存被驱逐Cache行（Line）的物理地址并追踪重用情况，就像当前已被溢出并获得第二次机会进行LRU栈行走一样。

图1左右两侧的Cache替换操作分解动作解释了扩展LRU栈的运作方式：左侧为驱逐动作，原始栈（Primary）和扩展栈（Expanded）均为满栈状态，分别需要选择LRU位置的Cache行H和P作为牺牲行进行驱逐操作；右侧为插入动作，原始栈驱逐H后将新入Cache行插入到MRU位置，扩展栈驱逐P后将原始栈驱逐的H插入MRU位置，模拟H溢出后获得第二次LRU栈行走机会。图1中每个LRU栈被划分为两个区域，MRU端白色的HIGH区和LRU端灰色的LOW区。本文定义每10 000个已提交的处理器核对L1的访问请求为一个周期，定义10 000为周期的间隔。在每个周期，记录每个LRU栈区域的命中次数，对L2的双栈四区域重用位置分布（Reuse Position Distribution，RPD）进行统计。图2展示了具有应用程序阶段特点的周期性RPD，统计数据通过使用全系统仿真工具GEM5[5]运行SPEC CPU2006测试集获取。通过观察可以看出，应用程序的不同而RPD不同，甚至应用程序内的阶段不同而RPD改变，如图2中应用程序bzip2.x、bwaves.x和soplex.x。本文将四个区域的命中次数分别命名为PH、PL、EH和EL。一方面，P数值（PH/L）和E数值（EH/L）分别反映了应用程序对本地和额外L2容量的重视程度。显然，RPD中较大数值的EH或EL，如图2中应用程序x.s，确保L2能够通过溢出高重用性的牺牲行获益明显（本文提到的重用性泛指L2中Cache行群体的重用性而非个体重用性）。另一方面，H/L比率可以帮助预测L2作为接收者的抗干扰性。图3对于重用位置高低不同的Cache行在干扰存与否情况下的LRU栈行走的过程进行描述。endprint

在图3的中央部分，Cache行Re开启了从插入位置MRU开始的LRU栈行走过程。左侧为高重用位置行走过程的描述，在图3上部没有遭遇干扰的情况下，Re经历重用时间间隔ΔTH后在HIGH区获得命中，然而，在图3下部遭遇干扰的情况下，Re经历相同的ΔTH后，受到外来干扰行IN的推移效应影响，最终在LOW区获得命中。相对地，右侧为低重用位置行走过程的描述，在图3上部没有遭遇干扰的情况下，Re经历重用时间间隔ΔTL后在LOW区获得命中，然而，在图3下部遭遇干扰的情况下，Re经历相同的ΔTL后，本应在LOW区命中却被外来干扰行推移出LRU栈导致了缺失的发生。考虑到外来干扰行的推移效应，高重用位置的Cache行相比低重用位置的Cache行的抗干擾能力更强。因此，本文提出假说：拥有H明显占优于L的RPD的L2具有较强的抗干扰性，能够胜任接收者角色。为了证实此假说的正确性，本文设计了干扰注入实验，对比干扰行注入前后L2的RPD的变化。图2中虚线隔出应用程序的干扰注入实验统计数据被绘制RPD注入前后对比情况如图4所示。本文提出的假说得到了干扰注入实验的证明。为了模仿外来溢出块，本文设计干扰注入器，产生无效的、物理地址不相关的Cache行，以具有代表性的频度200/周期插入L2作为干扰行。以下根据RPD的分类论述具有各种类型RPD的L2的抗干扰性，RPD共分为如下四类：1）接受者（RECEIVER）。此类RPD没有E数值而且PH相比PL较大，如图2中的gromacs.r和bwaves.r。具有此类RPD的L2不能通过额外的Cache容量获益，同时高比率的高重用位置Cache行保障了对外来溢出块的干扰免疫性。特殊实例为图2中的libquantum.r，甚至没有P数值，拥有天然的、无限制的抗干扰能力。接收者RPD的抗干扰性得到了图4中的bwaves.ri的证实，并拥有与bawaves.r相同的P总量（PH+PL），即外来干扰行只是将一部分命中从PH推移到PL，未能影响整体性能。

2）NEITHER。此类RPD没有E数值而且PH与PL相比未能占据主导地位，如图2中的bzip2.n、tonto.n和soplex.n。图4中注入后的soplex.ni显示了此类RPD较差的抗干扰性。干扰行的推移效应驱逐了部分本应贡献PL命中数的Cache行，这些Cache行被扩展LRU栈回收并转化为EH，即E_HIGH区域的命中数。缺失的Cache行造成了L2所在处理器核的性能损失，因此，具有此类RPD的L2既不应作为溢出者也不应作为接收者。

3）溢出者（SPILLER）。此类RPD具有E数值而且至少有一个H数值（P/EH）相比同栈的L数值（P/EL）未能占据主导地位，如图2中的bzip2.s、mcf.s、omnetpp.s和soplex.s。具有此类RPD的L2可以通过额外的Cache容量获益，却受制于其H/L比率，不适合作为接收者。不同于P区域（P_HIGH/LOW），E区域（E_HIGH/LOW）的推移效应源于受外来干扰行影响增多的溢出行。图4中注入后的omnetpp.si的E总量（EH+EL）相比omnetpp.s大幅降低，即增多的溢出行将竞争有限的接收者Cache容量，导致远程命中的减少造成性能损失。另外，即使新增溢出行能够得到等价的远程命中数（从PL转换为EH），片上远程取回操作相比本地命中既耗时又耗能，本文倾向于将PL保留在本地而不受外来干扰行的影响。因此，图2中的bzip2.s因为高比率的PL而不适合作为接收者。

4）EITHER。这是首次被提出的中立类型RPD。此类RPD具有E数值而且所有的H数值相比同栈的L数值均占据主导地位（H/L数值均为0为特殊情况），如图2中的bwaves.e和hmmer.e。图4中注入后的hmmer.ei的P和E总量均于hmmer.e相同。具有此类RPD的L2既可以作为溢出者通过额外的Cache容量获益，同时可以作为接收者贡献自身的Cache容量而不会影响性能，这归功于本文发现并利用独特的RPD。

2RAPCC机制的实现算法

基于上述对RPD的分类，RAPCC机制在运行时根据L2的RPD所表达的重用性和抗干扰性预期动态地调整L2的接受溢出角色，具有较强的可行性，容易实现。本文提供运行时易实现的RPD类型识别算法，研究可得运行内容如下。

每个L2需要添加两个1-bit的标志位：Spill和Receive，指示L2当前的接收溢出角色。接收溢出状态的命名采用RPD类型的名称，如上文程序中符号“※”后的注释。在本文中，溢出者需要找到接收者才能完成溢出操作，否则待溢出行将被写回内存。标志位Spill指示L2是否对遭驱逐牺牲行执行溢出操作，Receive则回答溢出者的问询指示此L2是否可以作为接收者。ThrP、ThrE、ThrPx、ThrEx和RHL均为算法参数。其中，ThrP和ThrE分别定义特定周期间隔下应用程序运行性能具有实质意义的P和E总量（amount）。当判断L2是否适合作为接收者时，在程序中的逻辑表达式{1}和{2}中，除了安全比率RHL确保H数值相比同栈L数值占据主导地位，Px和Ex数值也要小于阈值ThrPx和ThrEx。图1和图3中，极限区域以深灰色在LOW区高亮出来，重用位置落入极限区域的Cache行明显更容易受到干扰的影响。因此，阈值ThrPx和ThrEx定义了作为接收者所能承受的极限区域风险。

为了加大溢出行的重用可能，本文增强特定接收者（非保护类）的接纳能力，如图2中的libquantum.r，此类接收者不需要任何的防干扰措施，不但不能利用L2的存储容量，反而不断地向L2插入无重用性的L1替换行，徒然加速外来溢出行被驱逐的进程。借助独占的L2配置，本文采用旁路机制，将L1替换行直接写回至内存，延长外来溢出行的存活时间，增大远程命中机会。程序中，第二行判断L2为非保护类接收者之后将标志位Bypass打开，指示直接向内存写回L1替换行。值得注意的是，尽管直接执行写回内存操作，但是L1替换行的物理地址仍然被保存在扩展LRU栈中，以监控应用程序新阶段的L2命中。另如程序中的第四行所示，当监测到实质性的E总量，标志位Bypass和Receive均被关闭以保护应用程序新阶段的运行性能，如行6所示。endprint

3实验结果与分析

本文使用全系统仿真工具GEM5评估RAPCC机制，对比运行RAPCC机制的系统（RAPCC系统）与CC、DSR、CBS、ASCC以及基准系统在HPKI（Hits per Kilo Instructions）和IPC两方面的性能表现。基准系统为四核Tile多核处理器，私有、独占关系的L2。L1和L2使用与本文第一节相同的配置参数。所有系统均采用DP&TB[6-7]协议维护Cache一致性，运行相同的四线程工作负载[8]（Workload）。工作负载由SPEC CPU2006测试集中的四个不同基准测试程序段混合而成，运行四个程序段的L2具有不同的RPD类型，分别为omnetpp.s、hmmer.e、libquantum.r和soplex.n，如图2和4所示。本文设计此工作负载以模拟运行时复杂的片上Cache资源共享环境，检验运行各机制的系统应對复杂局面的挑战，解决私有LLC容量共享能力的难题。

图5描述了RAP（CC）系统相比CC、DSR、CBS以及AS（CC）系统在HPKI和IPC两个方面的性能表现情况，实验结果分别归一化到RAPCC和ASCC系统。所有系统均未能影响libquantum.r的性能，因此，运行此程序段线程的处理器核性能表现被从图5中滤除。Libquantum.r的主要作用是作为接收者贡献远程命中，如表1所示。

基准系统的实验结果未能出现在图5中，因为ASCC机制将所有L2组（Set）的接收溢出角色均决策为溢出者，导致整体运行过程中没有发生任何的溢出操作，因此ASCC的性能表现完全等同于基准系统。在图5的HPKI部分，本地命中和远程命中分别使用不同的颜色进行区分。所有机制均将omnetpp.s判断为溢出者，RAPCC在HPKI方面的性能表现优于DSR和CBS机制，得益于其旁路机制增强了运行libquantum.r的L2作为接收者的接纳能力。CC系统要求omnetpp.s同时作为接收者，虽然贡献了可观的远程命中次数，CC机制下运行omnetpp.s的处理器核未能获得应有的IPC提升，因为接收外来溢出行造成的干扰减少了其远程命中次数，如图4中的omnetpp.si所示。Hmmer.e在RAPCC系统中被给予接收溢出角色EITHER，既作为接收者同时又作为溢出者，在图5中获得了最多的远程命中次数，同时在表1中贡献了256次远程命中。DSR将hmmer.e判断为接收者，CBS则将其判断为溢出者，结果，DSR系统未能使运行hmmer.e的处理器核获得HPKI提升，而CBS在IPC方面的性能表现仅与ASCC系统持平。Soplex.n在RAPCC系统中被给予接收溢出角色NEITHER，既不作为接收者也不作为溢出者，保护了本地命中的次数未受外来溢出行干扰的影响。DSR和CBS将soplex.n判断为接收者，结果在HPKI方面的性能表现尚不如CC，因为二者不允许soplex.n作为溢出者，相比CC机制错过了远程命中的补救机会。RAPCC与ASCC系统相同，运行soplex.n的处理器核在IPC方面获得最优的性能表现。除ASCC外的所有机制均判断libquantum.r为接收者。如表1中libquantum.r行，RAPCC的旁路机制帮助libquantum.r贡献了最多的远程命中次数762。此外，表1中CC贡献了最多的远程命中次数3 251，然而，受到损失的本地命中次数导致CC系统最差的IPC性能表现。整体上，RAPCC在HPKI方面优于CC、DSR、CBS以及ASCC机制分别达38%、35%、39%和8%，在IPC方面优于CC、DSR、CBS以及ASCC分别已达17%、11%、13%和3%。

4结束语

本文借助重用位置分布（RPD）与重用性和抗干扰性预期相关联，提出重用性和抗干扰性可预测的协作缓存（RAPCC）机制，采用运行时的RPD类型识别算法，监控周期性的RPD并动态地调整LLC的接受溢出角色，同时也实际增强了私有LLC的Cache容量共享能力。实验结果表明，RAPCC在HPKI和IPC方面均超越了CC、DSR、CBS和ASCC机制，具备解决复杂私有LLC资源共享难题的能力，进一步增强了协作缓存机制的Cache共享效率。

参考文献：

[1] CHANG Jichuan， SOHI G S. Cooperative caching for chip multiprocessors[C]//International Symposium on Computer Architecture. Boston， Massachusetts：ACM， 2006：264-276.

[2] QURESHI M K. Adaptive spillreceive for robust highperformance caching in CMPs[C]//International Symposium on High PERFORMANCE Computer Architecture. Raleigh， NC：IEEE， 2009：45-54.

[3] JIA Xiaomin， JIANG Jiang， ZHAO Tianlei， et al. Towards online application cache behaviors identification in CMPs[C]//International Conference on High Performance Computing and Communications.Washington， DC， USA：IEEE， 2010：1-8.

[4] ROLN D， FRAGUELA B B， DOALLO R. Adaptive set-granular cooperative caching[C]//International Symposium on High Performance Computer Architecture. Washington， DC， USA：IEEE， 2012：1-12.

[5] BINKERT N， BECKMANN B， BLACK G， et al. The gem5 simulator[J]. ACM SIGARCH Computer Architecture News， 2011， 39（2）： 1-7.

[6] YUAN Fengkai， JI Zhenzhou. DP&TB： A coherence filtering protocol for manycore chip multiprocessors[J]. Journal of Supercomputing， 2013， 66（1）： 249-261.

[7] YUAN Fengkai， JI Zhenzhou， ZHU Suxia. Setgranular regional distributed cooperative caching[J]. IEEE Computer Architecture Letters， 2015， 14（1）： 75-78.

[8] QURESHI M K， PATT Y N. Utilitybased cache partitioning： A lowoverhead， highperformance， runtime mechanism to partition shared caches[C]//International Symposium on Microarchitecture. Orlando， Florida， USA：ACM， 2006：423-432.endprint