Cache replacement and write policies

Why it exists

Two decisions have to be made on every cache access that does not simply hit. When a block must be brought in and every line of its set is occupied, which line is thrown out? And when the processor writes, is memory updated at once, later, or only when the line is replaced? The first is the replacement policy, the second the write policy. They decide how often the cache misses, how much memory traffic it creates, and whether the memory ever holds stale data. GATE asks for the number of misses of a sequence under a policy, the contents of the cache after some accesses, the number of memory writes, and the properties of the policies.

Prerequisites

You need the structure of the cache (sets, ways, tag, valid bit) from cache mapping.

Precise definitions

Replacement is needed only when the set is full. In a direct-mapped cache there is no choice (one line per set); in a set-associative or fully associative cache one of the $W$ lines of the set must be chosen. A free (invalid) line is always used first.

Policies.

• LRU (least recently used): replace the block that has gone unused for the longest time; exploits temporal locality. Needs the order of use: counters or an ordered list per set; true LRU is costly for large associativity, so hardware often uses an approximation (pseudo-LRU).
• FIFO (first in, first out): replace the block that has been in the set longest, regardless of use. Simple (a pointer or a queue), a hit does not change the order.
• Random: replace a random line. Very cheap; performs about as well as the others for large caches.
• LFU (least frequently used): replace the block with the fewest accesses.
• Optimal (OPT, Belady's MIN): replace the block whose next use is farthest in the future. It needs knowledge of the future so it cannot be built, but it gives the fewest possible misses and is the yardstick.

Properties. For any sequence, OPT misses no more than any other policy. LRU and OPT have the stack (inclusion) property: the contents of a cache with $k$ lines are always contained in the contents of a cache with $k + 1$ lines, so more lines never produce more misses. FIFO does not: on some sequences a bigger cache has more misses (Belady's anomaly).

Write policies on a hit.

• Write-through: every write goes to the cache and to memory. Memory is always up to date, so a replaced block can simply be dropped; but every write costs a memory write (a write buffer hides the delay).
• Write-back (copy-back): a write updates only the cache and sets the line's dirty bit. The block is written to memory only when it is replaced (and only if dirty). Fewer memory writes (many writes to one block become one), but memory may be stale and the replacement of a dirty block costs a write-back.

Write policies on a miss.

• Write-allocate: bring the block into the cache first, then write as on a hit.
• No-write-allocate (write-around): write directly to memory and do not load the block.

Usual pairings. Write-back with write-allocate (locality of writes pays off) and write-through with no-write-allocate (nothing is gained by loading a block that will only be written).

Memory traffic. Count in blocks or words as the question says. Reads: one block fill per miss that allocates a line. Writes: write-through, one memory write per store (hit or miss); write-back, one block write per dirty replacement.

How it works

The reference string 1 2 3 4 1 2 5 1 2 3 4 5 (block numbers) in a fully associative cache of 3 lines. Step through all three policies. FIFO throws out the oldest block even if it is about to be used again; LRU throws out the one not used for the longest time; the optimal policy looks ahead. The final counts are 9 misses for FIFO, 10 for LRU and 7 for OPT. (LRU is not always better than FIFO: on this string it is worse.)

The write policies on a small direct-mapped cache of 4 lines with the operations: write 0, 1, 2, 3 (four writes to one block), read 16 (a different block that maps to the same line), read 0. First write-through with no-write-allocate (4 memory writes, 2 block reads) and then write-back with write-allocate (1 memory write, 3 block reads).

Worked examples

#include <stdio.h>
#include <string.h>
 
#define N 12
static const int seq[N] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
 
/* fully associative cache of `frames` lines; policy 0 = FIFO, 1 = LRU, 2 = optimal */
static int misses(int policy, int frames) {
    int blk[8], stamp[8], n = 0, miss = 0;
    for (int i = 0; i < N; i++) {
        int hit = -1;
        for (int k = 0; k < n; k++) if (blk[k] == seq[i]) hit = k;
        if (hit >= 0) {
            if (policy == 1) stamp[hit] = i;                     /* LRU remembers the last use */
            continue;
        }
        miss++;
        if (n < frames) { blk[n] = seq[i]; stamp[n] = i; n++; continue; }
        int victim = 0;
        if (policy == 2) {                                       /* optimal: the block used farthest in the future */
            int far = -1;
            for (int k = 0; k < n; k++) {
                int next = N + 1;
                for (int j = i + 1; j < N; j++) if (seq[j] == blk[k]) { next = j; break; }
                if (next > far) { far = next; victim = k; }
            }
        } else {                                                 /* FIFO: oldest load time, LRU: oldest use (the stamp) */
            for (int k = 1; k < n; k++) if (stamp[k] < stamp[victim]) victim = k;
        }
        blk[victim] = seq[i]; stamp[victim] = i;
    }
    return miss;
}
 
/* memory traffic of the write policies on a direct-mapped cache of 4 lines of 4 bytes */
static void traffic(int write_back) {
    long blk[4] = { -1, -1, -1, -1 };
    int dirty[4] = { 0, 0, 0, 0 }, reads = 0, writes = 0;
    struct { char op; int addr; } ops[6] = { {'W', 0}, {'W', 1}, {'W', 2}, {'W', 3}, {'R', 16}, {'R', 0} };
    for (int i = 0; i < 6; i++) {
        long b = ops[i].addr / 4;
        int line = (int)(b % 4);
        int hit = blk[line] == b;
        if (!hit && ops[i].op == 'W' && !write_back) { writes++; continue; }     /* write-through, no-write-allocate */
        if (!hit) {
            if (dirty[line]) writes++;                                           /* write the dirty victim back */
            reads++;
            blk[line] = b; dirty[line] = 0;
        }
        if (ops[i].op == 'W') { if (write_back) dirty[line] = 1; else writes++; }
    }
    printf("%-34s memory reads %d, memory writes %d\n", write_back ? "write-back, write-allocate:" : "write-through, no-write-allocate:", reads, writes);
}
 
int main(void) {
    printf("frames  FIFO  LRU  OPT\n");
    for (int f = 1; f <= 6; f++) printf("%6d  %4d  %3d  %3d\n", f, misses(0, f), misses(1, f), misses(2, f));
    printf("FIFO with 3 frames: %d misses, with 4 frames: %d misses (Belady's anomaly)\n", misses(0, 3), misses(0, 4));
    traffic(0);
    traffic(1);
    return 0;
}

frames  FIFO  LRU  OPT
     1    12   12   12
     2    12   12    9
     3     9   10    7
     4    10    8    6
     5     5    5    5
     6     5    5    5
FIFO with 3 frames: 9 misses, with 4 frames: 10 misses (Belady's anomaly)
write-through, no-write-allocate:  memory reads 2, memory writes 4
write-back, write-allocate:        memory reads 3, memory writes 1

Cheat box

Traps and GATE patterns

Connections

The set structure and the address fields are in cache mapping, and the time cost of misses and write-backs is in cache performance. Exactly the same policies and Belady's anomaly appear when the "cache" is main memory and the blocks are pages: page replacement.

PYQs

Consider
two
set-associative
cache
memory
architectures: WBC, which uses the write back
policy, and WTC, which uses the write through
policy. Both of them use the LRU (Least Recently
Used) block replacement policy. The cache memory
is connected to the main memory. Which of the
following statements is/are TRUE?

Let WB and WT be two set associative cache
organizations that use LRU algorithm for cache
block replacement. WB is a write back cache and
WT is a write through cache. Which of the
following statements is/are FALSE?

Assume a two-level inclusive cache hierarchy, L1
and L2, where L2 is the larger of the two. Consider
the following statements.
S1: Read misses in a write through L1 cache do not
result in writebacks of dirty lines to the L2
S2: Write allocate policy must be used in
conjunction with write through caches and no-write
allocate policy is used with writeback caches.
Which of the following statements is correct?

Consider a 2-way set associative cache with 256
blocks and use LRU replacement, initially the
cache is empty. Conflict misses are those misses
which occur due to the contention of multiple
blocks for the same cache set. Compulsory misses
occur due to first time access to the block. The
following sequence of accesses to memory blocks.

{0,128,256,128,0,128,256,128,1,129,257,129,1,12
9,257,129}

is repeated 10 times. The number of conflict
misses experienced by the cache is
.

Consider a 4-way set associative cache (initially
empty) with total 16 cache blocks. The main
memory consists of 256 blocks and the request
for memory blocks are in the following order:
0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155.
Which one of the following memory block will
NOT be in cache if LRU replacement policy is
used?

Consider a 2-way set associative cache memory
with 4 sets and total 8 cache blocks (0–7) and
main memory with 128 blocks (0–127). Which
memory blocks will be present in the cache after
the following sequence of memory block
references if LRU policy is used for cache block
replacement? If initially the cache did not have
any memory block from the current job?

0 5 3 9 7 0 16 55

Self-check

Revision card

References