Advanced Caches

Question 1

Ways to improve cache performance

Answer 1

1. reduce hit time
2. reduce miss rate
3. reduce miss penalty

Question 2

Ways to reduce hit time

Answer 2

1. pipelined caches
2. Improve TLB time
3. Way prediction
4. Improve replacement policy time

Question 3

What are pipelined caches?

Answer 3

Cache accesses are queued, so cannot access the cache while another instruction is accessing it (this can be multiple cycles) ==> instead pipeline the steps to look up an entry in the cache

Question 4

What is a PIPT cache?

Answer 4

Physically-indexed, physically tagged cache. This cache stores the actual physical address. Processor must look up physical address in TLB and then use that address to get the data in the cache

Question 5

What are some potential problems with virtually accessed caches?

Answer 5

• Must flush on context switch because VA are specific to a process
• Need other information from TLB on cache hits (such as does this process have permission to access this page)

Question 6

What is a VIPT cache?

Answer 6

Virtually Indexed - Physically Tagged Cache.
Cache uses virtual index to get physical tag.
At the same time. TLB uses virtual index to get physical tag.
If the tags match, then it is a hit
Do not need to flush on context switch

Question 7

What is cache aliasing?

Answer 7

In a VIPT cache, multiple virtual addresses might map to the same physical address, but will get store in the cache in different locations (because they are stored based on virtual address)

Question 8

Why is cache aliasing bad?

Answer 8

On a write, only one location will be updated

Question 9

How can we ensure that we do not have aliasing?

Answer 9

All of the index bits must come from the page offset. AKA (cache offset) + index <= page offset

Question 10

What is way prediction?

Answer 10

We try to guess which line in the set has the correct tag. If we miss, we do a normal check of the rest of the lines in the set.

Question 11

What is the relationship between associativity and hit time?

Answer 11

As associativity goes up, hit rate goes up, but hit time goes up ==> need to balance associativity

Question 12

What is wrong with LRU and random for replacement polcies?

Answer 12

• Random - nothing to update on cache hit, but has higher miss rate
• LRU - need to update lots of counters on cache hit, but lower miss rate

Question 13

What are some alternatives for LRU?

Answer 13

NMRU and PLRU

Question 14

What is PLRU?

Answer 14

Every time a line is accessed, set bit to 1. If we need to remove something, remove a 0. Once all the bits have been set, zero out all bits except the last one. Better than NMRU, not as good as LRU

Question 15

What are the three types of misses?

Answer 15

Compulsory, capacity (because of limited cache size), and conflict (because of low associativity)

Question 16

How to reduce the miss rate?

Answer 16

• larger cache blocks
• prefetching
• hardware prefetching
• loop interchange

Question 17

What is the relationship between cache block size and the miss rate?

Answer 17

Larger cache blocks reduce the miss rate, but only when spatial locality is good.
Graph of block size vs miss rate is smiley face because eventually the program will not have good enough locality

Question 18

What is prefetching?

Answer 18

Trying to guess which blocks will be needed next and loading them into the cache ahead of time

Question 19

What is cache pollution?

Answer 19

When the cache is polluted with junk blocks that we don’t need. Can be caused by bad prefetching. Can also cause a second cache miss because we evicted a block we needed to fetch some junk

Question 20

What are prefetch instructions and what are the downsides to using them?

Answer 20

A hardware instruction that tells the cache to prefetch data before it is used. They are hard to program correctly because it is hard to guess how long it will take to fetch data.

Question 21

What are the types of hardware prefetching?

Answer 21

Stream buffer, stride prefetcher, correlating prefetcher

Question 22

What is a stream buffer?

Answer 22

hardware prefetching that tries to fetch the next physical block after the one we just accessed

Question 23

What is stride prefetching?

Answer 23

Guesses next block based on address difference (stride) between previous blocks (Aka just looks for a pattern of adding 3)

Question 24

What is correlating prefetching and what is it good for?

Answer 24

remembers different patterns than stride and stream. (if we fetch A then B, then next time we fetch A, fetch B). good for linked lists.

Question 25

What is loop interchange?

Answer 25

• Compiler optimization to increase locality
• In a nested loop, swap the inner and outer loop so that we are iterating over a contiguous block of memory
• Not always possible => swapped code must be the same (prove by ensuring there are no dependencies between loops)

Question 26

How to reduce the miss penalty?

Answer 26

Overlap miss and cache hierarchy

Question 27

How to overlap misses?

Answer 27

Have a non-blocking cache that supports:
hit under miss: allow other hits to happen while we are fetching a miss
miss under miss: while we are fetching a miss, allow misses for other blocks to be fetched

Question 28

How to implement miss under miss?

Answer 28

Requires hardware support - Miss Status Handling Registers (MSHR) - keeps track of which fetches are currently in progress

Question 29

What is a miss vs half miss?

Answer 29

A miss would occur in a blocking cache, a half miss can only occur in a non-blocking cache and occurs when we miss on a block that we are already fetching

Question 30

What is the cache hierarchy?

Answer 30

L1, L2…LLC

Question 31

What is the local hit rate?

Answer 31

hit rate that the cache observes (i.e. only looking at requests that come to this level cache, what is the hit rate?)

Question 32

What is the global hit rate?

Answer 32

the overall hit rate of the entire cache

Question 33

What is MPKI?

Answer 33

Misses per 1000 instructions. another metric to use to describe overall hit rate of the entire cache

Question 34

What is inclusion?

Answer 34

If there is a block in L1, then it must be in L2

Question 35

What is exclusion?

Answer 35

If there is a block in L1, then is must NOT be in L2

Question 36

Do we prefer inclusion or exclusion?

Answer 36

Inclusion, better for write-backs