0

我在 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 算法放在冒号之后。所以如果我错过了什么，你能指出我正确的方向或给我一些提示吗？

非常感谢。

4

3 回答 3

2

It's hard to say without seeing the rest of the code, but I see two obvious possibilities here. One is that, as you're suggesting, the code for LRU management is missing, possibly through something like a mistake in editing.

The possibility I'd consider more likely, however, would be that for this particular part of the code, LRU and FIFO management do the same things, so they're depending on the "fall through" of a C switch statement to have the same code executed for both in this case (but presumably other code will be executed for other policies).

于 2012-03-15T22:13:00.160 回答
1

I happened to use Simplescalar before. Actually, Simplescalar have already implemented the true LRU algorithm.

The following comment clearly describes the function 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 */

The code that you cited is from the "cache miss" case when the cache is accessed:

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

Here the last way of the set is chose as victim and it is moved to the Head of the set. Later the replaced block data is written back and then the victim is replaced by the new data block.

The most important part that distinguishes LRU and FIFO comes from the "cache hit" case: 

  /* 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);
    }

Therefore, the ways in a set are following the decreasing order of age: The head of the set is the MRU (Most Recently Used) block while the tail is the LRU.

This is exactly the true LRU algorithm: When there is a cache hit, the hit block is promoted to the MRU way while preserving the order of others. When there is a cache miss, the LRU block is chosen as victim and the new block is placed in the MRU way. If we remove the previous "cache hit" code, no access history is recorded and the ways in a set are following the access order, thus providing FIFO behavior. If we remove the line

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

in the previous "cache miss" code, then the new block will be placed in the LRU way, thus providing LIP (LRU Insertion Policy) behavior.

于 2013-05-12T16:29:15.627 回答
0

看起来代码的其他部分以 FIFO 或 LRU 顺序对条目进行排序，以便无论替换策略是什么cp->sets，要替换的集合始终是。cp->sets[set].way_tail这两种替换策略仅在使用或添加线路时有所不同，在线路被替换时没有区别。

于 2012-03-15T22:59:11.987 回答