Cache替换策略

1. Introduction

本文主要内容系Reference的整理,介绍了cache访问模式的分类和几种cache替换策略。

2. Cache访问模式分类

$$
\begin{align}
&A:( a_1 , a_2 , … , a_{k-1} , a_k , a_k , a_{k-1} , … , a_2 , a_1 )^ N\text{ for any k}\\
&B:( a_1 , a_2 , … , a_k )^ N \text{ k > cache size}\\
&C:(( a_1 , a_2 , … , a_k )\text{ k= ∞}\\
&D:[ ( a_1 , … , a_k , a_k , … , a_1 )^A P_ε( a_1 , a_2 , … , a_k , a_{k+1} … , a_m ) ]^N \\
&E:[ ( a_1 , … , a_k )^A P_ε( b_1 , b_2 , … , b _m ) ] ^N\text{ k < cache size AND m > cache size , 0 < ε < 1}
\end{align}
$$

Let Pε(a1, … , ak) denote a temporal sequence that occurs with some probability ε.

Recency-friendly Access Patterns

上图中A模式即为典型的近期立即重用模式,N表示括号里的pattern重复N次。

Thrashing Access Patterns

图中B模式,当k>cache的block数时,LRU策略将命中0次。这种情况下,最佳策略应该是在cache中保持一定的working set。

Streaming Access Patterns

图中C模式表示该访问没有局部性,可以认为它数据的重用距离是无穷大。这种模式任何替换策略都无效。

Mixed Access Patterns

D和E为混合访问模式。当m+k < available cache时,working set(即循环体)可以放到cache里,因此LRU策略的miss率可以接受。但如果m+k > available cache,LRU会替换出循环体内次数多的a部分,反而将概率性出现的b部分放到cache里,产生不可接受的miss率。

3. Cache替换策略

此部分内容见于reference 2,主要是对Reference1论文的翻译总结。

LRU

常见的LRU(Least Recently Used,即最近最少使用)替换策略总是预期对cache的访问是近期立即重新使用的(near-immediate re-reference)。LRU策略的cache way可以看成一个队列,队尾(要被踢出去)的位置是LRU,最近最少使用的位置,队首的位置是MRU(Most Recently Used),最近经常使用。

NRU

NRU(Not Recent Used) 是LRU的一个近似策略,被广泛应用于现代高性能处理器中。应用NRU策略的cache,需要在每个cache block中增加一位标记,该标记(NRU bit)“0”表示最近可能被访问到的,“1”表示最近不能访问到的。

每当一个cache hit,该cache block的NRU bit被设置为“0”表示在最近的将来,该cache block很有可能再被访问到;每当一个cache miss,替换算法会从左至右扫描NRU bit为“1”的block,如果找到则替换出该cache block,并将新插入的cache block 的NRU bit置为“0”,如果没有找到,那么将所有cache block的NRU bit置为“1”,重新从左至右扫描。

STATIC RRIP

该替换策略是对NRU的扩展,其将NRU bit扩展成M位,当M=1时,该算法蜕化成NRU。而扩展成M位的原因是为了更细粒度的区分cache block,而不是只有两个状态(最近将要访问和最近最远将要访问)。

该算法的描述和NRU相同,每当一个cache hit,该cache block的NRU bit被设置为“0”表示在最近的将来,该cache block很有可能再被访问到;每当一个cache miss,替换算法会从左至右扫描NRU bit为“2^M -1”的block,如果找到则替换出该cache block,并将新插入的cache block 的NRU bit置为“2^M -2”,如果没有找到,那么将所有cache block的NRU bit增加1,重新从左至右扫描。

上面将新插入的cache block设置为“2^M -2”,主要是为了防止那些很久才能被再次使用到的cache block长期占用cache空间。说到这里,你也许会说,这样岂不是影响那些空间局部性很好的程序的性能,确实是这样。

在RRIP类的策略中,NRU bit被描述为RRPV(Re- reference Prediction Values),可以理解为当前block被替换出去的可能性,越高越容易被替换出去。

DYNAMIC RRIP

对Static RRIP来讲,如果程序的工作集大于cache容量,那么将会频繁的换进换出,造成抖动。为此,Bimodal RRIP提出,对于新插入的cache block,以较大概率设置NRU bits为“2^M -1″,同时以较小概率设置为”2^M -2″,一次来避免抖动。

那么对于混合的访存序列,应该使用SRRIP还是BRRIP的问题,一种称之为“set Dueling”的技术将两种技术应用到不同的两个cache set上,然后统计两个set上的运行情况(主要是命中率),然后来决断到底使用两种技术中的哪一个,然后将该算法策略部署到其余各个set上。

BRRIP

在Reference1中还提出了BRRIP(Bimodal RRIP),基于Reference3的BIP。我也在下面的模拟器中实现了。

4. Cache Simulator

我修改了很久以前写的基于trace做cache分析的简易模拟器,实现了上面的替换策略,但未做完整的测试。在项目的multipolicies分支里。

https://github.com/FindHao/CacheSim/tree/multipolicies

手把手教你写Cache模拟器

Reference

High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP), ISCA 2010

Adaptive insertion policies for high performance caching, ISCA 2007

一种缓存替换策略:DYNAMIC RE-REFERENCE INTERVAL PREDICTION (RRIP)

文章版权归 FindHao 所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权|
转载必须包含本声明,并以超链接形式注明作者 FindHao 和本文原始地址:
https://www.findhao.net/easycoding/2506

你可能喜欢:

Find

新浪微博(FindHaoX86)QQ群:不安分的Coder(375670127)不安分的Coder 微信公众号(findhao-net)

发表评论

电子邮件地址不会被公开。 必填项已用*标注