gem5学习（20）：替换策略——Replacement Policies

目录

一、Random

二、Least Recently Used (LRU)

三、Tree Pseudo Least Recently Used (TreePLRU)

四、Bimodal Insertion Policy (BIP)

五、LRU Insertion Policy (LIP)

六、Most Recently Used (MRU)

七、Least Frequently Used (LFU)

八、First-In, First-Out (FIFO)

九、Second-Chance

十、Not Recently Used (NRU)

十一、Re-Reference Interval Prediction (RRIP)

十二、Bimodal Re-Reference Interval Prediction (BRRIP)

---

这一教程中主要介绍了当内存系统满时，需要进行相应的替换策略。

官网教程：gem5: Replacement Policies

Gem5实现了多种替换策略。每种替换策略在确定需要替换的数据块时，都使用特定的替换数据进行判断。替换数据是衡量数据块被替换优先级的指标。

在所有替换策略中，无效块（invalid blocks）都被优先作为替换对象。无效块是指在缓存中没有有效数据的块，即没有被使用或者已经被无效化的块。因为无效块不再有用，可以立即被替换掉，给新的数据块提供空间。

替换策略由reset()、touch()、invalidate()和getVictim()方法组成。每种方法对替换数据的处理方式不同。

• reset()用于初始化替换数据（即将其标记为有效）。它只应在插入新条目时调用，并且在无效化之前不应再次调用。对条目的第一次访问必须始终是reset()。
• touch()用于访问替换数据，因此应在条目访问时调用。它的目的是更新替换数据，用来反映最新的访问情况。【当一个条目被访问时，touch()方法被调用，说明该条目被使用了一次。通过调用touch()方法，替换策略可以根据访问模式和频率来更新替换数据，更准确地判断哪个数据块适宜留在缓存中】
• invalidate()在条目无效化时调用，之所以会被无效化，通常是由于一致性处理的需求。一致性处理可能是其他处理器或缓存修改了相同的数据，导致当前缓存中的数据变成无效状态。此时，在确定需要被替换的条目时，invalidate()会调整替换数据，使得被无效化的条目在替换决策中的优先级较高，更有可能被替换出去。
• getVictim()在发生缺失时调用，必须从缓存中选择一项数据替换出去，以腾出空间来存储新的数据。在所有候选替换条目中，它会优先搜索具有最差替换数据的条目，这意味着会根据替换策略中定义的替换数据度量标准，选择具有较低优先级的条目作为替换的对象，同时优先选择替换掉无效条目。

我们简要介绍了Gem5中实现的替换策略。如果需要进一步了解，可以参考Cache Replacement Policies Wikipedia页面或相关论文。

一、Random

随机（Random）是一种最简单的替换策略，它不依赖于任何替换数据或者访问模式。在发生缺失需要进行替换时，随机替换策略会在所有的替换候选项中随机选择一个替换数据块。

这种策略的优势在于它的实现简单且成本低，因为不需要维护额外的替换数据结构。它可以适用于一些不需要特定的替换策略的场景，或者作为其他更复杂替换策略的基准进行比较。

然而，随机替换策略也存在一些缺点。由于其随机性质，它无法利用访问模式或者替换数据的信息，因此可能无法充分优化缓存的命中率。在某些情况下，随机替换策略可能会导致频繁替换频繁访问的数据块，从而降低缓存性能。

二、Least Recently Used (LRU)

最近最少使用（LRU）是一种替换策略，其替换数据包括最后访问时间戳，记录最后一次访问该条目的时间。当需要替换时，LRU替换策略会选择具有最早最后访问时间戳的条目作为替换数据块。

该策略的原理是，根据时间戳可以推测出最近被访问的数据块相对较新，而较长时间未被访问的数据块相对较旧。因此，最早被访问的数据块是最有可能在未来较长时间内不再被访问的，所以选择它作为替换数据块是合理的。通过基于最后访问时间戳选择替换数据块，LRU替换策略可以充分利用访问模式的局部性原理，即最近被访问的数据块在未来也可能被频繁访问。这有助于提高缓存的命中率，使得常被访问的数据块能够长时间保留在缓存中，提高访问性能。

然而，LRU替换策略也有一些限制。维护时间戳需要额外的开销，并且在高并发的情况下，更新时间戳可能会引入竞争条件。此外，对于具有周期性访问模式或者突发访问的数据块，LRU可能无法有效地适应其访问模式。

三、Tree Pseudo Least Recently Used (TreePLRU)

TreePLRU是对LRU替换策略的改进。它通过使用二叉树和1位指针来管理和跟踪缓存条目的使用情况。

TreePLRU的核心思想是将缓存条目组织成二叉树结构，并使用1位指针来表示每个节点的状态。二叉树的叶子节点表示缓存条目，而非叶子节点表示缓存条目的组合。通过在每个节点上设置1位指针，可以表示该节点的子节点中哪个子节点最近被访问过。当需要进行替换时，TreePLRU会根据节点的1位指针来选择替换数据块。具体选择的方法是从根节点开始，根据节点的1位指针选择下一个节点，直到到达叶子节点，该叶子节点即为需要替换的数据块。

