L5 & L6 & L7

Question 1

What is the simple (inefficient) solution to the cache coherency problem in multiprocessors?

Answer 1

Read/write to main memory but this negates the use of the cache

Question 2

What are the 3 states for a cache line using the MSI protocol?

Answer 2

A cache has 2 control bits for each line:

Modified state: cache line is valid but memory does not have the updated values

Invalid: the data is not valid and must be fetched from memory

Shared: not invalid and not modified

Question 3

What are the possible states for a dual-core CPU using the MSI protocol?

Answer 3

 Modified invalid
 Invalid invalid
 Invalid shared
 Shared shared

Question 4

Why is there no modified shared state? and no modified modified state?

Answer 4

because the second core cannot share the out of sync version

because only one core can be modified

Question 5

What are the state transitions for the Modified/Invalid state?

Answer 5

• Read on core 1: cache hit
• Write on core 1: cache hit
• Read on core 2: changes to Shared/Shared
• Write on core 2: changes to Invalid/Modified

Question 6

What are the state transitions for the Invalid/Invalid state?

Answer 6

• Read on core 1: fetches from memory, changes to Shared/Invalid
• Write on core 1: Fetches from memory, changes to Modified/Invalid
• Read on core 2: fetches from memory, changes to Invalid/Shared
• Write on core 2: Fetches from memory, changes to Invalid/Modified

Question 7

What are the state transitions for the Invalid/Shared state?

Answer 7

• Read on core 1: 2 sends value to 1, changes to Shared/Shared
• Write on core 1: changes to Modified/Invalid
• Read on core 2: cache hit
• Write on core 2: changes to Invalid/Modified

Question 8

What are the state transitions for the Shared/Shared state?

Answer 8

• Read on core 1: cache hit
• Write on core 1: changes to Modified/Invalid
• Read on core 2: cache hit
• Write on core 2: changes to Invalid/Modified

Question 9

What are the 2 types of snooping protocols? Which is the more widespread protocol?

Answer 9

Write-invalidate: when a core updates a cache line, other copies of that line in other caches are invalidated

Write-update: when a core updates a cache line, other copies of that line are updated

Write-invalidate is more widespread because write-update leads to higher bus traffic

Question 10

What are the two types of the Shared state? Why was this split made?

Answer 10

E: exclusive
 Switch to E after a read causing a fetch from memory

S: shared
 Switch to S after a read from another cache

This is done to distinguish when an invalidate request is necessary.

Question 11

What is the Modified state split into?

Answer 11

Modified: not in sync with memory

Owned: not in sync with memory, other valid copies in S

Question 12

Shared bus coherence does not scale well. What is a solution?

Answer 12

Directory centralising cache line information

Question 13

What does each directory entry in directory-based coherence have?

Answer 13

Present bitmap

Dirty bit (only one owner)

Question 14

Can the directory dirty bit be unset but the local dirty bit set?

Answer 14

No, because local dirty bit unset means the line is shared and there cannot be a unique owner.

Question 15

Is using a central directory for directory based coherence optimal?

Answer 15

No, central directory is a serious bottleneck. A solution is to distribute directory and cache it.

Question 16

What is an example of a distributed directory for directory based coherence?

Answer 16

NUMA (Non-uniform memory access) system, where each directory can access one socket. But, this results in slower communications.

Question 17

In a directory protocol, what happens when there is a read hit in the local cache?

Answer 17

simply read the value

Question 18

In a directory protocol, what happens when there is a read miss in the local cache?

Answer 18

If directory dirty bit is false:
o Get line from other cache or memory
o Set presence bit
o Set local valid bit

If directory dirty bit is true:
o Update memory and cache
o Clear directory dirty bit
o Set presence bit
o Set local valid bit

Question 19

In a directory protocol, what happens when there is a write hit in the local cache?

Answer 19

If local dirty bit is set: update the local cache

If local dirty bit is unset and directory dirty bit is false:
o Send invalidate to any cores with present bit set
o Set present bit
o Set directory dirty bit
o Set local dirty bit

Question 20

In a directory protocol, what happens when there is a write miss in the local cache?

Answer 20

If directory dirty bit is false
o Send invalidate to any cores with present bit set
o Set present bit
o Set directory dirty bit
o Set local dirty bit

If directory dirty bit is true:
o Owner core updates memory
o Clear owner’s present bit and set p[i] bit
o Set local dirty bit