Lectures 9 & 10 - The Memory Hierachy

Question 1

Which caches are separate?

Answer 1

L1 data and L1 instruction caches. This allows access to data memory and instruction memory in the same cycle. Characteristics can also then be optimised for contents.

Question 2

Which caches are unified?

Answer 2

L2/L3 caches are typically unified. Allows the proportion of memory dedicated to instructions and data to be dynamically adjusted depending on program requirements.

Question 3

Blocks or Cache Lines

Answer 3

Blocks help us exploit spatial locality of data. On a cache miss we must load a minimum of one block of data from main memory into the cache.

Question 4

Block Size - Optimal

Answer 4

Larger block size allows us to better exploit spatial locality - reduces miss rate.

Increasing block size decreases number of different blocks that can be stored. - increases miss rate

Large block size - increases miss rate.

Question 5

Direct Mapped Cache

Answer 5

Each block has only one place it can be stored in the cache. Low-access time but may suffer from many collisions meaning cache lines may be repeatedly evicted despite free entries.

Question 6

Set Associative Cache

Answer 6

Each block can be in n differrent places in cache.

Question 7

Fully associative cache (using cams also known as CAM-tag or CAM-RAN cache)

Answer 7

Highly associative caches often seen in embedded systems where energy consumption is a major concern. They reduce miss rates avoiding high cost of accessing main memory.

Question 8

Block Replacement Policies

Answer 8

Want to use invalid lines in the set if possible. Otherwise use LRU scheme or approximate LRU by FIFO or Not Last Used.

Question 9

Write-Allocate

Answer 9

Allocate block in cache and then write

Question 10

No-write allocate

Answer 10

Just write to lower-level memory

Question 11

Write through

Answer 11

Write to both cache and lower level of memory when we perform a write.

Question 12

Write Back

Answer 12

Only write dirty cache blocks to lower level of memory when they are replaced.

Question 13

Average Memory Access Time

Answer 13

Hit Time + Miss Rate x Miss Penalty

Question 14

Compulsory Cache Miss

Answer 14

Generated when a block is brought into the cache for the first time.

Question 15

Capacity

Answer 15

Capacity misses are produced when the number of blocks required by a program exceeds the capacity of the cache.

Question 16

Conflict

Answer 16

Misses caused by many blocks mapping to the same set.

Question 17

Write Buffer

Answer 17

Hide lower throughput of underlying memory system particularly useful for write-through cache. It allows loads to bypass buffered stores.

Question 18

L1 Cache

Answer 18

Optimised for fast access times as cache hits will be very common. They tend to be small (fast) with lower associativity.

Question 19

L2/L3 Cache

Answer 19

Have a low miss rate and minimise off-chip/DRAM accesses. They are larger with higher associativity.

Question 20

Multi-Level Inclusion

Answer 20

Include L1 data in L2 etc. Desirable as consistency between I/O and caches can be determined by just checking the L2.

Drawbacks:

May want different block sizes - inclusion still possible.

L2 is not much larger than L1, exclusion may be better policy.

Not required for instruction caches.

Question 21

Critical Word First

Answer 21

Processor often only requires a single word from a cache block so read required word first and allow processor to continue execution.

Question 22

Sub-block placement

Answer 22

Uses sub-block placement to transfer sub-blocks. Allows size of tag-RAM to be kept small without incurring large miss penalties larger blocks cause.

Question 23

Victim Cache

Answer 23

Small fully associative cache used in conjunction with direct-mapped cache. Holds lines displaces from L1 cache. Processor checks both L1 and VC. Data is swapped if VC hits.

Aims to reduce conflict misses (20-40% of direct mapped cache misses).

Question 24

Assist Cache

Answer 24

Small fully-associative cache used to assist direct-mapped caches.

Data enters assist cache when L1 misses, lines moved out of assist cache in FIFO order.

Helps eliminate thrashing behaviour associated with direct mapped caches.

Question 25

Non-blocking caches

Answer 25

If out-of-order execution is permitted then could continue to execute even if we are waiting for a cache miss to be serviced. Can effective reduce the load miss penalty. In order to implement need to keep track of outstanding memory requests by adding special registers to store this information. Stored in miss status golding register.

Question 26

Programming for caches - simple optimisations

Answer 26

Working set is small enough to fit in the cache

Reposition program in memory to optimise instruction cache performance

Question 27

Loop Interchange

Answer 27

Improve spatial locality by favouring sequential accesses to non-unit strides.

Question 28

Loop fusion

Answer 28

Fuse together loops that access the same data to improve temporal locality.

Question 29

Array Merging

Answer 29

Guarantee spatial locality by reorganising data as array. Works well if data is related and accessed together.

Question 30

Array Padding

Answer 30

Shifts the position of arrays in memory to reduce problematic conflict misses.

Question 31

Cache Blocking

Answer 31

Organise computation so we access sub-matrices that fit into the cache.

Question 32

Sequential prefetcher

Answer 32

One Block Lookahead

On a cache miss: fetch required block and prefetch next sequential block into prefect buffer, on miss check this buffer first.

Question 33

Tagged sequential prefetcher

Answer 33

Adds tag bit per cache line which is set when a block is prefetched into the cache. If bit is set on a cache hit then next cacheline is prefetched.

Question 34

Striped prefetch

Answer 34

Detect regular access patters and prefetch data

Question 35

Regrence Prediction Table

Answer 35

indexed by address of load instruction. It stores last address referenced by load which is used to calculate and store delta between subsequent references. If stride between 3 such misses is constant then strided access pattern is assumed and delta is used to prefetch cache blocks.

Question 36

Helper Thread

Answer 36

A microthread which is run in parallel with the main thread to initiate memory request ahead of time. It can implement complex prefetch algorithm based on addresses of loads that miss.