Question

3. Consider ? 3 processor multiprocessor connected with a scalable network that has the follo ng proper t es: distributed memory o gar za ri drectory ase cache cher ence protocol i write n a date pol uso assume at the caches have a writeback policy. Initially. the caches al have invalid data. Assume that data X is stored in the memory connected to processor P2. Create a table similar to that in slide 13 of lecture 25 to indicate what happens for every request. (35 points) o o a o a P1: Read X P1: Write X P3: Read X P2: Read X P3: Write X

Answer 1

Before solving the problem we need to understand what is cache coherence problem.

Cache Coherence Problem:

This happens in shared multiprocessor system.

It is possible to have same copy of the shared variable in caches of differnt processors.

So when one processor changes that particular cache value others need to do the same. Otherwise it will lead to cache inconsistancy.

This is called cache coherence problem.

Cache coherence Mechanisms are of two types:

Snooping and directory based

Directory based is used in our question. So lets see what is directory based cache coherence mechanism.

It is used to solve cache coherence problem in Distribute shared memory model(NUMA). it uses a special centralised directory to keep track of shared variables.

Request	Cache hit/miss	Messages	Directory State	State in C1	State in C2	State in C3
P1: Read X	Miss	Read Request to Directory. Directory responds.	X:S:1	S	INV	INV
P1: Write X	Permission Miss	Upgrade request to Directory. Directory grands write permission	X:M:1	M	INV	INV
P3: Read X	Read Miss	Read request to Directory. Directory forwards request to P1. P1sends data to Directory. Memory write back. Directory sends data to P3	X:S:3	INV	INV	S
P2: Read X	Read Miss	Read request to Directory. Directory responds.	X:S:2,3	INV	S	S
P3: Write X	Write Miss	Upgrade request to Directory. Directory sends INV to P2. P2 sends ACK to Directory. Directory grants permission to P3.	X:M:3	INV	INV	M