Caching

Question 1

What are two kinds of cache locality?

Answer 1

spatial locality
temporal locality

Question 2

What is fully associative mapping in caches?What are the advantages and disadvantages?

Answer 2

Full associative is when any block of memory can be loaded in any line in the cache.
Advantage: Most flexible, high
Disadvantage: Most expensive since all the tags need to be checked in parallel

Question 3

What is direct-mapped in caches? What are the advantages and disadvantages?

Answer 3

A block in memory can only be placed in 1 particular line given by (block number % no. of lines)
Disadvantage: Least flexible
Advantage: Least expensive (need to only check 1 tag per access)

Question 4

What is common among blocks in a set?

Answer 4

(Block number % no. of sets) is the same. As a result, the occupy the same set and we only need to search each way within a set

Question 5

Explain the pseudo LRU replacement method.

Answer 5

There is 1 bit reserved for each way in a set. When each way is accessed, set its bit.
If all bits are in a set are 1, reset all but the last accessed
Replace a block with an unset bit

Question 6

LRU is the best cache replacement policy for _______________

Answer 6

small caches

Question 7

LRU and random replacement are similar for __________________

Answer 7

large caches

Question 8

List the replacement policies from best to worst for small caches? Large caches?

Answer 8

Small: LRU, FIFO, Random
Large: LRU and Random, FIFO

Question 9

What are the two types of write policies? Define each one

Answer 9

1. Write-through: Everytime the cache is modified, send it to the lower level.
2. Write-back: Only modify the cache and set the dirty bit. The block is written back to the lower level when replaced (only if dirty bit is set)

Question 10

What is the advantage of write-through cache policy?

Answer 10

Simplifies coherency

Question 11

List one way of measuring memory performance

Answer 11

Count the number of stalls at commit

Question 12

What is a “compulsory” miss?

Answer 12

The first time a block is accessed, it won’t be in the cache. It will need to be added and will always be a miss

Question 13

What is a “capacity” miss?

Answer 13

The whole program can’t be fit into the cache so blocks are replaced and retrieved again

Question 14

What is a “conflict” miss?

Answer 14

When there is a miss because there is a finite number of blocks in a set. Otherwise wouldn’t occur in a fully associative cache

Question 15

What is a “coherence” miss?

Answer 15

When blocks get invalidated because another core is writing/has written to it

Question 16

What stages can a cache lookup be broken into in order to make a pipelined cache?

Answer 16

set select, tag search, data read, return data

Question 17

How can increasing block size lead to cache misses?

Answer 17

Large blocks can lead to conflict misses (due to lower associativity) or capacity misses (due to unused blocks in the cache).

Question 18

How does critical word first work?

Answer 18

If an address is requested, and it indexes the middle of a block, the memory burst starts from the requested word and provides the block, wrapping around to the front of the block. The result burst order could look something like 4, 5, 6, 7, 0, 1, 2, 3
The cache then reassembles the block in order

Question 19

What is early restart?

Answer 19

The requested data is passed to the processor as soon as it arrives (while the block is still filling)