Simplescalar cache LRU implementation

Question

I'm looking for the LRU code in the cache.c file, but this is the only code I can find:

switch (cp->policy) {

  case LRU:

  case FIFO:

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

It looks like missing LRU code to me, I thought one should put the LRU algorithm right after colon. So If I missed something, can you point me to the right direction or give me some hints?

Thank you very much.

Answer 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.

Answer 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).

Answer 3

It looks like other sections of the code order the entries in cp->sets in FIFO or LRU order such that the set to be replaced is always cp->sets[set].way_tail no matter what the replacement policy is. The two replacement policies only differ when a line is used or added, and not when the line is replaced.