Simplescalar缓存LRU实现

Question

我在cache.c文件中查找LRU代码，但这是我能找到的唯一代码：

switch (cp->policy) {

  case LRU:

  case FIFO:

    repl = cp->sets[set].way_tail;
    update_way_list(&cp->sets[set], repl, Head);
    break;

在我看来缺少LRU代码，我认为应该把LRU算法放在冒号后面。所以如果我错过了什么，你能给我指出正确的方向或给我一些提示吗？

非常感谢。

Answer 1

我以前碰巧用过Simplescalar。实际上，Simplescalar已经实现了真正的LRU算法。

下面的注释清楚地描述了函数update_way_list。

/* insert BLK into the order way chain in SET at location WHERE */
static void
update_way_list(struct cache_set_t *set,        /* set contained way chain */
                struct cache_blk_t *blk,        /* block to insert */
                enum list_loc_t where)          /* insert location */

您引用的代码来自访问缓存时的“缓存未命中”情况：

  switch (cp->policy) {
  case LRU:
  case FIFO:
    repl = cp->sets[set].way_tail;
    update_way_list(&cp->sets[set], repl, Head);
    break;
  }

在这里，集合的最后一条路被选为受害者，并被移动到集合的头部。随后，将被替换的块数据写回，然后用新的数据块替换牺牲品。

区别LRU和FIFO的最重要部分来自“缓存命中”情况：

  /* if LRU replacement and this is not the first element of list, reorder */
  if (blk->way_prev && cp->policy == LRU)
    {
      /* move this block to head of the way (MRU) list */
      update_way_list(&cp->sets[set], blk, Head);
    }

因此，集合中的方法遵循年龄的递减顺序:集合的头部是MRU (最近使用的)块，而尾部是LRU。

这正是真正的LRU算法:当存在缓存命中时，命中的块被提升为MRU方式，同时保持其他块的顺序。当存在高速缓存未命中时，选择LRU块作为牺牲块，并将新块置于MRU方式中。如果我们删除之前的“缓存命中”代码，则不会记录访问历史，并且集合中的路径遵循访问顺序，从而提供FIFO行为。如果我们删除这行

    update_way_list(&cp->sets[set], repl, Head);

在前面的“缓存未命中”代码中，新的块将被放置在LRU路中，从而提供LIP (LRU插入策略)行为。

Answer 2

在看不到其余代码的情况下很难说，但我在这里看到了两种明显的可能性。一种是，正如您所建议的，LRU管理的代码丢失了，可能是由于编辑错误之类的原因。

然而，我认为更有可能的可能性是，对于代码的这一特定部分，LRU和FIFO管理执行相同的事情，因此它们依赖于C switch语句的"fall through“，以便在这种情况下为两者执行相同的代码(但假设其他代码将针对其他策略执行)。

Answer 3

它看起来像代码的其他部分，按照先进先出或cp->sets的顺序对LRU中的条目进行排序，以便无论替换策略是什么，要替换的集合始终是cp->sets[set].way_tail。这两个替换策略仅在使用或添加行时有所不同，而在行被替换时不存在差异。