针对组竞争仅考虑访问请求序列的替换结果而没有考虑请求的访存特征这个问题，提出了基于堆栈距离频度的复杂加权法在线识别访问模式的方法以及自适应访问模式的缓存管理替换算法，基本思想是依据在线识别的访问请求模式特征自动调整其插入策略.在Simics中，对选自SPEC CPU2000/2006的18个测试程序及组合负载的实验结果表明，该算法的缺失率相对于DIP、RRIP、TADIP和PIPP都有显著降低.
Many proposals about the optimization of cache management policies depend on set dueling, and they choose policies according to the results of miss rates. However, they are facing challenges in multicore since they have lower accuracy and higher storage overhead. The main reason is that they only consider the results of cache replacement policies rather than the characteristic of cache access sequences (or access pattern). Therefore, an online access pattern identification method, complex stack distance weighting method was proposed, and an adaptive cache replacement policy, least recently used-C (LRU-C), was put forward. Its basic idea is to adjust the insertion position according to the result of the online access pattern identification. Experiment in the full-system Simics running 18 benchmarks from SPEC CPU2000/2006 shows that the performance of LRU-C is better than those of dynamic insertion policy,re-reference interval prediction,thread aware dynamic insertion policy and promotion/insertion pseudo-partitioning.
在众多的优化缓存管理策略的方法中，有一类是基于组竞争在多种替换算法间切换，例如动态插入替换策略[1](DIP，dynamic insertion policy)，依据一段时间之后的缺失结果，选择缺失率更低的替换算法管理整个缓存. 这类方法考虑到了缓存请求序列的多样性，但需要设置独立的附属标记目录(ATD，auxiliary tag directory)实现组竞争. 在单核处理器中，这类方法表现良好，存储开销少. 但在多核处理器中，却遇到了很大的挑战，因为访问请求来源更加多样化，且在末级共享缓存进行了混合，访问请求间的竞争污染使得组竞争机制复杂化，不仅精度降低，而且存储开销呈指数级增加[1]，主要原因是仅考虑了访问请求序列的替换结果，而没有考虑到达的访问请求的特征. 如果能在线地检测和识别这些访问请求的特征，并能预测下一阶段的访问请求的特征，就能及时调整缓存管理策略，优化缓存管理. 笔者的研究基于这个思路展开.
1 缓存的访问模式访问模式是指一段时间内访问请求序列呈现出的保持不变的特征. Jaleel A等[1]扩展了DIP策略，将应用分成4类，并提出共享末级缓存中基于组竞争的线程敏感的动态插入替换策略(TADIP，thread-aware dynamic insertion policy). 重用间隔预测(RRIP，re-reference interval prediction)[2]机制将访问模式分成4类，即时间局部特征友好性访问模式、颠簸访问模式、流访问模式和混合访问模式，并采取不同的预测方法优化缓存管理，但没有给出访问模式在线识别的方法. 黄智濒等[3]提出了一种基于堆栈直方图峰值的在线识别访问模式的方法，但由于峰值识别需要一个较长的采样周期和较长的访问请求序列，影响访问模式的预测. 因此，笔者提出了一种新的在线识别机制.
1.1 复杂加权的在线访问模式识别法最近最少使用(LRU，least recently used)替换算法具有堆栈属性. 可通过堆栈距离直方图(SDH，stack distance histograms)获得替换算法的特征. Qureshi等[4]提出了一个低开销的电路来测量SDH，使用ATD统计SDH. 笔者的目的不是为了计算SDH，而是在线的识别访问模式，因此不需要ATD，而只需要少量的缓存块组成一个地址跟踪阵列(ATA，address trace array)，ATA可以通过保留一个L2缓存的缓存组或者使用寄存器文件构成.
访问模式识别器主要由2个部件构成：1) 地址跟踪阵列ATA,每个处理器核配备一个地址跟踪阵列，用来跟踪由该处理器核触发的缓存请求. ATA使用真LRU替换算法来管理，设其大小为T. 2) 堆栈距离直方图计数器组(CSDFs，counters of stack distance frequency)，由T+1个计数器组成，每个计数器32位,记录堆栈距离为1到T，以及大于T的频度. 依据实验情况，ATA只需要配置8个缓存块就可正确识别访问模式. 受L1缓存过滤效应的影响，访问模式识别器的带宽压力减轻，且不在访问请求的关键路径上，时间开销小.
复杂加权的在线访问模式识别法假设在一定的采样周期内，到达的缓存访问请求序列都是混合式的访问模式. 这种假设更符合实际的访问序列，只是其特征会偏向于某一种单纯的访问模式，且这种偏向性会动态变化. 复杂加权识别法依据堆栈距离频度的加权平均值(CWA，complex weight average)认定访问请求序列更偏向于哪一种访问模式. 它使用较短的采样周期和较短的访问请求序列即可确定模式特征的偏向性. 设λ为堆栈距离大于8时的权重，为了减少有限的ATA存储空间引起的误差，λ取值范围为T+1到2T. 复杂加权识别法的算法描述如下.
R是来自于核i 的缓存请求. A 是请求R 的地址.
CSDF={CSDF1,CSDF2,…,CSDFT,CSDFT+1}
PWA=上一个周期的堆栈距离频度加权平均值；初始值为0.
CWA=当前采样周期结束时，堆栈距离频度的加权平均值；
AP=访问模式类型
IF 采样周期结束 THEN BEGIN
CWA=1*CSDF1+2*CSDF2+…+T*CSDFT+λ*CSDFT+1
IF CWA >=PWA THEN
AP偏向颠簸或流访问模式
ELSE IF CWA<PWA THEN BEGIN
AP偏向时间局部特征友好性访问模式
END
PWA=CWA
重置堆栈距离直方图计数器组 {CSDFi}(1≤i≤n)
为当前周期的访问计数器的1/4值.
END ELSE IF采样周期没有结束 THE BEGIN
p=Lookup(R,ATAi) /*Lookup是在ATA中检索地址A，
返回值为该地址在替换堆栈中的位置，没有找到时，返回-1. */
IF p=-1/*NOT FOUND*/ THEN BEGIN
从ATAi中选择一个替换块V，基于LRU替换算法
将数据块A放置到ATAi中.
| $\begin{align} & CSD{{F}_{T+1}}=CSD{{F}_{T+1}}+1 \\ & END\text{ }ELSE\text{ }IF~p~in\text{ }\left( 1,T \right)\text{ }THEN\text{ }BEGIN \\ & CSD{{F}_{p}}=CSD{{F}_{p}}+1 \\ & END \\ & END \\ \end{align}$ |
每个采样周期结束时，识别访问模式的机制触发. 每个处理器核设置了一个额外的过去权重平均值(PWA，past weight average)计数器，用于记录上一个采样周期的CWA的值. PWA初始时设置为0. 首先计算CWA的值. 如果CWA大于PWA，则认为访问序列的特征偏向于颠簸或流访问模式. 如果CWA小于PWA，则认为偏向于时间局部特征友好性访问模式. 识别完成后，为了继承访问序列的历史信息，将这一个周期的访问计数器的1/4值作为历史数据带入到下一个采样周期.
1.2 开销分析在线识别方法的主要的存储开销就是每个处理器核设置T+1个计数器，每个计数器32位，依据实验分析，当T大于8时，就可有效地识别出访问模式. 时间开销很少，因为访问请求是同时分派到末级缓存和每一个处理器核的地址跟踪阵列.
另外，采样周期会决定访问请求序列的长度. 如果采样周期过长，难以及时地识别访问模式. 如果采样周期过短，识别过程发生太过频繁，且会导致识别精度不高. 在笔者提出的方法中，由于指令条数比较容易获取，依据指令平均触发的访存情况，依据实验过程以及参考以前的研究[3]，采样周期设为每10万条指令识别一次.
2 适应访问模式的缓存替换算法 2.1 基于请求序列的访问模式在线识别的自适应替换机制的架构基于缓存请求访问模式在线识别的自适应插入策略的整体架构，如图 1所示. 1) 缓存请求分派器(CRD，cache request dispatch)：用于区分缓存请求的来源，然后分派到对应的访问模式识别器. 来源主要有2类：a) 由于L1缓存缺失引起的对L2缓存的访问请求；b) 缓存一致性引擎广播的更新访问请求. 对于前者，可直接通过添加处理器核ID号区分. 对于后者，通过添加一个特殊的ID号，让所有的处理器核的访问请求地址跟踪机制均处理这类请求. 2) 缓存请求序列的关系模型：访问模式的识别是依据每个处理器核的访问请求序列，这些请求在共享末级缓存L2中混合. 因此，在缓存管理时，这种请求混和引起的竞争和污染不能忽视. 这个问题在TADIP[1]中有详细的讨论. 笔者采用TADIP-Isolated简单关系模型. 3) 插入策略：通过修改插入位置，可支持不同的访问模式. 例如在DIP机制中，通过将新载入的缓存块放置在堆栈底部位置，支持颠簸访问模式或流访问模式. 笔者扩展了这种思想，将插入位置进行细粒度的动态调整，实现对不同的访问模式及其混合的支持.
|
图 1 基于请求访问模式的自适应替换算法架构 |
LRU-C的替换算法分为插入子策略和移除子策略. 其中移出策略与传统的LRU替换策略一样，栈底元素被选中为移出缓存块.
当缓存请求R到达共享末级缓存时，缓存请求同时分派给共享末级缓存和缓存请求分派器CRD. CRD依据来源的处理器核顺序编号区分请求R. 然后，将R分派到对应的处理器核的ATA，并检索R请求的地址，如果R被命中，则计算其堆栈重用距离，并使对应的频度计数器加1. 如果R没有被命中，则CSDF>T增加1，在每一个采样周期结束时，判断访问序列所属的访问模式，LRU-C依据复杂加权识别法来在线判定访问模式，并依据近期策略预测未来访问模式.
LRU-C依据访问模式的不同调整插入位置. LRU-C与DIP机制的主要区别在于LRU-C基于访问请求序列的特征调整插入位置，而DIP机制依赖组竞争的结果判断如何调整插入位置. 在LRU-C中，插入位置有可能是替换堆栈的任意位置. 插入位置的调整是细粒度的，插入位置会沿着替换堆栈的栈顶提升1位或沿着栈底下降1位，调整的依据是访问频度的加权平均值的变化.
在共享的多核末级缓存，这些访问请求序列会发生混合，并产生竞争，进而导致污染. 因此，LRU-C还需要考虑这种混合后如何调整插入位置的问题. 笔者利用了TADIP-Isolated简单关系模型.
3 实验评估基于时钟周期的全系统模拟器Simics[5]，模拟了一个16核的多核处理器. 具体参数如表 1所示.
|
表 1 实验环境的基准配置 |
据缺失率特征将测试程序分成2组. 每一组由9个程序组成，其中Group 1的测试程序都是访存密集型的，Group 2都是计算密集型的. 表 2所示为21个两混合的并发进程负载. 对于单进程负载，主要以每千条指令的缺失作为性能评估指标，并与DIP和DRRIP进行比较. DRRIP是通过添加ATD实现组竞争而动态调整间隔预测的替换管理策略. 对于两进程负载，采用基于每个周期的指令(IPC，instruction per cycle)吞吐率[6]的性能比较. 主要与伪分区管理策略PIPP[7]和孤立的线程敏感动态插入策略TADIP-I[1]进行比较.
|
|
表 2 两进程负载组合 |
针对18个基准测试程序的实验结果如图 2所示. 与LRU相比，LRU-C、DIP和DRRIP策略的最大优化发生在WS5、WS6、WS7，它们是典型的颠簸应用. 相对于LRU管理时的数据，188.ammp(WS7)的每千条指令的缺失数在LRU-C、DIP和DRRIP管理时，分别降低了68.2%、26.2%和48.1%.
|
图 2 2MB/8路末级缓存分别在LRU/LRU-C/DIP/RRIP管理时18个程序单独运行时的缺失率 |
另外，与LRU相比，LRU-C、DIP和DRRIP策略的最小优化发生在WS1、WS2、WS4、WS8、WS10、WS11、WS12、WS13、WS15、WS16和WS17. 这些程序可以分为2类：1)时间局部特征友好性访问模式；2)流访问模式. 对于前者，如197.parser(WS8)和471.omnetpp(WS17). 传统的LRU替换管理策略就是性能优化的替换算法. 经过组竞争机制，LRU也会被选中用来管理整体的缓存组，从而DIP和DRRIP具有了和LRU一样的性能. 在LRU-C中，基于对访问模式的在线识别方法，LRU-C的插入位置也位于堆栈顶部. 这些结果也证明了笔者提出的在线识别访问模式方法的正确性. 且在LRU-C中，这些应用的缺失率比LRU还要低. 主要原因在于在线识别机制的细粒度性可更为有效地管理缓存. 例如，很多整体上时间局部特征友好的应用在其执行的某些阶段往往会表现出颠簸或流访问模式的特征，如WS3.
对于后者，如433.milc(WS12)，缓存块的重用很少，当缓存容量大小增加时，它的缺失率并不会有显著变化，绕开机制及其扩展机制可有效地降低这些访问请求对缓存的整体污染和影响. 由于笔者提出的在线访问模式的识别方法存储空间有限，使它识别出的流访问模式直接用来指导绕开机制会导致精度不高，这也是未来研究的内容之一. 但是，通过将这些应用触发的缓存请求块放置在合适的位置，有助于减少对其他缓存行的污染. 例如，相对于LRU，255.vortex(WS9)在LRU-C、DIP和DRRIP中的缺失率分别降低4.7%、2.2%和1.7%.
从这些对比数据中可以看出，LRU-C不仅优于LRU，而且比DIP和DRRIP机制有更好的性能.
在共享末级缓存中，来自多个请求源的缓存请求数据块插入在不同的位置，会形成不同的缓存块的生命周期，最终导致不同的缓存空间的占用[6-7]. 也就是说，调整插入位置会影响缓存请求序列之间的竞争和干扰. 在LRU-C中，针对各个处理器核之间的竞争污染，假设各处理器核之间的竞争是有利的，允许适度的竞争来提升缓存的利用效率.
笔者将LRU-C与PIPP和TADIP-I进行性能对比，如图 3所示. 在这3类混合进程的构造中，Group 1+Group 2类的构造的测试程序表现出了最好的性能提升. 相对于LRU、DIP、DRRIP和PIPP策略，提升的性能平均值达10.2%、4.1%、4.3%和0.8%. 在Group 2+Group 2组构成的并发进程中，LRU-C的性能与LRU非常接近. 因为Group 2+Group 2都是由时间局部特征友好的应用构成的. 在LRU管理下，它们的缺失率已很低，但LRU-C也有很好的性能和很低的缺失率. 在Group 1+Group 1组的性能变化则比较复杂. 虽在Group 1中的多数应用触发的缓存访问请求都是颠簸访问模式，但这些访存密集型的应用混合之后，它们之间的竞争和干扰严重相互影响. LRU-C由于采用了简化的独立关系模型，性能的提升潜力并没有完全发挥，但性能依然有所提升. 利用更复杂的关系处理模型应对处理器核之间的竞争和污染是未来的工作.
|
图 3 LRU-C与4种典型的替换管理机制基于IPC吞吐率的性能比较(基于真LRU数据) |
笔者提出了复杂加权的在线访问模式识别法和适应访问模式的缓存管理替换算法LRU-C. 通过选自SPEC CPU2000/2006的18个测试程序及其多进程组合负载的实验评估，其性能相对于DIP、DRRIP、TADIP和PIPP都有显著提升.
| [1] |
Jaleel A, William H, Qureshi M, et al. Adaptive insertion policies for managing shared caches[C]//Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques. New York:ACM, 2007:208-219.
( 0)
|
| [2] |
Jaleel A, Theobald K B, Steely S C, et al. High performance cache replacement using re-reference interval prediction (RRIP)[C]//Proceedings of the 37th Annual International Symposium on Computer Architecture. New York:ACM, 2010:60-71.
(0)
|
| [3] |
黄智濒, 周锋, 马华东, 等. 利用堆栈特征的片上末级缓存访问模式在线识别方法[J]. 国防科技大学学报 , 2015, 37 (1)
:1–7.
Huang Zhibin, Zhou Feng, Ma Huadong, et al. An online access pattern identification method based on the stack characteristic in the on-chip last-level-cache[J]. Journal of National University of Defense Technology , 2015, 37 (1) :1–7.
(0)
|
| [4] |
Qureshi M K, Patt Y N. Utility-based cache partitioning:a low-overhead, high-performance, runtime mechanism to partition shared caches[C]//Proceedings of the 39th Annual International Symposium on Microarchitecture. 2006:423-432.
http://cn.bing.com/academic/profile?id=2143773524&encoded=0&v=paper_preview&mkt=zh-cn (0)
|
| [5] |
Magnusson P S, Christensson M, Eskilson J, et al. Simics:a full system simulation platform[J]. Computer , 2002, 35 (2) :50–58.
doi:10.1109/2.982916 (0)
|
| [6] |
Huang Zhibin, Zhu Mingfa, Xiao Limin. LvtPPP:live-time protected pseudo-partitioning of multicore shared caches[J]. IEEE Transactions on Parallel and Distributed Systems , 2013, 24 (8) :1622–1632.
doi:10.1109/TPDS.2012.230 (0)
|
| [7] |
Xie Yuejian, Loh G H. PIPP:promotion/insertion pseudo-partitioning of multi-core shared caches[C]//Proceedings of the 36th Annual International Symposium on Computer Architecture. New York:ACM, 2009:174-183.
http://cn.bing.com/academic/profile?id=2135089498&encoded=0&v=paper_preview&mkt=zh-cn (0)
|