在直接映射cache中，当发生miss时，新请求的数据块只能映射到一条特定的cacheline。 在这种情况下，此cacheline的内容将替换为新的内存数据块。
在N路组相联cache中，一组中的N个cacheline可以继续容纳新请求的内存块。 如果组中的所有cacheline都已满，我们将面临替换哪个cacheline的问题。 换句话说，一组中的所有cacheline都可能被替换掉，我们必须选择最合适的行。
当一个公司的坑位满了，公司还需要招聘新的人才，这个时候同样也需要"替换策略"，也许替换掉效率低的，也许是随机的。
组相联cache常常使用最近最少（LRU）算法来确定当将新数据块带入组时，组中的哪条cacheline要被替换。 LRU算法确保替换最长时间未访问的cacheline。 LRU算法背后的关键思想是evict替换最长时间未访问的cacheline，假设在不久的将来不太可能需要最近较少使用的数据。
LRU算法确保cache一直填充着与工作负载最相关的数据，有可能减少cache miss并提高整体cache性能。
换位思考下，作为一个员工尽可能避免去到业务边缘，因为那样你就是"最近最少使用"了。
LRU算法维护每个cache 组最近访问的历史记录。 cache控制器根据访问cacheline更新LRU信息。
最初，一组中的所有cacheline都被认为是最近使用的。 当访问组中的cacheline（用于读取或写入）时，它被标记为最近使用。 组中的其他cacheline也进行调整，以反映其相对的访问时间。 当需要将新数据块带入已满的组时，cache控制器会选择标记为“最近使用最少”的cacheline进行驱逐evict。 然而，实现LRU算法可能相对复杂，需要额外的硬件来跟踪访问历史记录
作者：数字芯片
来源：数字芯片实验室
推荐阅读
更多数字IC设计技术干货等请关注数字芯片实验室专栏。添加极术小姐姐（微信：aijishu20)微信可申请加入IC设计交流群。
