8. Memory Hierarchy

Question 1

Define spatial locality.

Answer 1

Memory locations close to a recently accessed location are likely to be accessed again in the near future.

Question 2

Define temporal locality.

Answer 2

Recently accessed memory locations are likely to be accessed again in the near future.

Question 3

Why does locality exist in programs?

Answer 3

Instruction reuse: loops, functions.
Data working sets: arrays, objects.

Question 4

Describe the common memory hierarchy in a computer.

Answer 4

Registers (100s of bytes, ~1ns)
Cache (SRAM, 1KB-10MB, 1-10ns)
Main Memory (DRAM, 1-64GB, ~100ns)
Disk/SSD (100s GB SSD/1-2TB disk, ~100μs - 10ms)

Question 5

How does memory hierarchy take advantage of temporal locality and spatial locality?

Answer 5

Temporal locality:
- If accessing data from slower memory, move it to faster memory.
- If data in faster memory unused recently, move it to slower memory.

Spatial locality:
- If need to move a word from slower to faster memory, move adjacent words at same time.
- Gives rise to blocks and pages: units of storage within the memory hierarchy composed of multiple contiguous words.

Question 6

Between which memories does the software move the data, and which the hardware?

Answer 6

The software transfers between the registers and cache. (compiler)
The hardware transfers between the cache and main memory.
The software transfers between the main memory and disk. (operating system)

Question 7

How are hardware-managed transfers performed?

Answer 7

Data moved between levels automatically in response to the program’s memory accesses.

Memory always has a copy of cached data, but data in the cache may be more recent.

Question 8

In terms of caches, define block.

Answer 8

A block is the unit of data stored in the cache (normally in the range of 32-128 bytes). The block size is larger than a word to help exploit spatial locality.

Question 9

In terms of caches, define miss.

Answer 9

A miss is where the data is not found. The search needs to be performed in the next level of hierarchy (maybe another cache, or maybe main memory). Once the data is located, it is copied to the memory level where the miss happened.

Question 10

In terms of caches, define hit.

Answer 10

A hit is where data is found (so is completed quickly).

Question 11

In terms of caches, define hit rate.

Answer 11

The proportion of memory accesses that are hits at a given level of the memory hierarchy.

Question 12

In terms of caches, define miss rate.

Answer 12

The proportion of memory accesses that are misses at a given level of the memory hierarchy.

Question 13

In terms of caches, define allocation.

Answer 13

Placement of a new block into the caches, usually evicting another block.

Question 14

In terms of caches, define eviction.

Answer 14

Displacement of a block from the cache, which occurs when a new block is allocated in its place.

Question 15

Compare LRU and FIFO policies.

Answer 15

LRU (Least Recently Used) evicts the cache block that hasn’t been accessed for the longest.

FIFO (First In, First Out) replaces in the same order as filled.

Question 16

What are the three categories of cache?

Answer 16

Direct-mapped (each memory location is mapped to one location in the cache.)
Set-associative (each memory location can be placed in a set of locations in the cache.)
Fully-associative (each memory location can be placed anywhere in the cache.)

Question 17

In a direct-mapped cache, what is the most common mapping?

Answer 17

Cache address = (block address) mod (no. blocks in cache).

Question 18

What cache address will a memory address of 01101 take in an 8-block direct-mapped cache, with each block being a byte?

Answer 18

101

{01101 = 13 mod 8 = 5 -> 101}

Question 19

Each cache memory block has a tag associated with it. What is the purpose of the tag?

Answer 19

The tag identifies the block present at the address in the cache.

Question 20

What is the purpose of a valid bit?

Answer 20

To identify if the block is a valid address.

Question 21

A direct-mapped cache holds 16 KiB of data and 4-word blocks. Assume 32-bit addresses. How many bits are required in total?

Answer 21

16 KiB = 4096 = 2¹² words.
With a block size of 4 words, we have 2¹⁰ blocks.

Therefore, we have a index of 10 bits.
We have an offset of 4 bits (2 to specify the block, and two to specify the byte)
We therefore have a tag size of 18 bits.

16KiB for data, and (1 + 18)*2¹⁰ bits for rest.

Thus, 16 + 2.375 = 18.375 KiB

Question 22

Consider a cache with 64 blocks and a block size of 16 bytes. To what block number does byte address 1200 map?

Answer 22

Byte address 1200 will fall in the block numbered 1200/16 = 75.

75 mod 64 = 11

Question 23

Given a 4 KB, 4-way set associative cache with 4-byte blocks and 32-bit addresses, how many tag, index and offset bits does the address decompose into?

Answer 23

There are 4000 B of data, and as each block is 4B, there are 1000 blocks. These are grouped into sets of 4, so there are 250 sets.

Thus, we need 8 bits for the index.

We also need 2 bits for the offset, so the tag is (32 - (8 + 2)) = 22 bits.

Question 24

What is the write-through and write-back policy?

Answer 24

Write-through is when a hit occurs, the data is written to the cache, and then to memory.

Write-back is when a hit occurs, just the cache is updated. Each block has a dirty bit, set if the block has been written to. When a dirty is replaced, it is written to memory.

Question 25

Give an advantage and disadvantage of write-through over write-back.

Answer 25

Adv: Data in memory is always up-to-date.
Dis: Writes are slow.

Question 26

What are the write-allocate and write no-allocate policies?

Answer 26

Write-allocate: On a miss, bring the block into the cache and write to it.

Write-no-allocate: Do not bring the block into the cache; only modify data in memory.