在处理器系统处于正常的运行状态时,各级Cache处于饱和状态。由于Cache的容量远小于主存储器,Cache Miss时有发生。一次Cache Miss不仅意味着处理器需要从主存储器中获取数据,而且需要将Cache的某一个Block替换出去。
不同的微架构使用了不同的CacheBlock替换算法,本篇仅关注采用Set-Associative方式的Cache Block替换算法。在讲述这些替换算法之前,需要了解Cache Block的状态。如图2?4所示,在Tag阵列中,除了具有地址信息之外,还含有Cache Block的状态信息。不同的Cache一致性策略使用的Cache状态信息并不相同,如Illinois Protocol[32]协议使用的相关的状态信息,该协议也被称为MESI协议。
在MESI协议中,一个Cache Block通常含有MESI这四个状态位,如果考虑多级Cache层次结构的存在,MESI这些状态位的表现形式更为复杂一些。在有些微架构中,Cache Block中还含有一个L(Lock)位,当该位有效时,该Block不得被替换。L位的存在,可以方便地将微架构中的Cache模拟成为SRAM,供用户定制使用。使用这种方式需要慎重。
在很多情况下,定制使用后的Cache优化结果可能不如CPU自身的管理机制。有时一种优化手段可能会在局部中发挥巨大作用,可是应用到全局后有时不但不会加分,反而带来了相当大的系统惩罚。这并不是这些优化手段的问题,只是使用者需要知道更高层面的权衡与取舍。不谋万世者,不足谋一时;不谋全局者,不足谋一域。
在CacheBlock中,除了有MESIL这些状态位之外,还有一些特殊的状态位,这些状态位与Cache Block的更换策略相关。微架构进行Cache Block更换时需要根据这些状态位判断在同一个Set中Cache Block的使用情况,之后选择合适的算法进行Cache Block更换。常用的Replacement算法有MRU(Most Recently Used),FIFO,RR(Round Robin),Random,LRU(Least Recently Used)和PLRU(Pseudo LRU)算法。
所有页面替换算法与Belady's Algorithm算法相比都不是最优的。Belady算法可以对将来进行无限制的预测,并以此决定替换未来最长时间内不使用的数据。这种理想情况被称作最优算法,Belady's Algorithm算法只有理论意义,因为精确预测一个Cache Block在处理器系统中未来的存活时间没有实际的可操作性,这种算法并没有实用价值。这个算法是为不完美的缓存算法树立一个完美标准。
在以上可实现的不完美算法中,RR,FIFO和Random并没有考虑Cache Block使用的历史信息。而Temporal和Spatial Locality需要依赖这些历史信息,这使得某些微架构没有选用这些算法,而使用LRU类算法,这不意味着RR,FIFO和Random没有优点。
理论和Benchmark结果[23][35][37]多次验证,在Miss Ratio的考核中,LRU类优于MRU,FIFO和RR类算法。这也并不意味着LRU是实现中较优的Cache替换算法。事实上,在很多场景下LRU算法的表现非常糟糕。考虑4-Way Set-Associative方式的Cache,在一个连续访问序列{a, b, c, d, e}命中到同一个Set时,Cache Miss Ratio非常高。
在这种场景下,LRU并不比RR,FIFO算法强出多少,甚至会明显弱于Random实现方式。事实上我们总能找到某个特定的场景证明LRU弱于RR,FIFO和上文中提及的任何一种简单的算法。我们也可以很容易地找到优于LRU实现的页面替换算法,诸如2Q,LRFU,LRU-K,Clock和Clock-Pro算法等。
这些算法在分布存储,Web应用与文件系统中得到了广泛的应用。Cache与主存储器的访问差异,低于主存储器与外部存储器的访问差异。这使得针对主存储器的页面替换算法有更多的回旋空间,使得在狭义Cache中得到广泛应用的LRU/PLRU算法失去了用武之地。PLRU算法实现相对较为简单这个优点,在这些领域体现得并不明显,不足以掩饰其劣势。
LRU算法并没有利用访问次数这个重要信息,在处理File Scanning这种Weak Locality时力不从心。而且在循环访问比广义Cache稍大一些的数据对象时,Miss Rate较高[42]。LRU算法有几种派生实现方式,如LRFU和LRU-K。
LRFU算法是LRU和LFU(Least FrequentlyUsed),LFU算法的实现要点是优先替换访问次数最少的数据。LRU-K算法[38]记录页面的访问次数,K为最大值。首先从访问次数为1的页面中根据LRU算法进行替换操作,没有访问次数为1的页面则继续查找为2的页面直到K,当K等于1时,该算法与LRU等效,在实现中LRU-2算法较为常用。
LRU-K算法使用多个Priority Queue,算法复杂度为O(log2N)[39],而LRU,FIFO这类算法复杂度为O(1),采用这种算法时的Overhead略大,多个Queue使用的空间相互独立,浪费的空间较多。2Q算法[39]的设计初衷是在保持LRU-2效果不变的前提下减少Overhead并合理地使用空间。2Q算法有两种实现方式,Simplified 2Q和Full Version。
Simplified 2Q使用了A1和Am两个队列,其中A1使用FIFO算法,Am使用LRU算法进行替换操作。A1负责管理Cold数据,Am负责管理Hot数据,其中在A1的数据可以升级到Am,但是不能进行反向操作。
如果访问的数据p在Am中命中时将其放回Rear[1];如果在A1中命中,将其移除并放入到Am中。如果p没有在A1或者Am中命中时,率先使用这些Queue中的空余空间,将其放入到A1的Rear;如果没有空余空间,则检查A1的容量是否超过Threshold参数,超过则从A1的Front移除旧数据,将p放入A1的Rear;如果没有超过则从Am的Front移除旧数据,将p放入A1的Rear。
在这种实现中,合理设置Threshold参数至关重要。这个参数过小还是过大,都无法合理平衡A1和Am的负载。这个参数在Access Pattern发生变化时很难确定,很难合理地使用这些空间。LRU-2算法存在同样的问题。这是Full Version 2Q算法要解决的问题。
Full Version 2Q将A1分解为A1in和A1out两个Queue,其中Kin为A1in的阈值,Kout为Aout的阈值。此外在A1in和A1out中不再保存数据,而是数据指针,使用这种方法Am可以使用所有Slot,在一定程度上解决了Adaptive的问题。
如果访问的数据x在Am中命中时将其放回Rear;如果在A1out命中,则需要为x申请数据缓冲,即reclaimfor(x),之后将x放入Am的Rear;如果x在A1in中命中,不需要做任何操作;如果x没有在任何queue中命中,则reclaimfor(x)并将其放入A1in的Rear。
如果A1in,A1out
这些算法都基于LRU算法,而LRU算法通常使用Link List方式实现,在访问命中时,数据从Link List的Front取出后放回Rear,发生Replacement时,淘汰Front数据并将新数据放入Rear。这个过程并不复杂,但是遍历Link List的时间依然不能忽略。
Clock算法可以有效减少这种遍历时间,而后出现的Clock-Pro算法的提出使FIFO类页面替换算法受到了更多的关注。传统的FIFO算法与LRU算法存在共同的缺点就是没有使用访问次数这个信息,不适于处理Weak Locality的Access Pattern。
Second Chance算法对传统的FIFO算法略微进行了修改,在一定程度上可以处理Weak Locality的Access Pattern。Second Chance算法多采用Queue方式实现,为Queue中每一个Entry设置一个Reference Bit。访问命中时,将Reference Bit设置为1。进行页面替换时查找Front指针,如果其Reference Bit为1时,清除该Entry的Reference Bit,并将其放入Rear后继续查找直到某个Entry的Reference Bit为0后进行替换操作,并将新的数据放入Rear并清除Reference Bit。
Clock算法是针对LRU算法开销较大的一种改进方式,在Second Change算法的基础之上提出,属于FIFO类算法。Clock算法不需要从Front移除Entry再添加到Rear的操作,而采用Circular List方式实现,将Second Change使用的Front和Rear合并为Hand指针即可。
这些算法各有优缺点,其存在的目的是为了迎接LIRS(Low Inter-Reference RecencySet)[40]算法的横空出世。从纯算法的角度上看,LIRS根本上解决了LRU算法在File Scanning,Loop-Like Accesses和Accesses with DistinctFrequencies这类Access Pattern面前的不足,较为完美地解决了Weak Locality的数据访问。其算法效率为O(1),其实现依然略为复杂,但在I/O存储领域,略微的计算复杂度在带来的巨大优势面前何足道哉。
在LIRS算法中使用了IRR(Inter-ReferenceRecency)和Recency这两个参数。其中IRR指一个页面最近两次的访问间隔;Recency指页面最近一次访问至当前时间内有多少页面曾经被访问过。在IRR和Recency参数中不包含重复的页面数,因为其他页面的重复对计算当前页面的优先权没有太多影响。IRR和Recency参数的计算示例如图2?11所示。
其中页面1的最近一次访问间隔中,只有三个不重复的页面2,3和4,所以IRR为3;页面1最后一次访问至当前时间内有2个不重复的页面,所以Recency为2。我们考虑一个更加复杂的访问序列,并获得图2?12所示的IRR和Recency参数。
这组访问序列为{A,D,B,C,B,A,D,A,E},最后的结果是各个页面在第10拍时所获得的IRR和Recency参数。以页面D为例,最后一次访问是第7拍,Recency为2;第2~7中有3个不重复的页面,IRR为3。其中IRR参数为Infinite表示在指定的时间间隔之内,没有对该页面进行过两次访问,所以无法计算其IRR参数。LIRS算法首先替换IRR最大的页面,其中Infinite为最大值;当IRR相同时,替换Recency最大的页面。
IRR在一定程度上可以反映页面的访问频率,基于一个页面当前的IRR越大,将来的IRR会更大的思想;Recency参数相当与LRU。在进行替换时,IRR优先于Recency,从而降低了最近一次数据访问的优先级。有些数据虽然是最近访问的却不一定常用,可能在一次访问后很长时间不会再次使用。如果Recency优先于IRR,这些仅用一次的数据停留时间相对较长。
在一个随机访问序列中,并在一个相对较短的时间内精确计算出IRR和Recency参数并不容易。但是我们不需要精确计算IRR和Recency这两个参数。很多时候知道一个结果就已经足够了。在LIRS算法中比较IRR参数时,只要有一个是Infinite,就不需要比较其他结果。假如有多个infinite,比如C和D,此时我们需要进一步比较C和D的Recency,但是我们只需要关心CR>DR这个结果,并不关心C是4还是5。
LIRS算法的实现没有要求精确计算IRR和Recency参数,而是给出了一个基于LIRS Stack的近似结果。LIRS算法根据IRR参数的不同,将页面分为LIR(Low IRR)和HIR(High IRR)两类,并尽量使得LIR页面更多的在Cache中命中,并优先替换在Cache中的HIR页面。
LIRS Stack包含一个LRU Stack,LRU Stack大小固定由Cache决定,存放Cache中的有效页面,在淘汰Cache中的有效页面时使用LRU算法,用以判断Recency的大小;包含一个LIRS Stack S,其中保存Recency不超过RMAX[2]的LIR和HIR页面,其中HIR页面可能并不在Cache中,依然使用LRU算法,其长度可变,用于判断IRR的大小;包含一个队列Q维护在Cache中的HIR页面,以加快这类页面的索引速度,在需要Free页面时,首先淘汰这类页面。淘汰操作将会引发一系列连锁反应。我们以图2?13为例进一步说明。
我们仅讨论图2?13中Access5这种情况,此时Stack S中存放页面{9,7,5,3,4,8},Q中存放{9,7}。Stack S的{9,7,3,4,8}在Cache中,{3,4,8}为LIR页面,{9,7,5}为HIR页面。其中Cache的大小为5,3个存放LIR页面,2个存放HIR页面。
联系客服