Memory Hierarchy

Question 1

Draw a diagram of a machine’s memory hierarchy

Answer 1

.

Question 2

Where is SRAM found? What are its characteristics?

Answer 2

On processor chip
Low latency, high bandwidth, size limited by chip area, read/write size can easily be byte level

Question 3

Where is DRAM found? What are its characteristics?

Answer 3

Off chip
Higher latency
High bandwidth
Reads/writes are in small blocks, transferred as burts

Question 4

What type of hardware does page-based virtual memory use? What are its characteristics?

Answer 4

Magnetic hard disk or SSD
High latency, lower bandwidth, reads/writes in larger blocks needed for extensive error detection and correction codes

Question 5

Describe static multiple issue

Answer 5

• Compiler groups instructions to be executed together into “issue slots”
• Compiler detects and avoids hazards

Question 6

Describe dynamic multiple issue

Answer 6

• CPU chooses instructions to issue each cycle
• Compiler can help reorder instructions
• CPU resolves hazards at runtime

Question 7

What is speculation?

Answer 7

Guess what to do with an instruction, start operation asap, check whether guess was right and either complete the sequence or roll-back and do the right thing

Question 8

Give an example of speculation

Answer 8

Speculate on branch outcome - roll back if different path is taken

Question 9

What makes pipelining harder?

Answer 9

Poor ISA design:
1. Complex instruction sets
2. Complex addressing modes
3. Delayed branches

Question 10

What is the principle of locality?

Answer 10

Programs access a small proportion of their address space at any time, giving rise to spatial and temporal locality

Question 11

What is temporal locality?

Answer 11

Items accessed recently are likely to be accessed again soon

Question 12

Give 2 examples of temporal locality

Answer 12

1. Instructions in a loop
2. Loop counters

Question 13

What is spatial locality?

Answer 13

Items near those accessed recently are likely to be accessed soon

Question 13

Give 2 examples of spatial locality

Answer 13

1. Sequential instruction access
2. Array data

Question 14

What is cache?

Answer 14

Memory that holds recently used data so that it can be accessed with a lower latency next time to alleviate the von Neumann bottleneck

Question 15

What is a cache hit? What happens?

Answer 15

Data is found in the cache, so read

Question 16

What is a cache miss? What happens?

Answer 16

Data not in cache, so fetch from next level in memory hierarchy

Question 17

Write the equation for miss rate

Answer 17

Miss rate = number of cache misses / number of memory accesses

Question 18

Draw a diagram of a crude direct-mapped cache

Answer 18

.

Question 19

In a crude direct-mapped cache, for a given address, how many places are there to look?

Answer 19

1

Question 20

Give a real life example of a direct-mapped cache

Answer 20

Order all books by first two letters
Go to the right place and read the tag of the relevant book to check it is the correct one - there can only be one entry for each tag

Question 21

Which property must each item in a crude direct-mapped cache have?

Answer 21

A unique hash function value ie. cache address/tag

Question 22

What does the hash function do in a crude direct-mapped cache?

Answer 22

Takes the load address and converts it to the cache address, where the data is stored

Question 23

Give a disadvantage of a crude direct-mapped cache

Answer 23

Storing the address as a tag for every data item is a big overhead

Question 24

What is a simple direct-mapped cache?

Answer 24

Amortises the cost of crude direct-mapped cache by storing several data items per tag

Question 25

What is a cache line?

Answer 25

Some number of contiguous words in memory. Links with spatial locality and links with DRAM bursts when filling cache lines from main memory

Question 26

What is a fully associative cache?

Answer 26

There is no hash function ordering, must search through whole cache every time

Question 27

Draw a diagram of a simple direct-mapped cache

Answer 27

.

Question 28

What is the effect of larger cache lines in a variable sized cache? Why? What is a disadvantage that can override this benefit?

Answer 28

Reduce miss rate due to spatial locality. Larger miss penalty, can override the benefit of reduced miss rate

Question 29

What is the effect of larger cache lines in a fixed size cache? Why?

Answer 29

Fewer cache lines so more competition so increased miss rate Pollution so more data read in that may never be read

Question 30

How can we avoid the larger miss penalty that comes with larger cache lines?

Answer 30

Using early restart - give a word to the CPU as soon as we get it, don’t wait for the rest of the words

Question 31

