Multicore Processors

Question 1

What is a multicore processor?

Answer 1

• Multiple cores on same die
• Each core capable of running a stream of instructions
• Cores are independent but may work together
• MIMD parallelism

Question 2

What are the two ways in which we can enable communication between cores?

Answer 2

1. Shared memory
2. Message passing

Question 3

Draw a diagram to show 4 cores attached to a shared memory

Answer 3

.

Question 4

With shared memory: no matter how cores are organised, they all see ? ? values in memory

Answer 4

the same

Question 5

All cores see shared memory as a ???

Answer 5

single address space

Question 6

Writes to shared memory by one core are ? seen by others

Answer 6

eventually
Doesn’t have to happen instantly, but reads always get the most recent value

Question 7

Give 2 advantages of shared memory

Answer 7

+ Different cores can use memory to communicate - one core writes the value that the other reads
+ Shared memory is easy to program because it matches the view the programmers have

Question 8

When might one core write a value to memory that another core then reads?

Answer 8

If a program that was in the first core is rescheduled to run on the second one

Question 9

What are the advantages and disadvantages of using shared caches?

Answer 9

+ Good use of space
+ Data shared between cores faster than memory ie. good for applications that share data
- If a process has a large working set it can starve cache resources from other processes

Question 10

What are the advantages of using private caches?

Answer 10

+ Provide guaranteed space for each core
+ May be faster to access
- Different processes might have different caching requirements

Question 11

Draw a diagram of 4 cores with a shared memory and a single level of shared cache

Answer 11

.

Question 12

In this diagram, what is L1 cache really split into?

Answer 12

Data cache (read and write)
Instruction cache (read only)

Question 13

Draw a diagram of 4 cores with a shared memory and multiple shared caches

Answer 13

.

Question 14

Draw a diagram of 4 cores with a shared memory, private L1 and L2 cache, and shared L3 cache

Answer 14

.

Question 15

List the 3 cache inclusion schemes

Answer 15

1. Inclusive
2. Exclusive
3. Non-inclusive non-exclusive (NINE)

Question 16

Draw a diagram to show inclusive cache inclusion

Answer 16

.

Question 17

Draw a diagram to show exclusive cache inclusion

Answer 17

.

Question 18

Draw a diagram to show NINE cache inclusion

Answer 18

.

Question 19

What are the advantages and disadvantages of inclusive cache inclusion?

Answer 19

+ Miss may not have to go all the way to memory
- Wasteful since data is duplicated at different cache levels (L1 data is also in L2, L3)

Question 20

What are the advantages and disadvantages of exclusive cache inclusion?

Answer 20

+ More space in cache because no duplicate data
- More complicated - when we remove data from L1 it needs to be written to L2. This might kick data out of L2 etc. so effects will be propagated through cache hierarchy

Question 21

What is a write through cache?

Answer 21

Each write is propagated through caches to memory
Creates alot of traffic, still need to propagate values to other cores

Question 22

What is a write back cache?

Answer 22

Changes are written to memory after a batch of writes
Ideally only propagate values when necessary (ie. on reads by another core)

Question 23

What kind of data do caches allow faster access to?

Answer 23

Data with temporal or spatial locality

Question 24

Which type of cache do we prefer to use?

Answer 24

Write-back caches

Question 25

What is cache coherence?

Answer 25

Ensures all cores maintain a consistent view of shared data, preventing inconsistencies that can arise when multiple caches hold copies of the same data

Question 26

How can we maintain cache coherence?

Answer 26

Implement hardware to: 1. propagate values to keep caches and memory coherent 2. run cache coherence protocol to ensure all cores read the most up-to-date value for each memory address

Question 27

What is the hardware we implement for cache coherence?

Answer 27

Snoopy bus

Question 28

Describe a snoopy bus

Answer 28

Allows all caches to see what others do Using this information, caches make decisions about actions they might need to take

Question 29

Draw a diagram of 3 cores with private L1 cache and shared memory. The most up-to-date value of x is in core 1's cache, with an older copy in memory, and core 2 wants to read x. Show the snoopy bus

Answer 29

.

Question 30

How do we know the most up-to-date value?

Answer 30

Associate status bits with each cache line, on access the status tells us what actions to take

Question 31

The coherence protocol is run on ? ? ?

Answer 31

each cache line

Question 32

Draw a diagram showing the need for coherence

Answer 32

.

Question 33

What is the cache coherence protocol we will use?

Answer 33

MSI Protocol

Question 34

What 3 states could each cache line be in (ie. the 3 possible status values)?

Answer 34

1. Modified 2. Shared 3. Invalid

Question 35

Describe the modified state

Answer 35

Single up-to-date copy in this cache, value in main memory is stale

Question 36

Describe the shared state

Answer 36

Copy in this cache matches memory, may be present in other caches

Question 37

Describe the invalid state

Answer 37

No copy in this cache ie. cache miss

Question 38

What happens when there is a local read and the cache line status is M? Draw the state transition

Answer 38

Read hit, we can simply return the data M->M

Question 39

What happens when there is a local read and the cache line status is S? Draw the state transition

Answer 39

Read hit, we can simply return the data S->S

Question 40

What happens when there is a local read and: the cache line status is I and the data is in another cache in M state? Draw the state transition

Answer 40

Read miss, initiate a bus read to bring it into the cache That cache snoops the bus and flushes the data back to memory, it transitions to S state We get the data from memory and keep a copy in S state I->S

Question 41

What happens when there is a local read and: the cache line status is I and the data is in other caches in S state? Draw the state transition

Answer 41

Read miss, initiate a bus read to bring it into the cache Those caches snoop the bus but do nothing We get the data from memory and keep a copy in S state I->S

Question 42

What happens when there is a local read and: the cache line status is I and the data is not in another cache? Draw the state transition

Answer 42

Read miss, initiate a bus read to bring it into the cache We get the data from memory and keep a copy in S state I->S

Question 43

What happens when there is a local write and the cache line status is M? Draw the state transition

Answer 43

We can simply return the data, write hit M->M

Question 44

What happens when there is a local write and the cache line status is S? Draw the state transition

Answer 44

Send an upgrade request to other caches Any caches that hold a copy (in S state) invalidate We transition to M, write hit S->M

Question 45

What happens when there is a local write and: the cache line status is I and the data is in another cache in M state? Draw the state transition

Answer 45

Write miss, initiate a bus read to bring data into cache That cache snoops bus and flushes data back to memory, invalidates its own copy We get the data from memory and keep a copy in M state I->M

Question 46

What happens when there is a local write and: the cache line status is I and the data is in other caches in S state? Draw the state transition

Answer 46

Write miss, initiate a bus read to bring data into cache Those caches snoop the bus and invalidate their copies We get data from memory and keep a copy in M state I->M

Question 47

What happens when there is a local read and: the cache line status is I and the data is not in another cache? Draw the state transition

Answer 47

Write miss, initiate a bus read to bring data into cache We get data from memory and keep a copy in M state I->M

Question 48

Draw the full state transition diagram for the MSI protocol

Answer 48

.

Question 49

What is an exclusive bus read?

Answer 49

Bus read for data with the intent to modify the data

Question 50

Draw a table to show how the state of a line in one cache limits the states the same line in another cache can have

Answer 50

.

Question 51

Look over coherency example

Answer 51

.

Question 52

What would be faster than going to memory to get data as the MSI protocol requires?

Answer 52

Cache-to-cache sharing

Question 53

MSI sends a lot of invalidates for thread-private data. How can we solve this?

Answer 53

Add an extra Exclusive state - this is the only cache with a copy, value in memory is up-to-date