CMPSC 311 Test 2 Caching

Question 1

cache

Answer 1

—- a smaller, faster storage device that acts as a staging area for a subset of the data in a larger, slower device.

Question 2

faster, smaller, larger, slower

Answer 2

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

Question 3

locality, k, k + 1, slower, bit

Answer 3

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 —–

Question 4

storage, bottom, data, top

Answer 4

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 ——

Question 5

layers, processors

Answer 5

Most modern computers have multiple —— of caches to manage data passing into and out of the ——-

Question 6

L1

Answer 6

cache levels:

—–: very fast and small, processor adjacent

Question 7

L2

Answer 7

cache levels:

—: a bit slower but often much larger

Question 8

L3

Answer 8

cache levels:

—-: larger still, maybe off chip. May be shared amongst processors in multi-core system.

Question 9

Memory

Answer 9

cache levels:

—–: slowest, least expensive

Question 10

Instruction, data

Answer 10

—- caches are different from —– caches

Question 11

registers, L1, L2, main memory, local secondary storage, remote secondary storage

Answer 11

memory hierarchy top to bottom order

Question 12

locality

Answer 12

caches exploit —– to improve performance, of which there are two types.

Question 13

spatial locality

Answer 13

—— —-: accessed data used is tend to be close to data you already accessed

Question 14

temporal (time) locality

Answer 14

—– —- —: data that is accessed is likely to be accessed again soon

Question 15

spatial

Answer 15

two cache design strategies:

—–: cache items in blocks larger that accessed

Question 16

temporal

Answer 16

two cache design strategies:

—-: keep stuff used recently around longer

Question 17

subset, data, blocks

Answer 17

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 —–

Question 18

Hit

Answer 18

Data in block b is needed, block b is in cache: —–

Question 19

miss , memory, cache

Answer 19

data in block b is needed, block b is not in cache: —–

block b is fetched from ——

block b is stored in —-

Question 20

placement policy

Answer 20

—— —-: determines where b goes in cache

Question 21

replacement policy, victim

Answer 21

—— —–: determines which block gets evicted (called the ——)

Question 22

fully associative

Answer 22

Placement policy: anywhere = ——— ——-

Question 23

direct-mapped, mod

Answer 23

Placement policy: exactly one cache line (—– ——-).

commonly, block i is mapped to cache line (i — t) where t is the total number of lines

Question 24

n-way set associative

Answer 24

Placement policy: one of n cache lines (— – —- —)

Question 25

cold (compulsory) miss

Answer 25

cache miss:

—– —– —: cold misses occur because the cache is empty

Question 26

capacity miss, working set

Answer 26

cache miss:

—- –: occurs when the set of active cache blocks (—– —) is larger than the cache

Question 27

conflict miss, set-associative, direct mapping

Answer 27

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.

Question 28

conflict misses

Answer 28

—— —- occur when the level k cache is large enough, but multiple data objects all map to the same level k block.

Question 29

evict

Answer 29

When your cache is full and you acquire a new value, you must —- a previously stored value.

Question 30

cache eviction policy

Answer 30

Performance of cache is determined by how smart you are in evicting values, known as —– —– —-

Question 31

lest recently used (LRU)

Answer 31

popular policies:

—— —- —-: eject the value that has been in the cache the longest without being accessed

Question 32

least frequently used (LFU)

Answer 32

popular policies:

—– —– —-: eject the value that accessed the least number of times

Question 33

first in first out (FIFO)

Answer 33

popular policies:

— — —– —-: eject the same order they come in

Question 34

hit performance, costs, working, workload

Answer 34

Policy efficiency is measured by the —– ——- (how often is something asked for and found) and measured ——

determined by —– set and ——

Question 35

cache hit

Answer 35

A —– —- is when the referenced information is served out of the cache

Question 36

cache miss

Answer 36

a —– —- occurs referenced information cannot be served out of the cache

Question 37

hit ratio

Answer 37

the – —- is the #cache hits/ # total accesses

Question 38

cache hits/ #total accesses

Answer 38

hit ratio is : ——

Question 39

hit ratio

Answer 39

Note that the efficiency of a cache is almost entirely determined by the — —-

Question 40

average memory access time

Answer 40

The —- —- —- — can be calculated: memory latency -= hit cost + p(miss) * miss penalty

Question 41

memory latency = hit cost + p(miss) * miss penalty

Answer 41

average memory access time equation : ———-

Question 42

hit cost

Answer 42

avg mem access time equation:

—— —: is the cost to access the cache

Question 43

miss penalty

Answer 43

avg mem access time equation:

—- —- is the cost to serve out of main memory

Question 44

P(miss)

Answer 44

avg mem access time equation:

——- is the probability of a cache access resulting in a miss e.g., 1 - hit ratio