CMPSC 311 Test 2 Caching Flashcards
cache
—- a smaller, faster storage device that acts as a staging area for a subset of the data in a larger, slower device.
faster, smaller, larger, slower
fundamental idea of a memory hierarchy: For each k, the —–, —– device at level k serves as a cache for the —–, —– device at level k + 1
locality, k, k + 1, slower, bit
Why do memory hierarchies work? because of ——, programs tend to access the data at level — more often than they access the data at level ——. thus storage at level k + 1 can be —-, and thus larger and cheaper per —–
storage, bottom, data, top
big idea of caches: The memory hierarchy creates a large pool of —- that costs as much as the cheap storage near the —-, but that serves —- to programs at the rate of the fast storage near the ——
layers, processors
Most modern computers have multiple —— of caches to manage data passing into and out of the ——-
L1
cache levels:
—–: very fast and small, processor adjacent
L2
cache levels:
—: a bit slower but often much larger
L3
cache levels:
—-: larger still, maybe off chip. May be shared amongst processors in multi-core system.
Memory
cache levels:
—–: slowest, least expensive
Instruction, data
—- caches are different from —– caches
registers, L1, L2, main memory, local secondary storage, remote secondary storage
memory hierarchy top to bottom order
locality
caches exploit —– to improve performance, of which there are two types.
spatial locality
—— —-: accessed data used is tend to be close to data you already accessed
temporal (time) locality
—– —- —: data that is accessed is likely to be accessed again soon
spatial
two cache design strategies:
—–: cache items in blocks larger that accessed
temporal
two cache design strategies:
—-: keep stuff used recently around longer
subset, data, blocks
general cache concepts:
smaller, faster, more expensive memory caches a—— of the blocks.
—– is copied in block-sized transfer units
Larger, slower, cheaper memory viewed as partitioned into —–
Hit
Data in block b is needed, block b is in cache: —–
miss , memory, cache
data in block b is needed, block b is not in cache: —–
block b is fetched from ——
block b is stored in —-
placement policy
—— —-: determines where b goes in cache
replacement policy, victim
—— —–: determines which block gets evicted (called the ——)
fully associative
Placement policy: anywhere = ——— ——-
direct-mapped, mod
Placement policy: exactly one cache line (—– ——-).
commonly, block i is mapped to cache line (i — t) where t is the total number of lines
n-way set associative
Placement policy: one of n cache lines (— – —- —)
cold (compulsory) miss
cache miss:
—– —– —: cold misses occur because the cache is empty
capacity miss, working set
cache miss:
—- –: occurs when the set of active cache blocks (—– —) is larger than the cache
conflict miss, set-associative, direct mapping
cache miss:
— —– (—– — and —- —– only)
Most cache limits blocks at level k + 1 to a small subset (sometimes a singleton) of the block positions at level k. Eg Block i at level k+1 must be placed in block (i mod 4) at level k.
conflict misses
—— —- occur when the level k cache is large enough, but multiple data objects all map to the same level k block.
evict
When your cache is full and you acquire a new value, you must —- a previously stored value.
cache eviction policy
Performance of cache is determined by how smart you are in evicting values, known as —– —– —-
lest recently used (LRU)
popular policies:
—— —- —-: eject the value that has been in the cache the longest without being accessed
least frequently used (LFU)
popular policies:
—– —– —-: eject the value that accessed the least number of times
first in first out (FIFO)
popular policies:
— — —– —-: eject the same order they come in
hit performance, costs, working, workload
Policy efficiency is measured by the —– ——- (how often is something asked for and found) and measured ——
determined by —– set and ——
cache hit
A —– —- is when the referenced information is served out of the cache
cache miss
a —– —- occurs referenced information cannot be served out of the cache
hit ratio
the – —- is the #cache hits/ # total accesses
cache hits/ #total accesses
hit ratio is : ——
hit ratio
Note that the efficiency of a cache is almost entirely determined by the — —-
average memory access time
The —- —- —- — can be calculated: memory latency -= hit cost + p(miss) * miss penalty
memory latency = hit cost + p(miss) * miss penalty
average memory access time equation : ———-
hit cost
avg mem access time equation:
—— —: is the cost to access the cache
miss penalty
avg mem access time equation:
—- —- is the cost to serve out of main memory
P(miss)
avg mem access time equation:
——- is the probability of a cache access resulting in a miss e.g., 1 - hit ratio