通过使用二叉树和1位指针来管理替换数据，TreePLRU能够更高效地跟踪和更新条目的使用近期性。相比传统的LRU实现，它节省了额外的时间和空间开销。

然而，TreePLRU也有一些限制。由于使用二叉树结构，它需要维护和更新树的指针，这可能会引入一些复杂性和开销。此外，TreePLRU对于大型缓存和高并发访问的情况可能不够高效。

四、Bimodal Insertion Policy (BIP)

BIP是一种改进的替换策略，它在LRU的基础上引入了概率性的MRU插入。每个块在被插入缓存时，根据双模节流参数（btp）确定以MRU方式插入的概率。

双模节流参数（btp）是一个控制插入策略的参数，它决定了新块以MRU方式插入的可能性。较高的btp值表示更高的插入概率，即新块更有可能以MRU方式插入。换句话说，btp决定了新块插入时被放置的位置，越高的btp值表示新块更有可能被放置在最近最少使用的位置。

使用BIP策略时，较高的btp值可以增加新块以MRU方式插入的概率，这意味着最近访问的块可能会更长时间地保留在缓存中。这可以提高缓存的命中率，从而提高系统的性能。

然而，需要注意的是，较高的btp值也可能导致缓存中的块长时间保留，导致较少访问的块很难进入缓存。因此，在选择适当的btp值时需要进行权衡，以获得最佳的缓存性能。

五、LRU Insertion Policy (LIP)

LIP是一种改进的替换策略，它基于LRU替换策略的基本原则，但在插入新块时有所不同。通常，在LRU中，新块会被插入到最近使用的位置（MRU），以便它们有更高的机会在未来被频繁访问。然而，在LIP中，新块被插入到最近最少使用的位置（LRU），即最不可能被访问的位置。

当新块被插入到LRU位置时，它们的时间戳会被更新为MRU，以便在后续访问中正确反映它们的使用频率。这样，当新块被重复访问时，它们将逐渐向MRU位置移动，直到它们成为最近访问的块。

LIP也可以被视为BIP的一种特殊情况，其中将插入新块作为最近使用的可能性设置为0%。在BIP中，插入新块的概率可以根据双模节流参数进行调整，而在LIP中，新块始终以LRU方式插入，不考虑最近使用的可能性。

LIP的优点是它简化了插入策略，减少了实现的复杂性，并且在某些情况下可能提供更好的性能。然而，它可能会导致缓存中的新块较少，因为它们总是以LRU方式插入。

六、Most Recently Used (MRU)

MRU替换策略是一种基于使用频率的缓存替换策略。它与LRU（最近最少使用）相反，LRU策略选择的是最久未被使用的条目进行替换，而MRU策略选择的是最近被使用的条目进行替换。

在MRU策略中，条目的"新鲜度"越高，即最近被使用的时间越近，它们越有可能成为替换数据块。这意味着，相对较新的条目会更容易被替换，而相对较旧的条目会更有可能保留在缓存中。

这种策略的目的是优先保留最近使用的条目，以便它们在未来可能再次被访问。较新的条目通常被认为是在短期内更有可能被频繁访问的，因此将它们视为替换数据块可以提供更好的缓存性能。

然而，MRU策略也有一些局限性。由于它偏向保留较新的条目，可能会导致较旧但仍然频繁访问的条目被替换出缓存，从而降低缓存的命中率。这在某些工作负载下可能导致性能下降。

七、Least Frequently Used (LFU)

LFU替换策略是一种基于引用频率的缓存替换策略。它根据条目被访问的次数选择替换数据块，而不考虑这些访问发生的时间或距离上次访问的时间有多久。

在LFU策略中，每当一个条目被访问时，其引用计数会增加。当缓存空间不足时，LFU策略会选择引用计数最低的条目作为替换块，即最不经常被引用的条目。这样做的目的是尽可能保留经常被访问的条目，以提高缓存的命中率。

LFU策略可以很好地适应访问模式发生变化的情况。一旦某个条目不再被访问，其引用计数会逐渐降低。在未来如果该条目再次被访问，它的引用计数将重新增加，使其有机会被保留在缓存中。

然而，LFU策略也有一些局限性。如果某个条目在缓存中一直存在但很少被访问，它的引用计数可能始终较低，导致它很难被保留在缓存中。此外，LFU策略需要维护每个条目的引用计数，这可能需要额外的计算和存储开销。

八、First-In, First-Out (FIFO)

FIFO算法按照数据进入缓存的顺序确定替换顺序。当缓存已满且需要插入新数据时，最早进入缓存的数据将被替换出去，为新数据腾出空间。这是因为最早进入缓存的数据在时间上最久远，很可能是最不常使用的数据。

FIFO算法的优点是实现简单，容易理解和预测。然而，它也有一些缺点。由于只考虑了数据的插入时间，而没有考虑数据的访问频率和重要性，FIFO算法可能会导致缓存命中率较低。如果某个数据在一开始被频繁访问，但随后很少被使用，它仍然会一直留在缓存中，占用宝贵的空间，而更重要的数据可能无法被缓存。

九、Second-Chance

Second-Chance替换策略是一种基于FIFO的缓存替换策略。它引入了一个"第二次机会"的概念，以允许某些即将被替换的条目有机会继续留在缓存中。在Second-Chance策略中，每个条目都有一个额外的位，通常称为"第二次机会位"（second chance bit）。当一个条目被插入到缓存中时，它的第二次机会位被设置为1。当需要替换一个条目时，首先检查队列的第一个条目。如果该条目的第二次机会位为1，表示它已经得到了第二次机会，那么该位会被清除，并将该条目重新插入到FIFO队列的末尾。如果第一个条目的第二次机会位为0，表示它没有得到第二次机会，那么该条目会被替换。

当发生缺失（miss）时，即需要插入一个新的条目时，该条目的第二次机会位会被清除，以确保该条目在下一次替换时不会得到第二次机会。

Second-Chance策略允许某些即将被替换的条目有机会继续留在缓存中。如果一个条目在第一次机会时没有被访问，但在第二次机会时被访问到，它的第二次机会位将被设置为1，从而使其有机会继续存在于缓存中。

十、Not Recently Used (NRU)

NRU算法通过维护每个块的一个比特位来估计块的最近使用情况。当需要替换一个块时，NRU算法会优先选择那些比特位为1的块，因为它们可能已经较久没有被引用，有较高的可能性不会在短时间内被再次引用。

在NRU算法中，当一个块被替换时，所有与其一起可能被替换的块都会使其重新引用比特位递增。这是为了确保被替换的块在下一轮替换时有更高的机会被选择，从而避免频繁替换同一块。

NRU算法的优点是实现相对简单，且能够在一定程度上近似LRU算法。然而，由于它只使用了一个比特位来判断块的使用情况，因此无法提供精确的LRU替换策略。在某些情况下，NRU算法可能会导致较低的缓存命中率。

十一、Re-Reference Interval Prediction (RRIP)

Re-Reference Interval Prediction（RRIP）是一种用于缓存替换策略的扩展，它是基于NRU（Not Recently Used，最近未使用）策略的改进。RRIP引入了重新引用预测值（RRPV），用于预测块是否在不久的将来会被重新访问。

在RRIP中，每个缓存块都被分配一个RRPV值。初始时，所有的RRPV值被设置为最大值。当一个块被访问时，它的RRPV值会被重新设置为最小值。当需要替换一个块时，通过检查所有块的RRPV值来确定被替换的块。如果存在至少一个块的RRPV值为最大值，那么选择其中一个RRPV值为最大的块进行替换。如果所有块的RRPV值都不是最大值，那么选择RRPV值最小的块进行替换。

RRPV的值表示块距离下一次访问的间隔。值越高，表示块与下一次访问的间隔越远，即块越不可能在不久的将来被重新访问。通过使用RRPV值，RRIP可以更好地预测块是否会被重新使用，并相应地进行替换。

Static RRIP（SRRIP）是RRIP的一种实现方式，它总是以相同的RRPV值插入块。在SRRIP中，所有块的初始RRPV值都设置为最大值。当一个块被访问时，它的RRPV值被重新设置为最小值。这种实现方式简化了RRIP的操作，并且在实际应用中具有较好的性能。

十二、Bimodal Re-Reference Interval Prediction (BRRIP)

Bimodal Re-Reference Interval Prediction（BRRIP）是对RRIP策略的进一步扩展，它采用了Bimodal Insertion Policy的思想。BRRIP引入了一个概率控制机制，用于决定是否插入块，这与LRU策略中的不插入块的概率相似。这个概率由双模态节流参数（btp）控制。

在BRRIP中，每个缓存块都有一个重新引用预测值（RRPV），用于预测块是否会在不久的将来重新访问。与RRIP类似，RRPV值越高表示块与下一次访问的间隔越远。然而，BRRIP通过引入双模态节流参数（btp）来控制插入块的概率。

btp参数可以取0或1两个值，分别表示插入块的概率为0和1。当btp参数为0时，BRRIP的行为类似于LRU，即不插入块。当btp参数为1时，BRRIP的行为类似于RRIP，按照RRPV值进行插入和替换。通过调整btp参数，可以在BRRIP中控制插入块的概率，从而平衡缓存的性能和命中率。

BRRIP的双模态节流参数提供了一种灵活的机制，可以在不同的工作负载和访问模式下调整插入块的概率。根据具体的应用场景和性能需求，可以调整btp参数以适应不同的情况。