Lecture 4: Shared Memory Multiprocessors, Lecture 6: MESI and MOESI Cache Coherence, Lecture 7: Directory-Based Cache Coherence

Question 1

How does the structure of multiprocessors differ for shared and distributed memory?

Answer 1

Shared memory: all cpus have access to the same memory

Distributed memory: each cpu has its own local memory

Question 2

Whhich is more prevalent in mutliprocessors, shared or distributed memory, and why? Are there any drawbacks?

Answer 2

Shared memory because its easier to program. Hardware is more complex

Question 3

What problem does hardware complexity of shared memory multiprocessors lead to?

Answer 3

bus-based cache coherence systems that do not scale well

Question 4

What are caches?

Answer 4

Fast and small local memory holding recently used data and instruction. Can have different levels (L1, L2 (local), L3 (shared))

Main memory cannot keep up with processor speed

Question 5

What are two cache functions?

Answer 5

1. Fetch data from RAM on cache misses
2. Write modified data back to RAM

Question 6

What is the cache coherency problem?

Answer 6

Inconsistency of shared data across multiple caches in multi-core systems. Can occur when one core updates a value in its cache, leaving outdated copies in other caches.

Question 7

What is the solution to the cache coherency problem?

Answer 7

cache to cache communication with bus snooping

for performance to avoid involving the slow memory

Question 8

How does bus snooping work in maintaining cache coherency in multiprocessor systems?

Answer 8

Hardware attached to each core’s cache (one bus). Observes all transactions on the bus and able to modify the cache independently of the core. This hardware can take action on seeing pertinent transactions on the bus

Question 9

True or false

Cache has 2 control bits for each line it contains, indicating its state

Answer 9

True

Question 10

How many cache states are there?

Answer 10

Three:
1. Modified
2. Invalid
3. Shared

Question 11

1. Modified state
2. Invalid
3. Shared

A. Implicit. A valid cache entry exists and the line has the same values as main memory. Several caches can have the same line in that state

B. there may be an address match on this line but the data is not valid. We must go to memory and fetch it or get it from another cache

C. the cache line is valid and has been written to but the latest values have not been updated in memory yet. A line can be in the modified state in at most 1 core

Answer 11

1. C
2. B
3. A

Question 12

Which of the following states are legal?

a. modified invalid
b. modified modified
c. shared shared
d. invalid shared
e. modified shared
f. invalid invalid

Answer 12

a, c, d, f

Question 13

What are the aspects of state transitions?

Answer 13

1. messages
2. access made to main memory
3. state changes

Question 14

What are the messages sent between caches?

Answer 14

1. Read messages: 1 core request a cache line from another
2. Invalidate messages: 1 core asks another to invalidate one of its cache lines

Question 15

Describe the state transitions from the following state

modified invalid

Answer 15

Read on core 1: cache hit, served from cache
Write on core 1: cache hit, served from cache
Read on core 2: Overall change to state: shared/shared
Write on core 2: Overall state changes to (a’): invalid/modified

Question 16

Describe the state transitions from the following state

invalid invalid

Answer 16

Read on core 1: Go to (c’) shared/invalid
Read on core 2: symmetry - goes to state (c): invalid/shared
Write on core 1: State goes to (a) modified/invalid
Write on core 2: symmetry - goes to state (a’): invalid/modified

Question 17

Describe the state transitions from the following state

invalid shared

Answer 17

Read on core 1: Overall state goes to (d): shared/shared
Read on core 2: Cache hit, stays in (c): invalid/shared
Write on core 1: Overall state goes to (a): modified/invalid
Write on core 2: Overall state goes to (a’): invalid/modified

Question 18

Describe the state transitions from the following state

shared shared

Answer 18

Read on core 1 or 2: cache hit, served from the cache
Write on core 1: Overall state goes to: modified/invalid
Write on core 2: symmetry, state goes to (a’): invalid/modified

Question 19

Describe state transitions beyond 2 cores

Answer 19

Snoopy bus messages are broadcasted to all cores
1. Any core with a valid value can respond to a read request
2. Upon receiving an invalidate request:
Any core in S invalidates without writeback
A core in M writes back then invalidates

Question 20

What are the snooping protocols?

Answer 20

Write-Invalidate:
When a core updates a cache line, other copies of that line in other caches are invalidated
Future accesses on the other copies will require fetching the updated line from memory/other caches
Most widespread protocol, used in MSI (this lecture), MESI, MOESI (next video)

Write-update:

Question 21

What is a major implication of chache coherence?

Answer 21

All cores must always see exactly the same state of a location in memory
If one core writes and broadcast invalidate: No other core must be able to perform a read/write to that location
All cores must see the invalidate at the same time, i.e. within the same bus cycle
The coherence protocol is a major limitation to the number of cores that can be supported

Question 22

True or false

Multiple cores can use the bus at a time

Answer 22

False

Question 23

True or false

Invalidate always needs to be broadcasted with a write

Answer 23

False

Sometimes other cores are already invalid

Question 24

Describe MESI

Answer 24

Split the S state into:
E: exclusive
Switch to E after a read causing a fetch from memory
S: (truly) shared
Switch to S after a read that gets value from another cache

Question 25

Describe MOESI

Answer 25

Split the M state into two:
Modified: not in sync with memory only copy
Owned: not in sync with memory, other valid copies in S

Owner has exclusive rights to make changes
Broadcast the changes to the shared copies. No memory writeback needed
Writeback only when data in O or M is evicted

Question 26

True or false

Even with optimisations such as MESI and MOESI, bus-based systems can’t scale to large multiprocessor counts

Answer 26

True

Question 27

Describe directory structure

Answer 27

Each directory entry has:
1. Present bitmap: which core has a copy
2. Dirty bit: only one owner

Each line in caches also valid and dirty bits

Question 28

What is the bottleneck of directory based coherence? How can it be solved?

Answer 28

Central directory.
Distribute directory and cache it e.g. NUMA, Non-Uniform Memory Access, more than one directory each with its own address space

Question 29

NUMA drawbacks

Answer 29

1. Slower communications
2. Long/variable delays requires handshakes

Question 30

True or false

Directory-based coherency, improved on MESI MOESI, and is an optimal solution.

Answer 30

False

scaling to large numbers of cores is still a problem