USA: +1 (725) 712-1730 
Sign in
Architicture Class – Cache Coherence
A bus based multiprocessor system has 2 processors and a memory connected by a bus. It uses the MSI cache coherence protocol with write invalidation. Caches are write-back. A modified line is written to memory on a change of its state. The other cache that have issued a request which caused the change of state is delayed until the memory is updated, then re-tries. Initially all lines are invalid. P1 has a higher priority for bus arbitration than P2 in the case of a simultaneous attempts to access the bus. Processors execute the following time-ordered (left to right) sequence of memory requests to address A: P1: R(A), P2: R(A), P2: W(A), P1: W(A), P2 R(A) Show the protocol state transitions of the line A in each cache after each processor or request. Show where a line comes from, i.e. the memory (Mem) or cache (Ci). (Add more rows to the table if necessary).
Expert Answer
Cache Coherence Problem
Usually we except to see shared memory behavior. One core writes something to shared memory address, another core reads the shared memory it is excepted to see data written by first core. For example if core A writes x=15, core B reads x it should see the value 15. This is how shared memory works. In hardware each core has its own L1 cache. When each core has its own private cache the following problem happens:
Core A with L1 cache and Core B with its own L1 cache. Core A want to write x=15 to cache L1. Core A index L1 cache with address of ‘x’. If there is a cache miss at L1 cache of core A it fetches the whole block of ‘x’ from main memory. In the memory x=0.Core A writes the new value of x=15 to L1 cache. Now Core B wants to reads ‘x’. It uses address of ‘x’ to index to its own L1 cache and sees that it doesn’t have value of ‘x’. Therefore core B reads the value of ‘x’ from memory. Memory has x=0 still, because core A did not write back the new value of ‘x’ to memory. Because of this core B will read value of ‘x’ wrongly as 0.
From now on A can write to its own cache many times modifying ‘x’ value and not updating memory. B will read from its own cache and not checking memory. So B will keep using the value of ‘x=0’ no matter how many times A modifies value of ‘x’. So we are not receiving the communication between A’s writes to B’s reads. When a shared memory works in this way it’s said to be incoherent. To avoid this we need cache coherence which will make memory behave as a single unit even though in reality there are multiple copies of data.
MSI Coherence Protocol
In MSI a block can be in one of three states in cache. ‘I’ stands for INVALID state . A block is in INVALID state either when it’s present in the cache but its valid bit is not set or when it’s not present in cache. ‘S’ stands for SHARED state. A block is in shared state in a cache can be read without any further modifications. ‘M’ stands for MODIFIED state. In this state we can read and write the block locally. In the MODIFIED state we are sure that there are no other cache copies which is why we can localy write without informing anybody.
State Transition Table/Diagram
A state Transition Table for each relevant class in the system shows the following:
- Possible states of the class
- Events that cause a transition from on state to another
- Actions that result from state change
Let value at A be 10
| BUS REQUEST | C1 | C2 | |
| P1 Read A | C1 <- A (memory)
C1 <- A= 10 |
I=0 | |
| P2 Read A | C1 <- A (shared)
C1 <- A = 10 |
C2 <- A (shared)
C2 <- A = 10 |
|
| P2 writes 20 to A | I = 0 | C2 <-A
C2 <- A1 = 20 |
|
| A1 is written back | |||
| P1 writes 15 to A | C1 <- A = 15 (private) | C2 <- A1 = 20(private) | |
| A is written back | |||
| P2 reads A1 | C1 <- A (shared)
C1 <- A = 20 |
C2 <- A (shared)
C2 <- A = 20 |
|
