THE FOLD / GRIND / WARM CACHE / THE VICTIM CACHE
THE VICTIM CACHE
four entries that fix what doubling the ways does not
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Norman Jouppi, 1990: keep a tiny fully-associative buffer beside a direct-mapped cache and catch the lines it throws away. Four extra entries. It fixes a failure that doubling the associativity does not.
LIT verified live. on a trace of 999 accesses cycling three addresses that all map to the same set, the direct-mapped cache misses 999 of 999. A 2-way set-associative cache of the same total capacity also misses 999 of 999 — three lines will not fit in two ways, no matter how the ways are arranged. The direct-mapped cache with a 4-entry victim buffer misses 3: the compulsory ones. The victim buffer supplied 996 hits. On a purely streaming trace of the same length it supplies 0.
LIT verified live. on a trace of 999 accesses cycling three addresses that all map to the same set, the direct-mapped cache misses 999 of 999. A 2-way set-associative cache of the same total capacity also misses 999 of 999 — three lines will not fit in two ways, no matter how the ways are arranged. The direct-mapped cache with a 4-entry victim buffer misses 3: the compulsory ones. The victim buffer supplied 996 hits. On a purely streaming trace of the same length it supplies 0.
2 HOW IT WAS WEAVED · AI + HUMAN
Norman Jouppi’s 1990 ISCA paper introduced the victim cache; the mechanism and the motivation are his.
AVAN (AI) added the control that makes the claim mean something. It is easy to show a victim cache beating a direct-mapped cache — that only proves you added capacity. So the 2-way comparison was run at equal total lines, and it fails just as completely: 999 of 999. The victim buffer is not extra associativity spread thin, it is full associativity concentrated exactly where the conflicts land. The streaming control (0 victim hits) is the other half: on a trace with no conflicts the whole structure is dead silicon.
AVAN (AI) added the control that makes the claim mean something. It is easy to show a victim cache beating a direct-mapped cache — that only proves you added capacity. So the 2-way comparison was run at equal total lines, and it fails just as completely: 999 of 999. The victim buffer is not extra associativity spread thin, it is full associativity concentrated exactly where the conflicts land. The streaming control (0 victim hits) is the other half: on a trace with no conflicts the whole structure is dead silicon.
3 ONE DIMENSION
Three addresses, one set. Two ways is not enough.
4 TWO DIMENSIONS · INTERACTIVE
Step the trace and watch the victim buffer catch the evictions.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that four entries fix a pathology eight would not. The inverse is that the fix is a bet on clustering, and the bet is invisible until it loses. The victim buffer works because conflict misses are rare but bunched — a handful of addresses colliding again and again. Run a trace with no conflicts and it returns 0 hits while still burning area, power and a lookup on every miss. Read backwards, this is not a cache improvement; it is a wager about the shape of someone else’s access pattern, placed at design time, settled years later in silicon that cannot be changed.
LIT on 999 accesses cycling three addresses that map to one set, the direct-mapped cache misses 999 of 999 and a 2-way cache of the SAME total capacity also misses 999 of 999 - three lines will not fit in two ways however they are arranged - while direct-mapped plus a 4-entry victim buffer misses 3, the compulsory ones, with 996 hits supplied by the buffer; on a purely streaming trace of the same length that same buffer supplies 0
FIG Norman Jouppi's 1990 ISCA paper introduced the victim cache. AVAN added the control that makes the claim mean anything: beating a direct-mapped cache only proves you added capacity, so the 2-way comparison was run at equal total lines and fails just as completely, 999 of 999. The streaming control - 0 victim hits - is the other half: on a trace with no conflicts the whole structure is dead silicon.
FIG Norman Jouppi's 1990 ISCA paper introduced the victim cache. AVAN added the control that makes the claim mean anything: beating a direct-mapped cache only proves you added capacity, so the 2-way comparison was run at equal total lines and fails just as completely, 999 of 999. The streaming control - 0 victim hits - is the other half: on a trace with no conflicts the whole structure is dead silicon.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN