Consider three processors P0, P1 and P2. Each processor has a cache of 4 blocks. Each block is 3 words long. Thus, the last 3 bits are needed for block offset (which word in block). The next 2 bits are needed to decide block number. Here are the address to block translations
| Address (Dec) | Address (Hex) | Block Number | |
|---|---|---|---|
| 100 | 0001 0000 0000 | B0 | |
| 108 | 0001 0000 1000 | B1 | |
| 110 | 0001 0001 0000 | B2 | |
| 118 | 0001 0001 1000 | B3 | |
| 120 | 0001 0010 0000 | B0 | |
| 128 | 0001 0010 1000 | B1 | |
| 130 | 0001 0011 0000 | B2 |
The Main memory and Cache contents of the three processors are shown below. Each block has an associated coherency state.
The following instructions are independently applied to this initial state. Refer to the state diagrams of the MSI Protocol and follow along.
P0: read 120
- The address 120 is not available in the Cache of P0.
- Address 120 maps to B0.
- B0 is in Invalid state in P0.
- An Invalid state on CPU read, places a read miss on the bus and transitions to Shared state.
- The cache block for 120 is not present in any other cache. The bus request does not cause any changes.
P0: write 120 <- 80
- The address 120 is not available in the Cache of P0.
- Address 120 maps to B0.
- B0 is in Invalid state in P0.
- An Invalid state on CPU write, places a write miss on the bus and transitions to Modified state.
- The cache block for 100 is present in P1 and is in Invalid state. The bus request does not cause any changes.
- The cache block for 100 is present in P2 and is in Shared state. The bus request transitions this state to Invalid.
P2: write 120 <- 80
- The address 120 is not available in the Cache of P2.
- Address 120 maps to B0.
- B0 is in Shared state in P2.
- A Shared state on CPU write, places a write invalid on the bus and transitions to Modified state.
- The cache block for 100 is present in P0 and is in Invalid state. The bus request does not cause any changes.
- The cache block for 100 is present in P1 and is in Invalid state. The bus request does not cause any changes.
P1: read 110
- The address 110 is available in the Cache of P1.
- Address 110 maps to B2.
- B2 is in Invalid state in P1.
- An Invalid state on CPU read, places a read miss on the bus and transitions to Shared state.
- The cache block for 110 is present in P0 and is in Modified state. The bus request writes back the block to the requesting cache and memory and transitions to Shared state.
- The cache block for 110 is present in P1 and is in Invalid state. The bus request does not cause any changes.
P0: write 108 <- 48
- The address 108 is available in the Cache of P0.
- Address 108 maps to B1.
- B1 is in Shared state in P0.
- An Shared state on CPU write, places a write invalid on the bus and transitions to Modified state.
- The cache block for 108 is not present in P0. The bus request does not cause any changes.
- The cache block for 108 is present in P2 and is in Shared state. The bus request transitions to Invalid State.
P0: write 130 <- 78
- The address 130 is not available in the Cache of P0.
- Address 130 maps to B2.
- B2 is in Modified state in P0.
- An Modified state on CPU write doesn’t cause any changes. However, it commits the already modified block back to memory.
P2: write 130 <- 78
- The address 130 is not available in the Cache of P2.
- Address 130 maps to B2.
- B2 is in Invalid state in P2.
- An Invalid state on CPU write, places a write miss on the bus and transitions to Modified state.
- The cache block for 130 is not present in any other cache. The bus request does not cause any changes.