How does the CPU proceed on a cache hit?

Answer 31

Normally ie. carry on and fetch the next instruction

Question 32

How does the CPU proceed on a cache miss? How does this differ between instruction and data cache misses?

Answer 32

1. Stall the CPU pipeline 2. Fetch block from next level of hierarchy 3. If it is an instruction cache miss, restart instruction fetch. If it is a data cache miss, complete data access

Question 33

What are the two ways we can handle a data-write hit (ie. the block of data to update is in the cache)?

Answer 33

1. Write-back - just update the cache line 2. Write through - also update memory for consistency

Question 34

What is a disadvantage of write-through?

Answer 34

It makes writes take longer

Question 35

What is a solution to make write-through more efficient?

Answer 35

Use a write buffer

Question 36

What is a write buffer?

Answer 36

Holds data waiting to be written to memory. CPU continues immediately and only stalls if write buffer is already full

Question 37

What do we need to keep track of in write-back? Why?

Answer 37

Whether each cache-line is dirty ie. holds new data. When a dirty block is replaced, write it back to memory

Question 38

How can a write buffer be used in write-back too?

Answer 38

Allow replacement cache line to be read first

Question 39

List how we can handle write misses for write-through and write-back

Answer 39

For write-through: 1. Allocate on miss 2. Write around For write-back: 1. Allocate on miss

Question 40

What is allocate on miss?

Answer 40

Fetch the cache line (with write-back: to avoid having a cache line where some words or bytes are invalid)

Question 41

What is write around?

Answer 41

Don't fetch the cache line, instead write the data to the next level in the hierarchy

Question 42

Draw a diagram of a fully associative cache

Answer 42

.

Question 43

How much restriction is there on where data can be stored in a fully associative cache?

Answer 43

No restrictions

Question 44

What happens to the upper address bits (tag) of a memory address in a fully associative cache?

Answer 44

They are broadcast to every cache location, each with its own comparator. Hardware is parallel, so all comparisons are done simultaneously when the CPU is trying to access a data block

Question 45

How does FPGA circuit area compare between direct-mapped and fully-associative caches?

Answer 45

- Direct-mapped caches can be efficiently implemented using embedded block RAM - Fully-associative caches have to be made out of resisters and logic so are huge

Question 46

How does efficiency compare between direct-mapped and fully-associative caches?

Answer 46

Fully-associative caches tend to have higher hit rate than a direct-mapped cache that stores the same amount of data - no cache location conflicts, every cache location can be checked at once on data access

Question 47

What is the advantage of a set associative cache?

Answer 47

Combines the efficiency of a direct-mapped cache with the higher hit rate of a more associative cache

Question 48

What is a set associative cache?

Answer 48

Has N direct-mapped caches, reads look in all N caches for data, so cache has N-way associativity

Question 49

How many items can be stored with the same tag in a set-associative cache?

Answer 49

N

Question 50

What is the replacement policy for a direct-mapped cache?

Answer 50

No choice

Question 51

What is the replacement policy for a set-associative or fully-associative cache?

Answer 51

Replace a non-valid entry if there is one 1. Least recently used (LRU) - choose the one unused for the longest time 2. Not last used - approximates LRU and is simpler to implement 3. Random - simple to implement, gives approximately the same performance as LRU for high associativity

Question 52

What is a victim cache? How is it used?

Answer 52

Augment a direct-mapped cache with a tiny full-associative cache, then give evicted cache lines a second chance in the victim cache. Eliminates some pathological missed of a direct-mapped cache but not as effective as set-associative

Question 53

List the 3 sources of cache misses

Answer 53

1. Compulsory misses 2. Capacity misses 3. Conflict misses

Question 54

What is a compulsory miss?

Answer 54

First access to a block

Question 55

What is a capacity miss?

Answer 55

Due to finite cache size A replaced block is accessed again

Question 56

What is a conflict miss?

Answer 56

In a non-fully associative cache due to competition for entries in a set

Question 57

What prevents the construction of a large, low-latency memory requiring us to use a hierarchy of memories to approximate this?

Answer 57

Physical constraints

Question 58

There is no hash function in a simple direct-mapped cache. Where does the cache address come from?

Answer 58

The index bits. The upper address bits are used to tag the data

Question 59

What is the tag in a crude direct-mapped cache?

Answer 59

Data load address