Consider a 4-processor multiprocessor connected with a scalable network that has the following properties: (i) distributed memory organization, (ii) directory-based cache coherence protocol, (iii) write-invalidate policy. Also assume that the caches have a writeback policy. Initially, the caches all have invalid data. Assume that data X is stored in the memory connected to processor P2. Create a table similar to the example below to indicate what happens for every request. (50 points)

P1: Write X

P2: Read X

P3: Write X

P2: Write X

P4: Read X

Example Request Cache Messages Dir State State State State Hit/Miss State in C1 in C2 in C3 in C4 Inv Inv Inv Inv S Inv Inv Inv P1: Rd X Miss Rd-req to Dir. Dir responds X: S: 1 P2: Rd X Miss Rd-req to Dir. Dir responds. X: S: 1, 2 s s Inv Inv X: Inv M Inv Inv P2: Wr X Perms Upgr-req to Dir. Dir sends M: 2 Miss INV to P1. P1 sends ACK to Dir. Dir grants perms to P2. X: M: 3 Inv Inv M InV Wr-req to Dir. Dir fwds P3: Wr X Write Miss request to P2. P2 sends data to Dir. Dir sends data to P3. P3: Rd X Read Hit Inv Inv M Inv P4: Rd X Read Rd-req to Dir. Dir fwds X: S: 3, 4 Inv nV S Miss request to P3. P3 sends data to Dir. Memory wrtbk. Dir sends data to P4 11 Example Request Cache Messages Dir State State State State Hit/Miss State in C1 in C2 in C3 in C4 Inv Inv Inv Inv S Inv Inv Inv P1: Rd X Miss Rd-req to Dir. Dir responds X: S: 1 P2: Rd X Miss Rd-req to Dir. Dir responds. X: S: 1, 2 s s Inv Inv X: Inv M Inv Inv P2: Wr X Perms Upgr-req to Dir. Dir sends M: 2 Miss INV to P1. P1 sends ACK to Dir. Dir grants perms to P2. X: M: 3 Inv Inv M InV Wr-req to Dir. Dir fwds P3: Wr X Write Miss request to P2. P2 sends data to Dir. Dir sends data to P3. P3: Rd X Read Hit Inv Inv M Inv P4: Rd X Read Rd-req to Dir. Dir fwds X: S: 3, 4 Inv nV S Miss request to P3. P3 sends data to Dir. Memory wrtbk. Dir sends data to P4 11