我正在为一个面试学习,并且想在缓存方面恢复我的记忆。如果CPU的高速缓存具有LRU替换策略,那么如何在芯片上实际实现呢?每个缓存行都会存储一个时间戳记吗?
在两个CPU同时写入一个地址的双核系统中,还会发生什么?
对于只有两种方式的传统高速缓存,每套单个位可用于跟踪LRU。在访问任何命中的集合时,可以将位设置为未命中的方式。
对于较大的关联性,状态数量会急剧增加:方式数量的阶乘。因此,四路高速缓存将具有24个状态,每组需要5位,而八路高速缓存将具有40,320个状态,每组需要16位。除了存储开销外,更新值还需要更大的开销。
对于4路高速缓存,状态的以下编码似乎可以很好地发挥作用:两位用于最近使用的方式编号,两位用于下一个最近使用的方式编号,以及一位指示更高还是更高编号较低的方式最近被使用。
由于LRU跟踪具有此类开销,因此经常使用更简单的机制,例如二叉树伪LRU。在命中时,这样只会更新树的每个分支部分,命中了其中一半的关联方式。对于具有两种方式W的幂,二叉树pLRU高速缓存每组的状态位将为W-1 。8路高速缓存的方式6命中(使用3级二进制树)将清除树底的位,以指示方式(0,1,2,3)的下半部分较少最近使用,请清除下一个级别的较高位以指示这些方式的下半部分(4,5)较少使用,并在最终级别中将较高位设置为指示这些方式的上半部分(7)最近较少使用。不必读取此状态以进行更新可以简化硬件。
对于偏斜的关联性,其中不同的方式使用不同的哈希函数,有人提出了一种类似缩写的时间戳记(例如,“偏斜关联缓存的分析和替换”,Mark Brehob等,1997)。使用未命中计数器比循环计数更合适,但是基本思想是相同的。
关于两个内核尝试同时写入同一高速缓存行时发生的情况,可以通过仅允许一个L1高速缓存在给定时间将高速缓存行置于独占状态来解决此问题。实际上,这是一场比赛,一个核心将获得独占访问权。如果只有一个写入核心已经具有处于共享状态的缓存行,则它更有可能赢得竞争。在高速缓存行处于共享状态的情况下,高速缓存仅需要向高速缓存行的其他潜在持有者发送无效请求;在不存在高速缓存行的情况下,写操作通常需要请求数据的高速缓存行以及请求独占状态。
由不同的内核写入同一缓存行(无论是相同的特定地址,还是在数据共享的情况下写入同一行中的另一个地址)可能会导致“缓存行乒乓”,其中不同的内核会使缓存无效其他高速缓存中的高速缓存行以获取独占访问权(以执行写操作),以便高速缓存行像乒乓球一样在系统周围反弹。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句