Victim Caches

About this offer

2. Victim Caches Victim cache holds data that has been deleted from the cache, in case it is needed again This is fully associative cache and can help to reduce misses with direct-mapped or set associative caches A victim cache is a small buffer that sits between a cache and the next level of the memory hierarchy. It catches blocks the main cache has just evicted, so that if the processor asks for one of them again soon, it can be recovered quickly instead of fetched from the slower level below. How it works On a cache miss, the CPU looks in the main cache and, at the same time (or on the very next step), in the victim cache. If the block is in the victim cache (a victim hit), it is swapped with the block currently occupying that line in the main cache. The evicted block goes into the victim cache, and the requested block moves into the main cache. The penalty is only a cycle or two, far less than going to L2 or memory. If it misses in both, the block is fetched from the next level and placed in the main cache. Whatever it displaces is moved into the victim cache, pushing out the oldest entry (typically FIFO or LRU replacement). So blocks flow one way in the normal case: main cache → victim cache → discarded. The swap on a victim hit is the exception. Key properties Small: typically 4 to 16 entries, each holding a full cache block. Fully associative: any evicted block can go in any entry, and lookups compare against all tags in parallel. That is only affordable because it is so small. Holds only evicted blocks: it is not filled directly from memory, so it complements the main cache rather than duplicating it. Exclusive in spirit: a block lives in either the main cache or the victim cache, not both, thanks to the swap. The three cases to remember: Main cache hit: normal fast path, nothing else happens. Main miss, victim hit: swap the two blocks, so the requested block moves into the main cache and the evicted one takes its place in the victim cache. Miss in both: fetch from the next level into the main cache, and the displaced block goes into the victim cache (the oldest victim entry is dropped if it's full). only after update victim cache evict RLL = Read from Lower Level (fetching a block from memory) and WLL = Write to Lower Level (sending data down to memory). These are the two kinds of memory traffic that write policies and victim caches change. If your course defines them differently, tell me and I'll adjust. The four policy terms Two separate questions decide how a cache handles writes: On a write hit, when does memory get updated? Write-back (WB): only the cache is updated, and the block is marked dirty. Memory is updated later, when the dirty block is evicted. Write-through (WT): the cache and memory are both updated on every write. Blocks are never dirty. On a write miss, do we bring the block into the cache? Write-allocate (WA): yes. Read the block from memory (an RLL), then write it in the cache. No-write-allocate (NWA): no. Send the write straight to memory (a WLL) and leave the cache unchanged. These are usually paired. Write-back and write-allocate go together because both try to do writes in the cache instead of in memory, and allocating means a later write to the same block will be a hit. Write-through works naturally with no-write-allocate: every write goes to memory anyway, so loading the block on a write miss gains little Where the victim cache fits The victim cache sits between the main cache and memory and catches evicted blocks. Whether those blocks are dirty depends on the write policy: With WB-WA: evicted blocks may be dirty, so each victim-cache entry needs its own dirty bit. The victim cache becomes a waiting area for dirty data. A dirty block goes to memory (WLL) only when it is pushed out of the victim cache. If it is reused first, the write-back never happens. With WT-NWA: every block is clean, because memory is always up to date. A block leaving the victim cache is simply discarded, with no WLL. The victim cache saves only reads (RLLs). In both policies, a victim-cache hit is a swap. It saves an RLL, and in WB it can also save a WLL. Pick a policy and a situation below to see which paths are used and how many RLLs and WLLs happen. Takeaways for exams WB-WA pays for writes lazily. Repeated writes to one block cost zero WLL until that block finally leaves the victim cache. The victim cache gives dirty blocks a second chance, so it can save both RLLs and WLLs. WT-NWA pays one WLL on every write, hit or miss, and its victim cache can only save RLLs. In return, memory is always up to date and evictions are free. Real designs add a write buffer so the CPU doesn't stall waiting for each WLL. In both policies, a WB-WA write miss costs an RLL (allocate), while a WT-NWA write miss costs a WLL (bypass). Large last-level caches are often managed the same way. L3 is sometimes run as a victim cache, filled only with lines displaced from L2 (for example, AMD Barcelona and Apple A9). Handling dirty lines is a key design issue there too.