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 hit rate
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

How do you find the number of offset bits in the address?

Answer 4

no. of offset bits = log2(block size)

Question 5

How do you find the number of index bits in an address?

Answer 5

For direct-mapped
no. of index bits = log2(no. of lines)

For set-associative:
no. of index bits = log2(no. of sets)

Question 6

What 3 components is an address broken down into when searching caches?

Answer 6

1. tag
2. index
3. offset

Question 7

What is the correlation between the no. of pages and the size of the page table (in rows/no. of entries)?

Answer 7

The no. of pages = no. of rows in page table

Question 8

What is common among blocks in a set?

Answer 8

(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

Edit: The block index is the same

Question 9

Explain the pseudo LRU replacement method.

Answer 9

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 10

LRU is the best cache replacement policy for _______________

Answer 10

small caches

Question 11

LRU and random replacement are similar for __________________

Answer 11

large caches

Question 12

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

Answer 12

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

Question 13

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

Answer 13

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 14

What is the advantage of write-through cache policy?

Answer 14

Simplifies coherency

Question 15

List one way of measuring memory performance

Answer 15

Count the number of stalls at commit

Question 16

What is a “compulsory” miss?

Answer 16

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 17

What is a “capacity” miss?

Answer 17

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

Question 18

What is a “conflict” miss?

Answer 18

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

(When blocks share a set)

Question 19

What is a “coherence” miss?

Answer 19

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

Question 20

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

Answer 20

set select, tag search, data read, return data

Question 21

How can increasing block size lead to cache misses?

Answer 21

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

Question 22

How does critical word first work?

Answer 22

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 23

What is early restart?

Answer 23

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

Question 24

What is the most common virtual memory and cache combo?

Answer 24

VI/PT (Virtually Indexed, Physically Tagged)

Question 25

What is a problem with VI/PT virtual memory and cache?

Answer 25

Synonym Problem: Block shared with multiple processes assigned different virtual addresses

Question 26

What is the Homonym problem

Answer 26

Problem from VI/VT. Some virtual tag can reference multiple memory blocks.

Question 27

What is Content Addressable Memory used for? How does it work?

Answer 27

CAM is used for parallel tag checking in high associativity caches.
It uses matchlines that are precharged high. A search term (and its complement) is broadcast on the searchlines. If there is a mismatch, the cell discharges the matchline to ground

Question 28

What is the benefit to physically tagged, physically indexed? Drawback?

Answer 28

Benefit: Simple
Drawback: Slow due to translation

Question 29

What is the benefit to virtually indexed, physically tagged? Drawback?

Answer 29

Benefit: Faster since we can do cache lookup while translating
Drawback: Synonym problem

Question 30

What is the synonym problem w.r.t. virtual address translation?

Answer 30

Different processes using same block leads to duplicated blocks because they have different virtual addresses

Question 31

How is the synonym problem solved?

Answer 31

Page coloring. The OS assigns virtual page numbers s.t. the lower order bits used for the index are the same

Question 32

What is the homonym problem?

Answer 32

The same virtual tag can reference multiple memory blocks

Question 33

How is the homonym problem solved?

Answer 33

Adding an address space id (asid) or pid to the tags in order differentiate